Математическое ожидание числа неподвижных точек

Найдите математическое ожидание числа неподвижных точек для случайной перестановки на $n$ элементах.

Это задача №4 ШАД-2013, Новосибирск.

Решение.


Шаг 0. Напомним, что число всех перестановок на $n$ элементах равно $n!$.

Шаг 1. Найдём число перестановок в которых отсутствуют неподвижные точки (НТ),
такие перестановки называются беспорядками.

#{неподвижных точек нет} = #{все перестановки} - #{есть хотя бы одна НТ}
 
Далее с помощью формулы включения-исключения посчитаем количество перестановок в которых есть хотя бы одна НТ.
Рассмотрим множества
$A_i$ = {перестановки у которых номер $i$ является НТ}, $i=1,\dots,n$
Тогда #{есть хотя бы одна НТ} = $\bigcup A_i$.
Т.е. требуется посчитать число элементов объединения $\bigcup A_i$.
Для этого используется формула включений-исключений:
$$\#\left(\bigcup A_i\right) = \sum \#A_i - \sum\#(A_i\cap A_j) + \sum\#(A_i\cap A_j\cap A_k) -$$
$$\cdots + (-1)^{m+1}\sum\#(A_{i_1}\cap A_{i_2}\cdots\cap A_{i_m}) +\cdots  (-1)^{n+1}\#(A_{1}\cap A_{2}\cdots\cap A_{n}).$$
Несложно посчитать, что  $\sum\#(A_{i_1}\cap A_{i_2}\cdots\cap A_{i_m}) = \frac{n!}{m!}$.
Получаем
$$\#\left(\bigcup A_i\right) = n! -\frac{n!}{2!} + \frac{n!}{3!} +\cdots = \sum\limits_{k=1}^{n}\frac{n!(-1)^{k+1}}{k!}.$$

В итоге,
$$\#\{ \text{НТ отстутствуют} \} = n!\cdot\sum\limits_{l=0}^{n}\frac{(-1)^{l}}{l!}$$
--- число беспорядков.

Шаг 2. Посчитаем число перестановок в которых только одна неподвижная точка,
т. е. $(n-1)$ элемент обязательно меняют свой номер.
Это соответствует беспорядку на $(n-1)$ элементе.
Всего может быть $n$ различных одиночных НТ.
Поэтому число перестановок с ровно одной НТ
$$n\cdot\left((n-1)!\sum\limits_{l=0}^{n-1}\frac{(-1)^l}{l!}\right).$$

Шаг 3. Посчитаем число перестановок в которых $k$ НТ.
Можно выбрать $C_n^k$ различных наборов НТ по $k$ элементов.
Тогда число таких перестановок
$$C_n^k\cdot\left((n-k)!\sum\limits_{l=0}^{n-1}\frac{(-1)^l}{l!}\right)$$
или
$$\frac{n!}{k!}\sum\limits_{l=0}^{n-1}\frac{(-1)^l}{l!}.$$

Шаг 4. Вероятность того, что перестановка из $n$ элементов будет иметь $k$ НТ
$$p_k = \frac{1}{k!}\sum\limits_{l=0}^{n-k}\frac{(-1)^l}{l!}.$$
Математическое ожидание
$$E = \sum\limits_{k=0}^{n}k\cdot p_k = \sum\limits_{k=1}^{n}\frac{1}{(k-1)!}\left(\sum\limits_{l=0}^{n-k}\frac{(-1)^l}{l!}\right).$$

Шаг 5. Вычислим вышеприведённую сумму.
Преобразуем сумму $\sum\limits_{k=1}^{n}\cdots$ так, чтобы суммирование велось от $0$ до $n-1$ (заменим $k=j+1$)
$$\sum\limits_{k=1}^{n}\frac{1}{(k-1)!}\left(\sum\limits_{l=0}^{n-k}\frac{(-1)^l}{l!}\right) = \sum\limits_{j=0}^{n-1}\frac{1}{j!}\left(\sum\limits_{l=0}^{n-j-1}\frac{(-1)^l}{l!}\right)$$
теперь внутри суммы прибавляем и отнимаем $\frac{(-1)^{n-j}}{(n-j)!}$
$$= \sum\limits_{j=0}^{n-1}\frac{1}{(k-1)!}\left(\sum\limits_{l=0}^{n-j}\frac{(-1)^l}{l!}\right) - \sum\limits_{j=0}^{n-1}\frac{1}{j!}\frac{(-1)^{n-j}}{(n-j)!}$$
прибавляем и отнимаем $\frac{1}{n!}$
$$= \sum\limits_{j=0}^{n}\frac{1}{(k-1)!}\left(\sum\limits_{l=0}^{n-j}\frac{(-1)^l}{l!}\right) -  \\ \frac{1}{n!} - \sum\limits_{j=0}^{n-1}\frac{1}{j!}\frac{(-1)^{n-j}}{(n-j)!} = \sum\limits_{j=0}^{n}\frac{1}{(k-1)!}\left(\sum\limits_{l=0}^{n-j}\frac{(-1)^l}{l!}\right)  - \sum\limits_{j=0}^{n}\frac{(-1)^{n-j}}{j!(n-j)!}.$$

Заметим, что
$$\sum\limits_{j=0}^{n}\frac{1}{(k-1)!}\left(\sum\limits_{l=0}^{n-j}\frac{(-1)^l}{l!}\right) = \sum p_k = 1$$
и
$$\sum\limits_{j=0}^{n}\frac{(-1)^{n-j}}{j!(n-j)!}.$$
Последнее равенство выполняется поскольку
$$\sum\limits_{j=0}^{n}\frac{(-1)^{n-j}}{j!(n-j)!} = \frac{1}{n!}\sum\limits_{j=0}^{n}(-1)^jC_n^j = (1-1)^n.$$
Следовательно, математическое ожидание числа неподвижных точек случайной перестановки на $n$ элементах равно 1.

P.s. Спасибо за комментарий. Решение "в одну строчку" из "Конкретной математики" Кнута: