What's the probability that a given permutation has exactly $k$ fixed points.

Question

Given a random permutation $\sigma \in S_n$ from $[n] \to [n]$ in a uniform probability space, what is the probability that $\sigma $ has exactly $k$ fixed points for a given $k$ between $1$ and $n$?

In other words: what is the probability that $\exists x_1 ,...,x_k \in [n] : \sigma (x_i) = x_i $ for $\ i\in \{1,...,k\}$ and for every $y \notin \{x_1 , ... , x_k\}$ we get $\sigma(y) \neq y$.

I saw that $\lim_{n \to \infty } prob(A_0) = e^{-1}$ using Inclusion–exclusion principle and i belive that for a given k : $\lim_{n \to \infty} prob(A_k) = \frac{e^{-1}}{k!}$ but I am not sure how to show it.

*$A_k$ stands for the event "k".

Answer 1

There are $\binom{n}{k}$ possibilities for the $k$ fixed points.

If they are established then there are $!(n-k)$ derangements for the other points.

That gives $\binom{n}{k}\left[!(n-k)\right]$ permutations with exactly $k$ fixed points on a total of $n!$ permutations.

Also we have the formula: $$!(n-k)=(n-k)!\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}$$ and we end up with probability: $$\frac1{k!}\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}$$

Answer 2

1. Number of dearrangements of $k$-elements set is $$!k = k!\sum\limits_{m=0}^{k}\frac{(-1)^m}{m!}$$
2. In n-elements set we can select $(n-k)$ elements to dearrange them (all remaining $k$ points are fixed) in $\binom{n}{k}$ ways

Thus $$A_k^n = \binom{n}{k}(n-k)!\sum\limits_{m=0}^{n-k}\frac{(-1)^m}{m!}$$ And probability is $$P(A_k^n) = \frac{\binom{n}{k}(n-k)!\sum\limits_{m=0}^{n-k}\frac{(-1)^m}{m!}}{n!}=\frac{\frac{n!}{k!}\sum\limits_{m=0}^{n-k}\frac{(-1)^m}{m!}}{n!}=\frac{1}{k!}\sum\limits_{m=0}^{n-k}\frac{(-1)^m}{m!}$$