Random Permutations (Part 2)
Posted by John Baez
Here’s a somewhat harder pair of problems on random permutations, with beautiful answers.
Puzzle 3. In the limit as , what is the probability that the shortest cycle in a randomly chosen permutation of an -element set has length ?
We mainly need to count the permutations of an -element set whose shortest cycle has length . So, we define a functor
from the groupoid of finite sets to the category of finite sets, sending any finite set to the finite set
A functor from to is called a finite species and this is what my course was about. We think of a finite species as a map sending any finite set to the set of ‘-structures’ we can put on . Any finite species has a ‘generating function’
where in we are using as our notation for some -element set. Our basic strategy will be to compute the generating function of the species and use that to count permutations of an -element set whose shortest cycle has length . But in fact, to save work, we will just work out the asymptotics as .
We can compose species: a structure on consists of a way of writing as a union of disjoint parts, putting a -structure on the set of parts, and putting an -structure on each part. We have
where at right we’re composing generating functions.
So, if we can write as a composite of two species whose generating functions we know, we can work out .
In fact is the composite of two species called and . The species is called ‘being a finite set’: we can put an -structure on any finite set in exactly one way. The species is called ‘being a cyclically ordered set of cardinality ’: we can put a -structure on a finite set only if its cardinality is , and then a -structure on it is just a cyclic ordering.
We have
because a permutation with cycles of length on a finite set is the same as a way of chopping into subsets of cardinality and cyclically ordering each one. Thus, we have
and we just need to compute the two generating functions on the right-hand side.
The generating function of is easy to compute:
and this explains the name . The generating function of is
since there are cyclic orderings on an -element set. We have
(just integrate the geometric series) so we get
Since
we get
or simply
This is really a kind of formula for , the number of permutations of an -element set with shortest cycle of length . After all, by the definition of generating function, this equation says
Even better, the coefficient
is the probability we’re after: the probability that the shortest cycle in a randomly chosen permutation of an -element set has length .
Unfortunately, working out these coefficients is hard.
Fortunately, we just want to know the limit of these coefficients as . And for this we can use a little result from complex analysis. I’ll prove it later:
Lemma. Suppose
is a meromorphic function defined on a disc of radius centered at the origin, which is analytic on this disc except for a simple pole at . Then equals the residue of at .
If you want to understand this lemma, I urge that you consider an example: the function . The coefficients of its power series are all , and it has a pole at with residue . This is why we need to take the residue of in the lemma. In fact, proving the lemma consists of reducing the general problem to this special case.
Given this lemma, the quantity we’re trying to compute:
is the residue of the function
at the point . This function is just minus the generating function of , but I’ve changed to to emphasize that now we’re thinking of it as a function on the complex plane. It’s actually analytic everywhere except , and since has a simple pole of residue at this point, the residue of
at is just the numerator evaluated at , namely
So this number is the probability that the shortest cycle in a randomly chosen permutation of an -element set has length , in the limit.
This is beautiful, I think. And it leads immediately to another beautiful fact.
Puzzle 4. Give a simpler asymptotic formula for the above probability as .
Here we use the fact that
where is Euler’s constant. So, as , the probability we’ve just computed is
When Euler discovered his constant in his 1776 paper “On a memorable number naturally occurring in the summation of the harmonic series”, he voiced his suspicion that would be interesting… and here is some evidence that it is!
By the way, I learned about these questions here:
- Jeffrey Lagarias, Euler’s constant: Euler’s work and modern developments, Section 3.11.
They were first answered in 1952:
- Osias Gruder, Zur theorie der Zerlegung von Permutationen in Zyklen, Arkiv för Matematik 2 (1952), 385–414.
To wrap up, let me prove that lemma. It’s just a special case of a much more general useful result on the asymptotic behavior of the coefficients of a power series:
- Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, Cambridge, 2009.
But once you’ve seen the proof of this special case, it’s easy to generalize.
Lemma. Suppose
is a meromorphic function defined on a disc of radius centered at the origin, which is analytic on this disc except for a simple pole at . Then equals the residue of at .
Proof. The idea is to ‘subtract off the singularity’. We can write
where is analytic on a disc of radius and is the residue of at . If we write
then we have
for all . But the Cauchy–Hadamard theorem says that
where is the radius of convergence of , and since we have as . Thus
as was to be shown. █
Re: Random Permutations (Part 2)
Wow, this is a gorgeous application of generating functors and generating functions. It highlights the differences in the approaches and where they both shine: the functors rely on explicit bijections and looking into the process of building up the thing you’re counting (so they feel very concrete and constructive), while the functions are truly analytical objects that can be worked with complex analytically (and so they partake in the magic that is complex analysis)!