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.
Would you have published references to your “reasonably well-known exercises in combinatorics” and to your E(X^k)=B_k?
[…] 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. […]
[…] 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. […]