## January 11, 2020

### Random Permutations (Part 12)

#### Posted by John Baez

This time I’d like to repackage some of the results in Part 11 in a prettier way. I’ll describe the groupoid of ‘finite sets equipped with a permutation’ in terms of Young diagrams and cyclic groups. Taking groupoid cardinalities, this description will give a well-known formula for the probability that a random permutation belongs to any given conjugacy class!

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.
Posted at January 11, 2020 4:44 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3187

### Re: Random Permutations (Part 12)

A gorgeous piece of objective mathematics! As this whole series has been.

Posted by: David Jaz Myers on January 12, 2020 6:39 AM | Permalink | Reply to this

### Re: Random Permutations (Part 12)

Thanks! Too bad Ayn Rand’s brand of objectivism missed the point.

Posted by: John Baez on January 12, 2020 6:48 AM | Permalink | Reply to this

### Re: Random Permutations (Part 12)

Ha!

I’d like to try my hand at further objectifying your proof. Namely, I want to get at the term $\frac{B\mathbb{Z}/k^{y(k)}}{y(k)}$ more objectively.

I’ll work in homotopy type theory, since it’s what I know and it makes working with groupoids a breeze. So, with that in mind, we can define

${Perm} :\equiv (X : {Fin}) \times (X = X)$

to be the type of finite sets equipped with an automorphism. I’ll refer to an element of ${Perm}$ by its permutation. For $\sigma : \{1, \ldots, n\} = \{1,\ldots, n\}$, define ${Perm}_{\sigma} :\equiv {BAut}_{{Perm}}(\sigma)$ to be the type of permutations identifyable with $\sigma$. Here, I’m using the general definition ${BAut}_{X}(x) :\equiv (y : X) \times ||x = y||$ for any $x : X$ as the type of elements of $X$ which are somehow identifyable with $x$.

Just a few more definitions. Define ${B}\mathbb{Z}/k :\equiv {BAut}_{{Perm}}(+1 : \mathbb{Z}/k = \mathbb{Z}/k)$ to be the type of cyclic permutations of size $k$. Finally, for any type $G$ and $k : \mathbb{N}$ we define $\frac{G^k}{k!} :\equiv (X : {BAut}(k)) \times G^X$ to be the type of pairs consisting of a $k$-element set $X$ and an $X$-indexed tuple of elements of $G$.

Almost there – we still need to know what Young diagrams are. I’m going to define a Young diagram instead to be a function $Y : \mathbb{N}^+ \to {Fin}$ sending a positive natural number to a finite set so that the union over all $n : \mathbb{N}^+$ is finite. Then the Young diagram associated to the permutation $\sigma$ sends each positive natural $k$ to the set $Y_{\sigma}(k)$ of $k$-cycles in $\sigma$, considered as subactions of $\sigma$.

Now, we can state the result: ${Perm}_{\sigma} = (k : \mathbb{N}^+) \to (Z : {BAut}(Y_{\sigma}(k)) \times {B}\mathbb{Z}/k^{Z}.$

We can construct such an equivalence very explicitly. Given a permutation $\alpha$ identifiable with $\sigma$, and a positive $k$, we have that $Y_{\alpha}(k)$ is identifiable with $Y_{\sigma}(k)$. Given a cycle $C : Y_{\alpha}(k)$, $C$ itself is a cyclic permutation of size $k$ and therefore $C : {B}\mathbb{Z}/k$. So the map from left to write sends $\alpha$ to $k \mapsto (Y_{\alpha}(k), C \mapsto C)$.

On the other hand, suppose we have a function assigning to each positive number $k$ a set $Z_k$ of the same cardinality as $Y_{\sigma}(k)$, together with a function assigning each element $c$ of $Z_k$ a cyclic permutation $\alpha_c$. Then the disjoint union of the $\alpha_c$ over all $c$ and $k$ gives us a permutation $\alpha$. To show that this is identifiable with $\sigma$, suppose that $Z_k$ was actually $Y_{\sigma}(k)$. Then ${B}\mathbb{Z}/k^{Z_k}$ is connected, so we can assume again that the $\alpha_c$ are actually $C$ for $C : Y_{\sigma}(k)$. But $\sigma$ is the disjoint union of its cycles, so we’ve identified $\alpha$ with $\sigma$.

That these are inverse to eachother is pretty straightforward to check. If I write it in less Agda-inspired notation it now looks just like we want it: ${Perm}_{\sigma} = \prod_{k = 1}^{\infty} \frac{{B}\mathbb{Z}/k^{y(k)}}{y(k)!}.$

Posted by: David Jaz Myers on January 13, 2020 6:03 AM | Permalink | Reply to this

### Re: Random Permutations (Part 12)

Very minor notational issue: $B$ is in math italics in the first equation and in sans-serif nonitalic type later. I presume the latter is the desired convention.

Posted by: Blake Stacey on January 12, 2020 7:51 PM | Permalink | Reply to this

### Re: Random Permutations (Part 12)

Thanks! I’m trying to go with a notation where categories (and thus groupoids) are in \mathsf font, while mere sets are in \mathrm.

Posted by: John Baez on January 12, 2020 10:15 PM | Permalink | Reply to this

Post a New Comment