Number of Derangements on Finite Set
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:
\(\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$ |
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 = \paren {n - 1} \paren {D_{n - 1} + D_{n - 2} }$
where $D_1 = 0$, $D_2 = 1$.
Examples
Example: $7$ Envelopes
A correspondent writes $7$ letters and addresses $7$ envelopes, one for each letter.
In how many ways can all the letters be placed in the wrong envelopes?
Example: $10$ Envelopes
A correspondent writes $10$ letters and addresses $10$ envelopes, one for each letter.
In how many ways can all the letters be placed in the wrong envelopes?
Historical Note
This problem was first solved by Nicolaus I Bernoulli.
Later, independently, Euler rediscovered the solution.