|
|
|
|
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:
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
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)!} \]You can also read comments on the n-Category Café, and make your own comments or ask questions there!
|
|
|
|