## Fixed points of random permutations

November 7, 2012 by Qiaochu Yuan

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

- The number of permutations on elements with no fixed points (derangements) is approximately .
- The expected number of fixed points of a random permutation on elements is .

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 , the distribution of the number of fixed points of a random permutation on elements is asymptotically Poisson with rate .

**A boring proof**

Once we know that the number of derangements of elements is approximately , we know that the number of permutations of elements with exactly elements is times the number of derangements of elements, which is approximately

hence the probability that a permutation on elements has fixed points is approximately , which is precisely the probability that a Poisson random variable with rate takes the value .

**A more interesting proof**

For this proof we will show convergence in the sense of moments; that is, if is the random variable describing the number of fixed points of a random permutation on elements, we will show that the moments converge to the moments of a Poisson random variable with rate . First, we compute that the moment generating function of is

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

so it suffices to show that converges to . Actually we will show a little more than this.

**Theorem:** is the number of partitions of a set with elements into at most non-empty subsets.

*Proof 1.* Note that

where is the number of fixed points of acting on the set of functions . It follows by Burnside’s lemma that the above sum is equal to the number of orbits of acting on the set of functions , which is precisely the number of partitions of into at most non-empty subsets (by taking preimages of each element of ).

*Proof 2.* By the exponential formula,

which simplifies to

.

To extract moments, we can apply the differential operator and substitute . Either by induction or by a combinatorial argument (see for example this math.SE question), we can show that

where are the **Stirling numbers of the second kind**, which count the number of partitions of a set with elements into exactly non-empty subsets. We conclude that

and substituting we conclude that

.

This gives

as desired.

### Like this:

Like Loading...

*Related*

on November 9, 2012 at 11:23 pm |Short cycles in random permutations « Annoying Precision[…] Previously we showed that the distribution of fixed points of a random permutation of elements behaves asymptotically (in the limit as ) like a Poisson random variable with parameter . As it turns out, this generalizes to the following. […]