Ответ:
- Число перемещений (деренжментов) $D_n$ даётся включениями–исключениями, следовательно вероятность отсутствия точек фиксации
$$P_n=\frac{D_n}{n!}=\sum _{k=0}^n\frac{(-1{)}^k}{k!}.$$
- Асимптотика при $n\to \infty$:
$$\underset{n\to \infty }{\lim }{P}_n=\sum _{k=0}^{\infty }\frac{(-1{)}^k}{k!}=e^{-1},$$ и оценка остатка для знакопеременного ряда даёт
∣Pn−e−1∣≤1(n+1)!, \left|P_n-e^{-1}\right|\le\frac{1}{(n+1)!},
Pn −e−1 ≤(n+1)!1 , а также $D_n\sim \frac{n!}{e}$ (в том числе $D_n=\lfloor n!/e+1/2\rfloor$).
- Почему применимо приближение распределением Пуассона: пусть $X=$ число фиксированных точек и $X={\sum }_{i=1}^n{I}_i$, где $I_i$ — индикатор того, что элемент $i$ фиксирован, $P(I_i=1)=1/n$. Для любого фиксированного $k$ $$P(I_{i_1}=\cdots =I_{i_k}=1)=\frac{(n-k)!}{n!}=\frac{1}{n(n-1)\cdots (n-k+1)}\sim n^{-k},$$ поэтому все конечные моменты $X$ сходятся к моментам распределения $\mathrm{Poisson}(1)$. Следовательно $X$ сходится по распределению к $\mathrm{Poisson}(1)$, и в частности
$$P_n=P(X=0)\to e^{-1}.$$ Методы Chen–Stein дают оценку отклонения в расстоянии тотальной вариации, поэтому приближение Пуассона корректно и для вероятностей конечных значений.
- Ограничения: приближение Пуассона верно для фиксированных (нерастущих с $n$) чисел фиксированных точек; для событий, зависящих от большого (растущего) числа фиксированных точек, простое пуассоновское приближение может быть неприменимо.