Question

(a) Define a derangement.

(b) Why is counting the number of ways a hatcheck person can return hats to$n$people, so that no one receives the correct hat, the same as counting the number of derangements of$n$objects?

(c) Explain how to count the number of derangements of$n$objects.

Short answer

(a) A derangement is a permutation of objects that leaves no object in its original position.

(b) If the hatcheck person returns hats at random, so that$i^{\mathrm{th}}$hat goes to the$j^{\mathrm{th}}$person where always$i\ne j$, then it can be considered as a permutation of$n$objects (i.e.$n$hats) that leaves no object in its original position (i.e. none of the hats goes to its rightful owner).

(c) We can count derangement of $n$objects by using formula$D_n=n!\sum _{k=0}^n{(-1)}^k\frac{1}{k!}$

Step-by-step solution

  Given

(b) Counting the number of ways, a hatcheck person.

(c) The number of derangements of$n$objects

The Concept of derangement

A derangement is a permutation of objects that leaves no object in its original position.

We can count derangement of $\mathit{n}$objects by using formula${\mathit{D}}_{\mathbf{n}}\mathbf{=}\mathit{n}\mathbf{!}\mathbf{\sum }_{\mathbf{k}\mathbf{=}\mathbf{0}}^{\mathbf{n}}{\mathbf{(}\mathbf{-}\mathbf{1}\mathbf{)}}^{\mathbf{k}}\frac{\mathbf{1}}{\mathbf{k}\mathbf{!}}$.

(a) Determine the derangement

A derangement is a permutation of objects that leaves no object in its original position

(b) Determine the count

If the hatcheck person returns hats at random, so that $i^{\mathrm{th}}$hat goes to the $j^{\mathrm{th}}$person where always$i\ne j$ , then it can be considered as a permutation of $n$objects (i.e. $n$hats) that leaves no object in its original position (i.e. none of the hats goes to its rightful owner).

(c) Determine the relation to count

The number of derangements of $n$objects.

Suppose the number of derangement of a set with n elements is $D_n$.

Let $P_i$the property that a permutation fixes the $i^{\mathrm{th}}$object for $i=1,,2,\dots ,n$.

If the permutation is a derangement, then it has none of the properties $P_i,1\le i\le n$.

Thus, $D_n=N\left(P_1^{\text{'}}{P}_2^{\text{'}}\cdots P_n^{\text{'}}\right)$.

According to the principle of inclusion-exclusion.

$N\left({P^{\text{'}}}_1{P}_2^{\text{'}}\cdots P_m^{\text{'}}\right)=n+\sum _{k=1,1\le i_1<i_2<\cdots <i_k\le n}^n\sum {(-1)}^{k}N\left(P_{i_1}{P}_{i_2}\cdots P_{i_k}\right)$

If the ${\mathrm{i}}^{\mathrm{th}}$object is fixed at its position, then the rest of them can be permuted in $(n-1)$ways for each $i=1,2,\dots ,n$.

In general if $i_1,i_2,\cdots ,i_k$are fixed at their respective positions, the other objects can be permuted in exactly (n -k) ! ways, for each of the n/k different choices of k objects.

Considering $N=n$! is the total number of permutations of objects among themselves the above formula reduces to:

\(\begin{array}{c}{D_n} = n! + \sum\limits_{k = 1}^n {{{( - 1)}^k}} \cdot \left( {\begin{array}{*{20}{c}}n\\k\end{array}} \right)(n - k)!\\ = n!\sum\limits_{k = 0}^n {{{( - 1)}^k}} \frac{1}{{k!}}\end{array}\)