Closed Form of Number of Derangements on a Finite Set

Theorem

The number of derangements $D_n$ on a finite set $S$ of cardinality $n$ is:

$\displaystyle D_n = n! \left({1 - \frac 1 {1!} + \frac 1 {2!} - \frac 1 {3!} + \cdots + \left({-1}\right)^n \frac 1 {n!} }\right)$

Proof

Let $s_i$ be the $i$th element of set $S$.

Begin by defining set $A_m$, which is all of the permutations of $S$ which fixes $S_m$.

Then the number of orders, $W$, with at least one element fixed, $m$, is:

$\displaystyle W = \left|{\bigcup_{m=1}^n A_m}\right|$

Applying the Inclusion-Exclusion Principle:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle W\)	\(=\)	\(\displaystyle \sum_{m_1=1}^n \left \vert A_{m_1} \right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle - \sum_{m_1, m_2 : 1 \le m_1 < m_2 \le n} \left\vert{A_{m_1} \cap A_{m_2} } \right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle + \sum_{m_1, m_2, m_3 : 1 \le m_1 < m_2 < m_3 \le n} \left \vert A_{m_1} \cap A_{m_2} \cap A_{m_3} \right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle - \cdots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

Each value $A_{m_1} \cap \cdots \cap A_{m_p}$ represents the set of permutations which fix $p$ values $m_1, \ldots, m_p$.

Note that the number of permutations which fix $p$ values only depends on $p$, not on the particular values of $m$.

Thus from Cardinality of Set of Subsets there are $\displaystyle \binom n p$ terms in each summation.

So:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle W\)	\(=\)	\(\displaystyle \binom n 1 \left \vert {A_1} \right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle - \binom n 2 \left \vert {A_1 \cap A_2} \right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle + \binom n 3 \left\vert {A_1 \cap A_2 \cap A_3} \right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle - \cdots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle + \left({-1}\right)^{p-1} \binom n p \left \vert{A_1 \cap \cdots \cap A_p} \right\vert\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \cdots\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

$\left|{A_1 \cap \cdots \cap A_p} \right|$ is the number of permutations fixing $p$ elements in the correct position, which is equal to the number of permuting the remaining $n - p$ elements, or $\left({n - p}\right)!$.

Thus we finally get:

$\displaystyle W = \binom n 1 (n-1)! - \binom n 2 (n-2)! + \binom n 3 (n-3)! - \cdots + \left({-1}\right)^{p-1} \binom n p (n-p)! \cdots $

That is:

$\displaystyle W = \sum_{p=1}^n (-1)^{p-1} \binom n p (n-p)!$

Noting that $\displaystyle \binom n p = \frac{n!}{p!(n-p)!}$, this reduces to:

$\displaystyle W = \sum_{p=1}^n (-1)^{p-1} \frac{n!}{p!}$

$\blacksquare$

Sources

• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 78 \alpha$