# Derrangements

Consider a permutation $\sigma$ of $[n]$, and let $X^n_j$ be the random variable that takes the value $1$ if this permutation fixes $j$, and takes the value zero elsewhen. Set $X_n= \sum X_n^j$.

1. Express $P(X_n=k)$ in terms of $P(X_m=0)$ for a suitable $m$.
2. Find $P(X_n >0)$, and hence find $P(X_n=0)$.
3. Find $P(X_n=0)$ as $n\to\infty$, and deduce that $X_n$ converges in distribution to a Poission variable. Of what weight?
1. 1. Choose $k$ fixed points in a set of $n$ elements, then choose a derangement of the other $n-k$ elements, we get $n!P(X_n=k)=\binom {n}{k}(n-k)!P(X_{n-k}=0)$, so $P(X_n=k)=\frac{1}{k!}P(X_{n-k}=0)$.
2. Let $A_k$ be the number of permutations that fix $k \in [n]$, by the inclusion-exclusion principle
$n!P(X_n>0) = |\bigcup_{i=1}^n A_i| = \sum_{k_1}|A_{k_1}| - \sum_{k_1
Then, $P(X_n>0) = \sum_{j=1}^n\frac {(-1)^{j-1}}{j!}$. Thus, $P(X_n = 0 ) = \sum_{j=0}^n\frac {(-1)^{j}}{j!}$.
3. Clearly $\lim_{n\to\infty}P(X_n = 0) = \sum_{j=0}^\infty\frac {(-1)^{j}}{j!} = e^{-1}$. And, by 1., $\lim_{n\to\infty}P(X_n = k) = \lim_{n\to\infty}\frac{1}{k!}P(X_{n-k}=0) = \frac{e^{-1}}{k!} = \frac{1^ke^{-1}}{k!}$. Thus, $X_n$ converges in distribution to a Poisson variable of rate parameter $1$.