XII OM - III - Task 6

Someone wrote six letters to six people and addressed six envelopes to them. In how many ways can the letters be placed into the envelopes so that no letter ends up in the correct envelope?
Let $ F (n) $ denote the number of all ways of placing $ n $ letters $ L_1, L_2, \ldots, L_n $ into $ n $ envelopes $ K_1, K_2, \ldots, K_n $ so that no letter $ L_i $ ends up in the correct envelope $ K_i $, or more simply, so that there is no "hit". We need to calculate $ F (6) $.
Suppose we incorrectly place all letters by putting letter $ L_1 $ in envelope $ K_i $ ($ i \ne 1 $). There are $ 2 $ cases:
a) Letter $ L_i $ ends up in envelope $ K_1 $. The remaining $ 4 $ letters must then be incorrectly placed in the remaining $ 4 $ envelopes, which can be done in $ F (4) $ ways. Since $ K_i $ can be any of the $ 5 $ envelopes $ K_2 $, $ K_3 $, $ K_4 $, $ K_5 $, $ K_6 $, case a) can occur $ 5 \cdot F (4) $ times.
b) Letter $ L_i $ does not end up in envelope $ K_1 $. By assigning envelope $ K_1 $ to letter $ L_i $ as its "pseudo-correct" envelope, we can say that none of the letters $ L_2 $, $ L_3 $, $ L_4 $, $ L_5 $, $ L_6 $ end up in their correct envelopes, which can be done in $ F (5) $ ways. Since $ K_i $ can be any of the $ 5 $ envelopes, case b) can occur $ 5 \cdot F (5) $ times.
Since cases a) and b) cover all possibilities, therefore

Analogously

\[ F (5) = 4F (4) + 4F (3) \]

\[ F (4) = 3F (3) + 3F (2) \]

\[ F (3) = 2F (2) + 2F (1). \]

But of course

\[ F (2) = 1 \]
\[ F (1) = 0 \]

Therefore, from the above equations, we obtain sequentially,

\[ F (3) = 2 \cdot 1 + 2 \cdot 0 = 2 \]
\[ F (4) = 3 \cdot 2 + 3 \cdot 1 = 9 \]
\[ F (5) = 4 \cdot 9 + 4 \cdot 2 = 44 \]

Note. In the above solutions, the number $ 6 $ does not play any significant role. The same methods can be applied to $ n $ letters and $ n $ envelopes. Method I leads to the formula

\[ F (n) = (n - 1) [F (n - 1) + F (n - 2)] \]

This is the so-called recursive or reduction formula, which allows us to calculate $ F (n) $ if the values of $ F (n - 1) $ and $ F (n - 2) $ are known. Similarly, Method II leads to the recursive formula

\[ F (n) = nF (n - 1) + (-1)^n \]

Formula (1) allows us to calculate $ F (n) $ in terms of $ n $. We can write this formula as

\[ F (n) = nF (n - 1) + (-1)^n \]

From formula (3), we see that the function $ F (k) - kF (k - 1) $ has the same absolute value for every natural number $ k > 1 $, but changes sign when transitioning from $ k $ to $ k + 1 $. And since

\[ F (2) - 2F (1) = 1 \]

we have

\[ F (3) - 3F (2) = -1 \]
\[ F (4) - 4F (3) = 1 \]
\[ \ldots \]

From equality (4), we get

\[ F (n) - nF (n - 1) = (-1)^n \]

We introduce the notation

\[ \varphi (k) = \frac{F (k)}{k!} \]

Formula (5) becomes

\[ \varphi (k) - \varphi (k - 1) = \frac{(-1)^k}{k!} \]

Analogously

\[ \varphi (n) - \varphi (n - 1) = \frac{(-1)^n}{n!} \]

\[ \varphi (n - 1) - \varphi (n - 2) = \frac{(-1)^{n-1}}{(n-1)!} \]

\[ \ldots \]

\[ \varphi (2) - \varphi (1) = \frac{1}{2}. \]

Adding these formulas and considering that $ \varphi (1) = \frac{F (1)}{1} = 0 $, we get

\[ \varphi (n) = \sum_{k=1}^{n} \frac{(-1)^k}{k!} \]

Therefore,

\[ F (n) = n! \sum_{k=1}^{n} \frac{(-1)^k}{k!} \]

The problem we solved is known as the Bernoulli-Euler problem of the mislaid letters.