Number of Derangements on a Finite Set
From ProofWiki
Contents |
Theorem
Closed Form of Number of Derangements on a Finite Set
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)$
Recurrence Relation for the Number of Derangements on a 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.
