Feeds:
Posts

## Fixed points of random permutations

The following two results are straightforward and reasonably well-known exercises in combinatorics:

1. The number of permutations on $n$ elements with no fixed points (derangements) is approximately $\frac{n!}{e}$.
2. The expected number of fixed points of a random permutation on $n$ elements is $1$.

As it turns out, it is possible to say substantially more about the distribution of fixed points of a random permutation. In fact, the following is true.

Theorem: As $n \to \infty$, the distribution of the number of fixed points of a random permutation on $n$ elements is asymptotically Poisson with rate $\lambda = 1$.

A boring proof

Once we know that the number of derangements of $n$ elements is approximately $\frac{n!}{e}$, we know that the number of permutations of $n$ elements with exactly $k$ elements is ${n \choose k}$ times the number of derangements of $n-k$ elements, which is approximately

$\displaystyle \displaystyle {n \choose k} \frac{(n-k)!}{e} = \frac{n!}{k! e}$

hence the probability that a permutation on $n$ elements has $k$ fixed points is approximately $\frac{1}{k! e}$, which is precisely the probability that a Poisson random variable with rate $\lambda = 1$ takes the value $k$.

A more interesting proof

For this proof we will show convergence in the sense of moments; that is, if $X_n$ is the random variable describing the number of fixed points of a random permutation on $n$ elements, we will show that the moments $\mathbb{E}(X_n^k)$ converge to the moments of a Poisson random variable $X$ with rate $\lambda = 1$. First, we compute that the moment generating function of $X$ is

$\displaystyle \mathbb{E}(e^{tX})) = \frac{1}{e} \sum_{k \ge 0} \frac{e^{tk}}{k!} = e^{e^t - 1}$

which is the exponential generating function of the Bell numbers $B_k$, which count the number of partitions of a set with $k$ elements. We conclude that

$\displaystyle \mathbb{E}(X^k) = B_k$

so it suffices to show that $\mathbb{E}(X_n^k)$ converges to $B_k$. Actually we will show a little more than this.

Theorem: $\mathbb{E}(X_n^k) = B_{k, n}$ is the number of partitions of a set with $k$ elements into at most $n$ non-empty subsets.

Proof 1. Note that

$\displaystyle \mathbb{E}(X_n^k) = \frac{1}{n!} \sum_{\sigma \in S_n} \text{Fix}(\sigma)^k$

where $\text{Fix}(\sigma)^k$ is the number of fixed points of $\sigma$ acting on the set of functions $[k] \to [n]$. It follows by Burnside’s lemma that the above sum is equal to the number of orbits of $S_n$ acting on the set of functions $[k] \to [n]$, which is precisely the number of partitions of $[k]$ into at most $n$ non-empty subsets (by taking preimages of each element of $[n]$). $\Box$

Proof 2. By the exponential formula,

$\displaystyle \sum_{n \ge 0} \frac{t^n}{n!} \sum_{\sigma \in S_n} z^{\text{Fix}(\sigma)} = \exp \left( z t + \frac{t^2}{2} + ... \right)$

which simplifies to

$\displaystyle \exp \left( (z - 1)t + \log \frac{1}{1 - t} \right) = \frac{1}{1 - t} \exp \left( (z - 1) t \right)$.

To extract $k^{th}$ moments, we can apply the differential operator $\left( z \frac{\partial}{\partial z} \right)^k$ and substitute $z = 1$. Either by induction or by a combinatorial argument (see for example this math.SE question), we can show that

$\displaystyle \left( z \frac{\partial}{\partial z} \right)^k = \sum_{r \ge 0} S(k, r) z^r \frac{\partial^r}{\partial z^r}$

where $S(k, r)$ are the Stirling numbers of the second kind, which count the number of partitions of a set with $k$ elements into exactly $r$ non-empty subsets. We conclude that

$\displaystyle \left( z \frac{\partial}{\partial z} \right)^k \frac{1}{1 - t} \exp \left( (z - 1) t \right) = \frac{1}{1 - t} \sum_{r \ge 0} S(k, r) z^r t^r \exp \left( (z - 1) t \right)$

and substituting $z = 1$ we conclude that

$\displaystyle \sum_{n \ge 0} \frac{t^n}{n!} \sum_{\sigma \in S_n} \text{Fix}(\sigma)^k = \frac{1}{1 - t} \sum_{r \ge 0} S(k, r) t^r$.

This gives

$\displaystyle \frac{1}{n!} \sum_{\sigma \in S_n} \text{Fix}(\sigma)^k = \sum_{r \le n} S(k, r) = B_{k, n}$

as desired. $\Box$