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

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".

• The number $D_{n,k}$ of permutations with exactly $k$ fixpoints of an $n$-set is called a rencontres number. – Jeppe Stig Nielsen Oct 10 '17 at 11:36

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!}$$

• Very cool! As $n$ grows (for fixed $k$), this approaches $\frac1{k! e}$ – MichaelChirico Nov 6 '19 at 11:31
• And also by corollary, the probability of at least one fixed point approaches $1-\frac1{e}$ – MichaelChirico Nov 6 '19 at 11:38
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!}$$

By way of enrichment here is an alternate formulation using combinatorial classes. The class of permutations with fixed points marked is

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\mathcal{U} \times \textsc{CYC}_{=1}(\mathcal{Z}) + \textsc{CYC}_{=2}(\mathcal{Z}) + \textsc{CYC}_{=3}(\mathcal{Z}) + \cdots).$$

This gives the generating function $$G(z, u) = \exp\left(uz + \frac{z^2}{2} + \frac{z^3}{3} + \frac{z^4}{4} + \frac{z^5}{5} + \cdots\right)$$

which is

$$G(z, u) = \exp\left(uz-z+\log\frac{1}{1-z}\right) = \frac{\exp(uz-z)}{1-z}.$$

Now for $$k$$ fixed points we get

$$[u^k] \frac{\exp(uz-z)}{1-z} = [u^k] \frac{\exp(uz)\exp(-z)}{1-z} = \frac{z^k}{k!} \frac{\exp(-z)}{1-z}.$$

This is the EGF of permutations having $$k$$ fixed points. We extract the count by computing (the factor $$n!$$ is canceled because we require the average)

$$[z^n] \frac{z^k}{k!} \frac{\exp(-z)}{1-z} = \frac{1}{k!} [z^{n-k}] \frac{\exp(-z)}{1-z}.$$

We find

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{k!} \sum_{q=0}^{n-k} \frac{(-1)^q}{q!}.}$$

We can identify this as choosing the $$k$$ fixed points and combining them with a derangement of the rest:

$$\frac{1}{n!} {n\choose k} (n-k)! \sum_{q=0}^{n-k} \frac{(-1)^q}{q!}$$

which is the combinatorial class

$$\textsc{SET}_{=k}(\mathcal{Z}) \times \textsc{SET}(\textsc{CYC}_{\ge 2}(\mathcal{Z})).$$