### Random Permutations (Part 6)

#### Posted by John Baez

Now I’ll tackle a really fundamental question about random permutations — one whose answer will quickly deliver the solutions to many others!

**Puzzle 7.** What is the expected number of cycles of length $k$ in a random permutation of an $n$-element set?

The answer is beautiful: it’s $1/k$. More precisely, this holds whenever the question is reasonable, meaning $1 \le k \le n$.

Note that this answer passes a simple sanity check. If on average there’s $1$ cycle of length $1$, $1/2$ cycles of length $2$, and so on, the average number of elements in our $n$-element set must be

$1 \cdot 1 + \frac{1}{2} \cdot 2 + \cdots + \frac{1}{n} \cdot n = n$

Whew!

Before we show the expected number of cycles of length $k$ in a random permutation of an $n$-element set is $1/k$, let’s see how knowing this lets us answer some other questions we’ve met.

- What’s the expected number of fixed points of a random permutation?

Since a fixed point is a cycle of length $1$, the answer is $1$. We’ve already seen this in Part 1. There we got it the hard way, by computing the probability that a permutation has $k$ fixed points. But I hinted that there’s a much easier way. Here it is: since the probability that a random permutation of an $n$-element set fixes any given point is $1/n$, the expected number of fixed points is $n \cdot \frac{1}{n} = 1$.

- What’s the probability that a random permutation of an $n$-element set has a cycle of length $k$, assuming $k \gt n/2$?

Since $k$ is more than $n/2$, there can be at most one cycle of length $k$. Thus, the probability that such a cycle exists equals the expected number of such cycles! So, the probability must be $1/k$. We already saw this in Part 4. Now we’re seeing a nice way to generalize this fact to $k \le n/2$, not by asking whether a cycle of length $k$ *exists*, but by asking the *expected number* of such cycles.

- What is the expected number of cycles in a random permutation of an $n$-element set?

This was Puzzle 5 in Part 3. Since the expected number of cycles of length $k$ is $1/k$, we can sum over $k = 1, \dots, n$ and get the answer:

$\frac{1}{1} + \cdots + \frac{1}{n}$

Asymptotically this is $\ln n$. Or, even better, it’s $\ln n + \gamma$ plus a correction that goes to zero as $n \to \infty$.

- If we choose an element of an $n$-element set and random permutation of this set, what is the probability that the element lies in a cycle of length $k$?

This was Puzzle 8 of Part 3. Now I’m telling you that the expected number of cycles of length $k$ is $1/k$. Since each contains $k$ elements, the expected number of elements of our set lying on cycles of length $k$ is $k \cdot \frac{1}{k} = 1$. So, the probability that any element lies on a cycle of length $k$ is $1/n$. It’s cool how this is independent of $k$.

Okay, I hope you’re convinced by now that computing the expected number of cycles of length $k$ in a random permutation of an $n$-element set is the key to understanding many things. Let’s do it!

Flajolet and Sedgewick do this using bivariate generating functions in Example III.9 of their book *Analytic Combinatorics*. I explained the basic method last time so now I’ll just use it.

We start by making up a functor

$H_k \colon S \times \mathbb{N} \to FinSet$

that assigns to the pair $(n,i)$ the set $H_k(n,i)$ of all permutations of $n$ having exactly $i$ cycles of length $k$. Note that $n$ here is being treated as a finite set, while $i$ and $k$ are just numbers.

The generating function of $H_k$ is defined by

$\displaystyle{ |H_k|(z,u) = \sum_{n \ge 0} \sum_{i \ge 0} |H_k(n,i)| \, \frac{z^n}{n!} u^i }$

Suppose we could compute this. How could we use this to answer our puzzle?

We want the *expected* number of cycles of length $k$ in a permutation of an $n$-element set. Since the probability that a random permutation has $i$ cycles of length $k$ is

$\frac{|H_k(n,i)|}{n!}$

this expected number is

$\sum_{i \ge 0} i \frac{|H_k(n,i)|}{n!}$

So this is the sum we need to compute.

But notice,

$\begin{array}{ccl} \displaystyle{ \left. \frac{\partial}{\partial u} |H_k|(z,u) \,\right|_{u=1} } &=& \displaystyle{ \left. \frac{\partial}{\partial u} \sum_{n \ge 0} \sum_{i \ge 0} |H_k(n,i)| \, \frac{z^n}{n!} u^i \; \right|_{u=1} } \\ \\ &=& \displaystyle{ \sum_{n \ge 0} \sum_{i \ge 0} i |H_k(n,i)| \, \frac{z^n}{n!} } \\ \\ \end{array}$

So, the expected number we want is the coefficient of $z^n$ in the power series for

$\left. \frac{\partial}{\partial u} |H_k|(z,u) \,\right|_{u=1}$

Thus, to answer our puzzle, we should figure out $|H_k|(z,u)$, differentiate it with respect to $u$, set $u = 1$, and read off the coefficient of $z^n$.

For this, we’ll need a formula for $H_k$:

$H_k \cong Exp \circ (Cyc_{\ne k} + U \cdot Cyc_k)$

Let’s see what this means! As soon as you understand what it means, you’ll know it’s true. That happens a lot in category theory.

Here $Cyc_k \colon S \to FinSet$ is the species ‘being a cyclically ordered $k$-element set’. We’ve already met the species

$Cyc \cong \sum_{i \ge 0} Cyc_i$

which is ‘being a cyclically ordered finite set’, and now we’ll define a species

$Cyc_{\ne k} \cong \sum_{i \ne k} Cyc_i$

which is ‘being a cyclically ordered finite set of cardinality $\ne k$’. All these species can be seen as functors from $S \times \mathbb{N}$ to $FinSet$ that don’t involve the second variable.

On the other hand, we have a functor

$U \colon \mathbb{N} \to FinSet$

called ‘being the number 1’. This is defined by setting $U(1) = 1$ and $U(i) = \emptyset$ for all $i \ne 1$. This can be seen as a functor from $S \times \mathbb{N}$ to $FinSet$ that doesn’t involve the *first* variable.

It’s a bit hard for me to describe the functor

$Cyc_{\ne k} + U \cdot Cyc_k$

in plain English, mainly because I haven’t developed a vocabulary for functors $S \times \mathbb{N} \to FinSet$ the way I have for species! A species describes a type of structure you can put on a finite set; one of these functors describes a type of structure you can put on a finite set and a natural number. This one is ‘either your finite set is cyclically ordered and not of cardinality $k$ and your number is $0$, or it’s cyclically ordered and of cardinality $k$ and your number is $1$’.

As a consequence

$Exp \circ (Cyc_{\ne k} + U \cdot Cyc_k)$

describes the following sort of structure on a finite set and a natural number. This structure is a way to chop the finite set into cyclically ordered pieces *and simultaneously write the number as sum of $0$’s and $1$’s*, but using a $1$ for each piece of cardinality $k$, and a $0$ for every other piece. This is why we get

$Exp \circ (Cyc_{\ne k} + U \cdot Cyc_k) \cong H_k$

where $H_k(n,i)$ is the set of all permutations of the set $n$ having exactly $i$ cycles of length $k$.

That’s my best attempt at a purely verbal explanation of this isomorphism. Now let’s exploit it: it gives an equation between generating functions

$|H_k| = exp \circ (|Cyc_{\ne k}| + |U| \cdot |Cyc_k|)$

which will let us compute $|H_k|$.

To proceed, notice that

$|Cyc_k| = \frac{(k-1)!}{k!} z^k = \frac{z^k}{k}$

since there are $(k-1)!$ ways to cyclically order a $k$-element set. Similarly,

$\begin{array}{ccl} |Cyc_{\ne k}| &=& \displaystyle{ \sum_{i \ne k} \frac{z^i}{i} } \\ \\ &=& \displaystyle{ \ln\left(\frac{1}{1-z}\right) - \frac{z^k}{k} } \end{array}$

The whole point of $U$ is that

$|U| = u$

So, we get

$| Cyc_{\ne k} + U \cdot Cyc_k | = \ln\left(\frac{1}{1-z}\right) + (u-1) \frac{z^k}{k}$

In other words, this generating function is like that of $Cyc$, the species of cyclic orderings:

$|Cyc| = \ln \left( \frac{1}{1-z} \right)$

except that we’ve yanked out the $z^k/k$ term and stuck it back in multiplied by $u$. That’s why it pays special attention to cycles of length $k$.

From this we get

$\begin{array}{ccl} |H_k| &=& \exp \circ (|Cyc_{\ne k}| + |U| \cdot |Cyc_k|) \\ \\ &=& \displaystyle{ \exp \left( \ln \left( \frac{1}{1-z} \right) + (u-1) \frac{z^k}{k} \right) } \\ \\ &=& \displaystyle{ \frac{e^{(u-1)z^k/k}}{1-z} } \end{array}$

Now to answer our puzzle we differentiate this with respect to $u$, set $u = 1$, and read off the coefficient of $z^n$. That’ll be the expected number of cycles of length $k$ in a random permutation of an $n$-element set!

Here we go:

$\begin{array}{ccl} \displaystyle{ \left. \frac{\partial}{\partial u} |H_k|(z,u) \,\right|_{u=1} } &=& \displaystyle{ \left. \frac{\partial}{\partial u} \frac{e^{(u-1)z^k/k}}{1-z} \right|_{u=1} } \\ \\ &=& \displaystyle{ \frac{z^k/k}{1-z} } \\ \\ &=& \displaystyle{ \frac{z^k}{k} + \frac{z^{k+1}}{k} + \frac{z^{k+1}}{k} + \cdots } \end{array}$

As long as $n \ge k$, the coefficient of $z^n$ in this power series is $1/k$. But of course, we need $k \ge 1$ for this whole calculation to make sense.

So whenever $1 \le k \le n$, the expected number of cycles of length $k$ in a random permutation of an $n$-element set is $1/k$. It’s a little jewel of mathematics.

## Re: Random Permutations (Part 6)

You rhetorically asked:

…and answered…

That

isbeautiful!Another way to say it is this: in a random permutation of an $n$-element set, the expected number of $k$-periodic points is $1$.

Do you know of any direct way of seeing that the expected number of $k$-periodic points in a permutation of $n$ elements should be independent of $n$, for $n \geq k$?

E.g. why should the expected number of 3-periodic points in a permutation of 10 elements be the same as in a permutation of 100 elements?

For some reason this is reminding me of Barbier’s beautiful solution of the Buffon needle problem. But if I could put my finger on why, I could answer my own question!