Closed Form for Number of Derangements on Finite Set

From ProofWiki
Jump to: navigation, search

Theorem

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

$D_n = n! \left({1 - \dfrac 1 {1!} + \dfrac 1 {2!} - \dfrac 1 {3!} + \cdots + \dfrac {\left({-1}\right)^n} {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\vert {\bigcup_{m \mathop = 1}^n A_m}\right\vert$

Applying the Inclusion-Exclusion Principle:


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

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 $\dbinom n p$ terms in each summation.

So:

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


$\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:

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

That is:

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

Noting that $\dbinom n p = \dfrac {n!} {p! \left({n - p}\right)!}$, this reduces to:

$\displaystyle W = \sum_{p \mathop = 1}^n \left({-1}\right)^{p - 1} \dfrac {n!} {p!}$

$\blacksquare$


Also see


Sources