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 $n$ elements with no fixed points (derangements) is approximately $\frac{n!}{e}$ .
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$

Posted in math.CO, math.PR | Tagged generating functions, MaBloWriMo | 2 Comments

2 Responses

on September 7, 2020 at 10:28 am | Reply 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. […]
on November 9, 2012 at 11:23 pm | Reply 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. […]

Comments RSS

	ZW on The double commutant theo…
	auto on More about the Schrödinger equ…
	Jaromir Kuben on Meditation on the Sylow theore…
	Qiaochu Yuan on Meditation on the Sylow theore…
	Qiaochu Yuan on Some remarks on the infinitude…

Annoying Precision

"A good stock of examples, as large as possible, is indispensable for a thorough understanding of any concept, and when I want to learn something new, I make it my first job to build one." – Paul Halmos