The n-Category Café

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.