In permutations and combinations, what is the concept behind this derangement formula?
$$D_n = n!\left(1-\dfrac{1}{1!}+\dfrac{1}{2!}-\dfrac{1}{3!}+...+(-1)^n\dfrac{1}{n!}\right)$$
Also, how is it the solution to the number of ways in which all letters can be put in the wrong box?
$\endgroup$ 31 Answer
$\begingroup$Consider the sequence $\{1, 2, 3, \ldots, n\}$. There are $n!$ permutations of this sequence. A derangement of the sequence is a permutation with no fixed points. Therefore, we wish to exclude those permutations which have one or more fixed points. There are $\binom{n}{k}$ ways of choosing $k$ fixed points and $(n - k)!$ ways of arranging the remaining elements of the sequence. By the Inclusion-Exclusion Principle, the number of permutations with no fixed points is \begin{align*} D_n & = \sum_{k = 0}^{n} (-1)^k\binom{n}{k}(n - k)!\\ & = n! - \binom{n}{1}(n - 1)! + \binom{n}{2}(n - 2)! - \binom{n}{3}(n - 3)! + \cdots + (-1)^n\binom{n}{n}(n - n)!\\ & = n! - \frac{n(n - 1)!}{1!} + \frac{n(n - 1)(n- 2)!}{2!} - \frac{n(n - 1)(n - 2)(n - 3)!}{3!} + \cdots + (-1)^n\frac{n!}{n!}\\ & = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n\frac{1}{n!}\right) \end{align*}
$\endgroup$ 0
