Number of Derangements on Finite Set

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$

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$.

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?

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?

This problem was first solved by Nicolaus I Bernoulli.

Later, independently, Euler rediscovered the solution.