Closed Form for Number of Derangements on Finite Set

From ProofWiki
Jump to navigation Jump to search

Theorem

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

\(\ds D_n\) \(=\) \(\ds n! \paren {1 - \dfrac 1 {1!} + \dfrac 1 {2!} - \dfrac 1 {3!} + \cdots + \dfrac {\paren {-1}^n} {n!} }\)
\(\ds \) \(=\) \(\ds !n\) where $!n$ denotes the subfactorial of $n$


Proof 1

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 permutations, $W$, with at least one element fixed, $m$, is:

$\ds W = \size {\bigcup_{m \mathop = 1}^n A_m}$


Applying the Inclusion-Exclusion Principle:

\(\ds W\) \(=\) \(\ds \sum_{m_1 \mathop = 1}^n \size {A_{m_1} }\)
\(\ds \) \(\) \(\, \ds - \, \) \(\ds \sum_{m_1, m_2 : 1 \mathop \le m_1 \mathop < m_2 \mathop \le n} \size {A_{m_1} \cap A_{m_2} }\)
\(\ds \) \(\) \(\, \ds + \, \) \(\ds \sum_{m_1, m_2, m_3 : 1 \mathop \le m_1 \mathop < m_2 \mathop < m_3 \mathop \le n} \size {A_{m_1} \cap A_{m_2} \cap A_{m_3} }\)
\(\ds \) \(\) \(\, \ds - \, \) \(\ds \cdots\)

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:

\(\ds W\) \(=\) \(\ds \binom n 1 \size {A_1}\)
\(\ds \) \(\) \(\, \ds - \, \) \(\ds \binom n 2 \size {A_1 \cap A_2}\)
\(\ds \) \(\) \(\, \ds + \, \) \(\ds \binom n 3 \size {A_1 \cap A_2 \cap A_3}\)
\(\ds \) \(\) \(\, \ds - \, \) \(\ds \cdots\)
\(\ds \) \(\) \(\, \ds + \, \) \(\ds \paren {-1}^{p - 1} \binom n p \size {A_1 \cap \cdots \cap A_p}\)
\(\ds \) \(\) \(\ds \cdots\)


$\size {A_1 \cap \cdots \cap A_p}$ is the number of permutations fixing $p$ elements in position.

This is equal to the number of permutations which rearrange the remaining $n - p$ elements, which is $\paren {n - p}!$.


Thus we finally get:

$W = \dbinom n 1 \paren {n - 1}! - \dbinom n 2 \paren {n - 2}! + \dbinom n 3 \paren {n - 3}! - \cdots + \paren {-1}^{p - 1} \dbinom n p \paren {n - p}! \cdots$


That is:

$\ds W = \sum_{p \mathop = 1}^n \paren {-1}^{p - 1} \binom n p \paren {n - p}!$


Noting that $\dbinom n p = \dfrac {n!} {p! \paren {n - p}!}$, this reduces to:

$\ds W = \sum_{p \mathop = 1}^n \paren {-1}^{p - 1} \dfrac {n!} {p!}$

$\blacksquare$


Proof 2

A derangement is a permutation that fixes no elements.

So, to compute the total number of derangements, we compute the number of permutations that fix elements, that is leave elements in the same place.

Let $\pi$ be a permutation of $S$.

Let $x, y \in S$.

Let $i$ be a position in a given permutation of set $S$, where $1 \le i \le n$.

Let $\map {P_i} \pi$ be the property that $\map \pi x = y$ at position $i$.

Let $\map N {P_i, \dots, P_j}$ be the number of permutations where $\map {P_i} \pi, \dots, \map {P_j} \pi$ hold.


If we consider all the permutations of a set where the property $P_i$ holds, we have fixed a single element of the set.

So there are $\paren {n - 1}!$ such possible permutations.

Furthermore, we could have chosen $i$ as any element in the set so there are $\dbinom n 1$ terms to choose from.

So $\map N {P_i} = \paren {n - 1}!$ and there are $\dbinom n 1$ terms.

Similarly, $\map N {P_i, P_j} = \paren {n - 2}!$ and there are $\dbinom n 2$ terms.


So now we can compute the total number of derangements:

\(\ds D_n\) \(=\) \(\ds n! - \dbinom n 1 \paren {n - 1}! + \dbinom n 2 \paren {n - 2}! - \ldots + \paren {-1}^n \dbinom n n \paren {n - n}!\)
\(\ds \) \(=\) \(\ds n! - \frac {n!} {1! \paren {n - 1}!} \paren {n - 1}! + \frac {n!} {2! \paren {n - 2}!} \paren {n - 2}! - \cdots + \paren {-1}^n \frac {n!} {n! \paren {n - n}!} \paren {n - n}!\) Definition of Binomial Coefficient
\(\ds \) \(=\) \(\ds n! \paren {1 - \frac 1 {1!} + \frac 1 {2!} - \frac 1 {3!} + \cdots + \paren {-1}^n \frac 1 {n!} }\)

$\blacksquare$


Also see


Historical Note

This problem was first solved by Nicolaus I Bernoulli.

Later, independently, Euler rediscovered the solution.


Sources