Number of Derangements on Finite Set

From ProofWiki
Jump to navigation Jump to search

Theorem

Closed Form for Number of Derangements on Finite Set

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

$D_n = n! \paren {1 - \dfrac 1 {1!} + \dfrac 1 {2!} - \dfrac 1 {3!} + \cdots + \dfrac {\paren {-1}^n} {n!} }$


Recurrence Relation for Number of Derangements on Finite Set

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

$D_n = \left({n - 1}\right) \left({D_{n-1} + D_{n-2}}\right)$

where $D_1 = 0$, $D_2 = 1$.


Historical Note

This problem was first solved by Nicolaus I Bernoulli.

Later, independently, Euler rediscovered the solution.