The n-Category Café

Here is what we’ll prove:

$$\mathsf{Perm} \simeq \sum_{y \in Y} \prod_{k=1}^\infty \frac{ \mathsf{B}(\mathbb{Z}/k)^{y(k)}}{ y(k)!}$$

Let me explain the notation here.

First, $\mathsf{Perm}$ stands for the groupoid of finite sets equipped with permutation. Explicitly:

• an object $(X,\sigma)$ of $\mathsf{Perm}$ is a finite set $X$ with a bijection $\sigma \colon X \to X$;
• a morphism $f \colon (X,\sigma) \to (X',\sigma')$ is a bijection $f \colon X \to X'$ such that $\sigma' = f \sigma f^{-1}$.

Second, $Y$ stands for the set of Young diagrams. A Young diagram looks like this:

but we will think of Young diagrams as functions $y \colon \mathbb{N}^+ \to \mathbb{N}$ that vanish at all but finitely many points. The idea is that a Young diagram $y$ has $y(k)$ columns of length $k$ for each $k = 1, 2, 3, \dots$. For example, the Young diagram above has $y(1) = 1, y(2) = 3, y(3) = 1$ and $y(n) = 0$ for all other $n$.

Third, $\mathsf{B}(G)$ stands for the one-object groupoid corresponding to the group $G$.

Fourth, for any category $\mathsf{C}$,

$$\frac{\mathsf{C}^k}{k!}$$

stands for the $k$th symmetrized power of $\mathsf{C}$. This is easiest to understand if we recall that the free symmetric monoidal category on $\mathsf{C}$, say $\mathsf{S}(\mathsf{C})$, has a description as

$$\mathsf{S}(\mathsf{C}) \simeq \sum_{k = 0}^\infty \frac{\mathsf{C}^k}{k!}$$

where an object of $\mathsf{C}^k/k!$ is a $k$-tuple $(c_1, \dots, c_k)$ of objects of $\mathsf{C}$ and a morphism is a $k$-tuple $(f_1, \dots, f_k)$ of morphisms in $\mathsf{C}$ together with a permutation $\sigma \in S_k$. The morphisms are composed in a manner familiar from the ‘wreath product’ of groups. Indeed, if $G$ is a group and $\mathsf{B}(G)$ is the corresponding one-object groupoid, we have

$$\frac{\mathsf{B}(G)^k}{k!} \simeq \mathsf{B}(S_k \ltimes G^k) \quad \quad (1)$$

where the semidirect product $S_k \ltimes G^k$ is called the wreath product of $S_k$ and $G$.

Now that all the notation is defined, we can prove the result:

Theorem. There is an equivalence of groupoids

$$\mathsf{Perm} \simeq \sum_{y \in Y} \prod_{k=1}^\infty \frac{ \mathsf{B}(\mathbb{Z}/k)^{y(k)}}{ y(k)!}$$

Proof. First note that $\mathsf{Perm}$ is equivalent to its full subcategory where we use one finite set with each cardinality. It is thus equivalent to the groupoid where

• an object is a natural number $n$ and an element $\sigma \in S_n$,
• a morphism $f \colon (n,\sigma) \to (n, \sigma')$ is a permutation $f \in S_n$ such that $\sigma' = f \sigma f^{-1}$.

Thus, isomorphism classes of objects in $\mathsf{Perm}$ correspond to conjugacy classes of permutations. A conjugacy class of permutations is classified by its number of cycles of each length, and thus by a Young diagram $y \colon \mathbb{N}^+ \to \mathbb{N}$ saying that there are $y(k)$ cycles of length $k$ for each $k = 1, 2, 3, \dots$.

In short, if we use $\pi_0(G)$ to stand for the set of isomorphism classes of objects of the groupoid $G$, we have established an isomorphism

$$\pi_0(\mathsf{Perm}) \cong Y$$

where $Y$ is the set of Young diagrams. The groupoid $\mathsf{Perm}$ is thus equivalent to a coproduct of connected groupoids, one for each Young diagram:

$$\mathsf{Perm} \simeq \sum_{y \in Y} \mathsf{Perm}_y$$

By taking a skeleton we can assume each groupoid $\mathsf{Perm}_y$ has one object, namely $(n,\sigma)$ where $\sigma \in S_n$ is a chosen permutation with $y(k)$ cycles of length $k$ for each $k = 1, 2, 3, \dots$. The automorphisms of this object are then permutations $f \in S_n$ with $\sigma = f \sigma f^{-1}$.

In short, $\mathsf{Perm}_y$ is the one-object groupoid corresponding to the centralizer of $\sigma \in S_n$, where $\sigma$ is any permutation with $y(k)$ cycles of length $k$ for all $k$.

We can choose $\sigma$ to act on the boxes of the Young diagram $y$, cyclically permuting the entries in each column in such a way that the first entry in each column is mapped to the second, the second is mapped to the third, and so on, with the last entry being mapped to the first. Any element of the centralizer of $\sigma$ thus consists of a permutation of the columns, mapping each column to some other column of the same height, followed by an arbitrary cyclic permutation of the entries in each column. It follows that the centralizer is isomorphic to

$$\prod_{k=1}^\infty S_{y(k)} \ltimes (\mathbb{Z}/k)^{y(k)}$$

so

$$\mathsf{Perm}_y \simeq \mathsf{B} \left( \prod_{k=1}^\infty S_{y(k)} \ltimes (\mathbb{Z}/k)^{y(k)} \right)$$

Then, by equation (1) and the fact that $\mathsf{B} \colon \mathsf{Gp} \to \mathsf{Gpd}$ preserves products, we have

$$\begin{array}{ccl} \mathsf{Perm}_y &\simeq& \displaystyle{ \prod_{k=1}^\infty \mathsf{B} \left( S_{y(k)} \ltimes (\mathbb{Z}/k)^{y(k)} \right) } \\ \\ &\simeq & \displaystyle{ \prod_{k=1}^\infty \frac{ \mathsf{B}(\mathbb{Z}/k)^{y(k)}}{ y(k)!} } \end{array}$$

It follows that

$$\begin{array}{ccl} \mathsf{Perm} &\simeq & \displaystyle{ \sum_{y \in Y} \mathsf{Perm}_y } \\ \\ &\simeq& \displaystyle{ \sum_{y \in Y} \prod_{k=1}^\infty \frac{ \mathsf{B}(\mathbb{Z}/k)^{y(k)}}{ y(k)!} } \end{array}$$

as desired.   ■

Now let’s see how this result lets us compute the probability that a random permutation of an $n$-element set lies in any given conjugacy class. The conjugacy classes in $S_n$ correspond to Young diagrams $y$ with $n$ boxes. For each such $y$ we will compute the probability that a random element of $S_n$ lies in the corresponding conjugacy class. Let’s call this probability $p_y$.

In general, the probability that a randomly chosen element of a finite group $G$ lies in some conjugacy class $K$ is $|K|/|G|$. But $K \cong G/C(k)$ where $C(k)$ is the centralizer of some element $k \in K$. Thus, the probability in question equals $1/|C(k)|$.

Recall that $\mathsf{Perm}_y$ is one-object groupoid corresponding to the centralizer of some $\sigma \in S_n$ whose conjugacy class corresponds to the Young diagram $y$. The cardinality of a one-object groupoid is the reciprocal of the cardinality of the corresponding group, so

$$|\mathsf{Perm}_y| = \frac{1}{|C(\sigma)|}$$

It follows that

$$p_y = |\mathsf{Perm}_y|$$

In other words, the probability we are trying to compute is the cardinality of a groupoid we have already studied! We saw in the proof of the Theorem that

$$\mathsf{Perm}_y \simeq \mathsf{B} \left( \prod_{k=1}^\infty S_{y(k)} \ltimes (\mathbb{Z}/k)^{y(k)} \right)$$

so

$$\begin{array}{ccl} p_y &=& |\mathsf{Perm}_y| \\ \\ &=& \displaystyle{ \prod_{k=1}^\infty \frac{1}{|S_{y(k)} \ltimes (\mathbb{Z}/k)^{y(k)}| } } \\ \\ &=& \displaystyle{ \prod_{k=1}^\infty \frac{1}{y(k)! \, k^{y(k)} } } \end{array}$$

So, we get a well-known result:

Theorem. The probability $p_y$ that a random permutation of an $n$-element set has $y(k)$ cycles of length $k$ for all $k = 1, 2, 3, \dots$ is given by

$$p_y = \prod_{k=1}^\infty \frac{1}{y(k)! \, k^{y(k)}}$$

The theorem is easy to prove, so the point is just that this probability is the cardinality of a naturally defined groupoid, and a similar formula holds at the level of groupoids:

$$\mathsf{Perm}_y \simeq \prod_{k=1}^\infty \frac{ \mathsf{B}(\mathbb{Z}/k)^{y(k)}}{ y(k)!}$$

---

Here is the series so far, on my website:

• Part 0 — What’s the average length of the longest cycle in a random permutation of an $n$-element set?
• Part 1 — What is the probability that a randomly chosen permutation of an $n$-element set has exactly $k$ fixed points?
• Part 2 — What is the probability that the shortest cycle in a randomly chosen permutation of an $n$-element set has length greater than $k$?
• Part 3 — A large collection of questions about random permutations, with answers.
• Part 4 — What is the probability that a randomly chosen permutation of an $n$-element set has a cycle of length greater than $n/2$?
• Part 5 — What is the average length of a cycle in a randomly chosen permutation of an $n$-element set?
• Part 6 — What expected number of cycles of length $k$ in a randomly chosen permutation of an $n$-element set?
• Part 7 — How is the distribution of the number of cycles of length $k$ in a random permutation related to a Poisson distribution?
• Part 8 — What’s the $n$th moment of a Poisson distribution?
• Part 9 — If we treat the number of cycles of length $k$ in a random permutation of an $n$-element set as a random variable, what do the moments of this random variable approach as $n \to \infty$?
• Part 10 — How to compute statistics of random permutations using groupoid cardinalities.
• Part 11 — How to prove the Cycle Length Lemma, a fundamental result on random permutations, using groupoid cardinalities.
• Part 12 — How to write the groupoid of finite sets equipped with a permutation as a sum over Young diagrams, and how to use this to compute the probability that a random permutation has given cycle lengths.