Derangements

Today I turned 25487 days old and the first OEIS entry for this number is A002467: 

Given \(n\) letters and \(n\) envelopes, how many ways are there to fill the envelopes so that at least one letter goes into its right envelope? 

It took some further investigation to realise that this sequence was closely related to OEIS A000166 the numbers of derangements of \(n\): 1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ...

So what is a derangement? According to Wikipedia:

In combinatorial mathematics, a derangement is a permutation of the elements of a set, such that no element appears in its original position. In other words, derangement is a permutation that has no fixed points. 

The number of derangements of a set of size \(n\), usually written \(Dn\), \(dn\), or \(!n\), is called the "derangement number" or "de Montmort number". (These numbers are generalised to rencontres numbers.) The subfactorial function (not to be confused with the factorial \(n!\)) maps \(n\) to \(!n\). No standard notation for subfactorials is agreed upon; \(n¡\) is sometimes used instead of \(!n\). 

The problem of counting derangements was first considered by Pierre Raymond de Montmort in 1708; he solved it in 1713, as did Nicholas Bernoulli at about the same time.

To construct the formula, let's consider \(n\) letters and \(n\) envelopes. The first envelope can be filled in \(n-1\) ways and, for the second envelope, there are two possibilities. If the second envelope is filled with the first letter, then the first and second letters are taken care of the problem is reduced to \(n-2\) envelopes and \(n-2\) letters. If this does not happen, then there are now \(n-1\) envelopes and \(n-1 \) letters. This can be written as: $$ !n=(n-1)(!(n-1)+!(n-2))$$From here a formula can be derived to calculate the derangements for \(n\) items, specifically:$$!n=n! \sum_{i=0}^{n} \frac{(-1)^n}{i!}$$For this formula !0=1 and !1=0. In the case of 8 letters and 8 envelopes, we get: !8 = 14833.

One letter has ended up in the right envelope. There are 25487
ways in which at least one letter will end up in the right envelope.

So 14833 is the number of ways that no letters end up in the right envelopes. We are interested in the number of ways that at least one letter will end up in the right envelope. So 14833 needs to be subtracted from 8! = 40320 (the total number of possibilities) to get 25487.

Let's look at how the probability of a derangement changes as the number of elements increases. It can be noted that the Taylor Series for the function \(f(x)=1/e^x\) is given by:$$
\frac{1}{e^x}= \sum_{i=0}^{\infty} \frac{(-1)^i x^i}{i!}
$$So when \(x=1\), it can be seen that \(1/e\) is identical to the formula for the derangements:$$
\frac{1}{e}= \sum_{i=0}^{\infty} \frac{(-1)^i}{i!} \approx 0.3678794412
$$So after about four elements, the probability of a derangement quickly settles down to about 37%, no matter what the number of elements. Here is a link to a paper on derangements that begins:

A group of \(n\) men enter a restaurant and check their hats. The hat-checker is absent minded, and upon leaving, she redistributes the hats back to the men at random. What is the probability \(P_n\) that no man gets his correct hat, and how does \(P_n\) behave as \(n \rightarrow \infty\)?

Here are two Numberphile videos on Derangements with James Grimes presenting. The first is an introduction and the second derives a proof for the formula: