If n people mix their hats, why are there (n-1)! permutations in which no one gets his own?

Question

I am looking for the smartest explanation from a pedagogical point of view.

Draco: Sorry, but I don't get your reasoning. (n-1)! is the number of all possible permutations of n-1 hats, but we have n hats in this case.

That's right, I was wrong. So what's the general formula?

I give 10 points for the general formula in the case of n hats.

Answer 1

There aren't. Consider 4 men and their hats - they may be distributed in the following ways without any hat being returned to its owner:

[2,1,4,3]
[2,3,4,1]
[2,4,1,3]
[3,1,4,2]
[3,4,1,2]
[3,4,2,1]
[4,1,2,3]
[4,3,1,2]
[4,3,2,1]

Your formula predicts that there are only (4-1)!=6 ways to do this. Yet as you can clearly see, the valid permutations number nine. The hat-check problem is much more complicated than you make it out to be at first - here is an article discussing it:

http://www.vm.ibm.com/DEVPAGES/GREER/MENSHATS.HTML

Answer 2

Not true, is it? Or am I misunderstanding? Look at the case for 4:

1 2 3 4
------------
2 1 4 3
2 3 4 1
2 4 1 3
3 1 4 2
3 4 1 2
3 4 2 1
4 1 2 3
4 3 1 2
4 3 2 1

This is 9 different ways for 4 hats, which according to your question should be 3! = 6. Am I missing something?

Darn, I was too slow. No wonder I was having trouble figuring the actual answer out.

Answer 3

It would be n! permutations if a hat was allowed to be in the correct spot (on the owner's head). However, since each hat cannot be on its owner's head, there are n-1 possible locations for each hat and a total of (n-1)! permutations of hats where none of them are on their owner's head.

Answer 4

Damn dude. I want what you're smokin'!