Can you possibly clarify the terms such as ‘moves’.
Are you saying that man gets his own coat?
I'm confused about how to approach this problem. If someone could give me a start, I would really appreciate it!
Suppose n men throw their coats into a closet and later pick them up blindly - one coat per man, uniform probability that any particular coat will go to any particular man.
Let B_n be the number of ways of permuting n coats so that every coat gets moved (i.e. B_2 = 1 because there is 1 way of switching 2 coats so that each coat gets moved).
Let C_n be the number of permutations (i.e. C_2 = 2 because there are 2 ways of arranging 2 objects. In general, C_n = n!).
B_n divided by C_n equals D_n.
Prove that D_n - D_{n-1} = -1/n (D_{n-1} - D_{n-2}).
This is what I mean by "moved." Sorry, I should have stated it more clearly:
Each man puts his coat in a certain position in the closet. B_n means the number of ways such that each coat gets switched to a different position in the closet (so that when each man returns to the closet to pick up his coat, he winds up with a different one than before because since he is unaware that the coats were moved, he is picking his coat based on where he initially placed it in the closet).
For example, B_2 = 1 because there is only one way of switching the coats so that each of two men winds up with a different coat than the one he started with. Using the same logic, B_3 = 2.
I am not sure that I can give you help with the proof of the recursion formula.
However, I can give you the exact formula for:
Those are called derangements or totally active permutations; rearrangements in which no element remains in the original position.