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

Найдите математическое ожидание числа неподвижных точек для случайной перестановки на $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. Спасибо за комментарий. Решение "в одну строчку" из "Конкретной математики" Кнута: