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?

I wrote a blog post about an approach to this problem using integrals. You might find it interesting. http://mathblag.wordpress.com/2010/12/23/counting-with-integrals-2/

Thanks, David, that’s a really cool way of thinking about things. I love the line about how people don’t usually think about integrals being a way to count things.

Here is a brute force solution to an algebra problem I did with my daughter using Scratch (from MIT). Actually, this is just a screencast of how to make it.

http://vimeo.com/7355830

This is great. “What’s it called? (I told you before)” “Oh, Brute Force!”. Love it.

He pointed to the bottom “guy” and said he could either move his hat clockwise or counterclockwise, so, two ways.Whoa, deep.

Pingback: Deranged « Dethorning STEM

Another great thing about the brute force approach is that… 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…Actually, if I were to teach the problem of derangements to undergraduates*, and wanted to test whether they really understood my derivation of the solution, this would be a nice tractable little question to do so. I’ll have to keep it in mind. (Your point about questions that don’t have analytical solutions is also well-taken, though.)

* Unfortunately I opted not to cover the problem of derangements in my discrete math class this year. I think the level of difficulty is appropriate for the course, but it’s a bit too time-consuming for a rather non-standard topic.

It’s funny, I knew that the 2 hats one was likely analytical but I couldn’t quickly come up with one that definitely wouldn’t be analytical. Can you? Thanks again for getting me going on this!

Huh, I guess I forgot to subscribe to comments. Sorry for the delay. To get an ordering in which exactly two people have the right hat, you pick the two who keep their hats and “derange” the other 6 hats. The number of ways to do this is 8C2 times the number of ways can I rearrange 6 letters so that no letter is in its original position: 28 * 265 = 7420.

Also,

How many ways can the second person and one other have the correct hat…Choose the “one other” person and derange the other 6. There are 8 * 265 = 2120 ways to do this.

…or how often do the 4th, 5th, and 6th people (only) have the correct hats?Derange the other 5 people. There are 44 ways to do this.

Here’s a derangement-like problem whose analytical solution does not immediately occur to me (but, to be honest, probably exists): If 8 people sit in a row, how many ways can you rearrange their hats so that no one receives a hat from one of their neighbors?

This sequence is http://oeis.org/A001883 (if a person cannot get his own hat or his neighbor’s hat) or http://oeis.org/A078480 (if a person can get his own hat but not his neighbor’s hat). The latter sequence has an explicit formula.

That was astoundingly fast. How did you do that? Brute force then OEIS search?

Yes. That’s my usual approach to counting problems when the answer isn’t immediately obvious.