More brute force probability

Last night a tweep of mine posted this:

How many ways can I rearrange the letters ABCDEFGH so that no letter is in its original position? What a deceptively simple question!—
R. Wright (@r_w_wright) September 01, 2011

I thought about it for a while with factorials running through my head but, as more people were commenting that it’s not trivial, I thought I’d try a brute force approach just to see what the answer was.

I’ve blogged about a brute force approach to probability before. The basic idea is that computers are plenty fast these days to just try all combinations of things and count whatever it is you’re looking for.

My approach

So I scratched my head for a bit to see how to get Mathematica to do the counting for me. My first approach worked so I went with it:

• Make an array with 8 different numbers (orig=Range[8])
• Find all permutations and store them (all=Permutations[orig])
• make a function to check how many characters are in their original location (check[list_]:=Count[list-orig, 0])
• What this does is term-by-term subtract the original array from the test permutation (“list”). If there are any zeros, then there was a digit in the correct place. This function simply counts how many zeros there are.
• Run all the permutations through the function (checklist=check/@all;)
• Note, the semicolon is important because it’s a long list you don’t want to display. You should do the same with the permutation command above
• Check how many of those came up with zero zeros (meaning no digit was in its original place): (total=Count[checklist, 0])

Using that, I got 14,833 permutations out of the 40,320 (or 8!) total where the no digit was in its original place.

Analytical solution

Professor Wright has since posted his analytical solution. Note that he also has a link to a cool screencast of a different analytical solution. These are very thorough and very cool. I learned a lot working my way through them. I especially like that, if you start to use a lot of letters (or hats or digits or whatever), the number of  deranged permutations is given by and so the probability of finding one is . That’s cool!

Pattern solution

Another excellent contribution to the conversation last night can be seen here:

@earlsamuelson @r_w_wright For AB, 1 way. ABC, 2 ways. For ABC, 9. Leads me to suspect oeis.org/A000166—
Max Goldstein (@dethornSTEM) September 01, 2011

This was very cool. He did it for 2 and then 3 letters and then just put the pattern he saw into an awesome web page that finds known series that match the pattern. UPDATE: HERE’S HIS BLOG POST ON IT. Check the web page out, it’s very cool.

Discussion

So what do all these approaches bring to the table. There’s no question that the analytical approaches really make you think clearly about the problem, and allow you to get a result for any number of letters (or hats, digits, . . .). It’s the most thorough and, some would say, satisfying.

However, the analytical approaches are difficult, especially as you think about asking this question to an audience that might not be able to handle some of the probability jargon.

Next, what about the pattern matching way? I think getting students to start seeing patterns is an important goal of mine. It reminds me of teaching differential equations. We want students to say things like “hey, this is the Bessel equation! I know the solutions to that” even when they’re studying a brand new physical system.

Finally, the brute force way. It certainly true that it gives you the answer you’re looking for quite quickly, but is there any more? I think so (hence the blog post For me, figuring out how to get Mathematica to do what I wanted took a little head-scratching. How do I mathematically determine whether a pattern meets my criteria? Figuring that out was fun, and, I think, could be a useful thing to do with students if you throw a problem like this at them.

Another great thing about the brute force approach is that, once you have the basic code together, it’s easy to ask different questions, some of whom may not have analytical solutions. For example, what if you wanted to calculate how many derangements have two people with the correct hat (Count[checklist, 2] = 7420). Or, how many ways can the second person and one other have the correct hat, or how often do the 4th, 5th, and 6th people (only) have the correct hats? I think it would be fun to work with students in a computer lab doing things like that.

My son

As I was typing this up, I asked my 11 year old son how he’d do it. I posed it as the hats version to give him context. I told him to do 8 people and he balked a little but I encouraged him to do 2 people (he nailed it). Then I said, how about 3 people. Almost immediately he said “2 ways” with great confidence. I asked him how he did it. He put up three fingers in a triangle with the point at the bottom. He pointed to the bottom “guy” and said he could either move his hat clockwise or counterclockwise, so, two ways. Cool huh?

About these ads