Question

17. (4 points) Answer the hat-check problem (ie, the problem of derangements) for general n. This number is known as Dr.-

Answer 1

The total number of permutations of n hats =n!

The total number of permutations of n hats such that first hat to the first position= (n-1)!

The total number of permutations of n hats such that first two hats to their respective position= (n-2)!

.....

.....

.....

The total number of permutations of n hats such that n hats to the respective position= 0!

Since there are n hats, the number of ways of selecting one hat to fix at its respective position=$\binom{n}{1}$

The number of ways of selecting two hats to fix at their respective position= $\binom{n}{2}$

The number of ways of selecting three hats to fix at their respective position=$\binom{n}{3}$

.....

.....

.....

The number of ways of selecting n hats to fix at their respective position=$\binom{n}{n}$

Hence, by the Exclusion-Inclusion Principle,

The number of ways of putting n hats such that none goes to its respective position:

»-(*)x – 1) + ( x – 2) -() – 3) + ... + (-)(-) :