Skip to main content

Section 1.8 The symmetric group \(S_n\)

Many of the concepts that we just studied abstractly become alive when we study the symmetric group \(S_n\text{,}\) which is the group of permutations of \(n\) elements. Everything becomes clear and explicit, since we kind of all known intuitively how permutations work.

Subsection 1.8.1 Cayley's theorem

But in fact studying the symmetric group \(S_n\) is fundamental, because of what is known as Cayley's theorem, which basically states that any finite group \(G\) of order \(n\) is isomorphic (that is, identical as abstract group) to a subgroup of the symmetric group \(S_n\text{.}\) More precisely, the statement of Cayley's theorem is that \(G\) is a subgroup of the group of permutations of the elements of \(G\text{,}\) which is \(S_n\) since \(G\) has order \(n\text{.}\) So from this point of view, studying symmetric groups and their subgroups basically means studying all finite groups.

Cayley's theorem is quite deep, since it says that we can realize any abstract finite group as a subgroup of a permutation group. In other words, it connects abstract group theory to the very concrete world of permutations. Isn't it cool? As we will see, Cayley's theorem gives an example of a nice representation which exists for all finite groups, and is called the regular representation.

Why is Cayley's theorem true? Without going through a formal proof, let us see how it goes. Consider the multiplication table of a finite group \(G = \{g_1, \ldots, g_n \}\text{.}\) The \(i\)'th row of the table is given by the elements \(\{ g_i g_1, \ldots, g_i g_n \}\text{.}\) By the Rearrangement Theorem Theorem 1.4.2, this is the same set of elements as \(G\text{,}\) but in a different order. Thus we can assign to the \(i\)'th row an element of the permutation group of \(n\) elements, that is an element of \(S_n\text{,}\) which acts as \(\{ g_1, \ldots, g_n \} \mapsto \{g_i g_1, \ldots, g_i g_n\}\text{.}\) As a result, to every element \(g_i \in G\) we can assign a permutation \(s_i \in S_n\text{;}\) we have constructed a map from \(G\) to a subgroup of \(S_n\text{,}\) and one can show that this map is a group isomorphism. This is the essence of Cayley's theorem.

As an example, consider the group of three elements \(G = \mathbb{Z}_3\) with multiplication table Table 1.4.5. We see that the map assigns to the element \(e \in G\) the identity permutation \(e \in S_3\text{;}\) to \(a \in G\) it assigns the cyclic permutation \(1 \mapsto 2, 2 \mapsto 3, 3 \mapsto 1\) in \(S_3\text{;}\) and to \(b \in G\) it assigns the cyclic permutation \(1 \mapsto 3, 2 \mapsto 1, 3 \mapsto 2\text{.}\) Thus we have identified \(G = \mathbb{Z}_3\) with the alternating subgroup \(A_3 \subset S_3\) consisting of even permutations.

Subsection 1.8.2 Notation

Now let us study the symmetric group \(S_n\) in more detail. First we introduce standard notation. An element of \(S_n\) corresponds to a permutation of \(n\) elements. It is customary to denote it by its action on the \(n\) elements \(\{1, \ldots, n \}\text{.}\) For instance, the cyclic rotation of the \(n\) elements, which takes 1 to 2, 2 to 3, etc., would be denoted by

\begin{equation*} \pi = \begin{pmatrix} 1 \amp 2 \amp \cdots \amp n-1 \amp n \\ 2 \amp 3 \amp \cdots \amp n \amp 1 \end{pmatrix}. \end{equation*}

Generically, a permutation \(\pi\) that takes \(1\) to \(\pi(1)\text{,}\) \(2\) to \(\pi(2)\text{,}\) and so on, would be denoted by

\begin{equation*} \pi = \begin{pmatrix} 1 \amp 2 \amp \cdots \amp n-1 \amp n \\ \pi(1) \amp \pi(2) \amp \cdots \amp \pi(n-1) \amp \pi(n) \end{pmatrix}. \end{equation*}

As an example, consider \(S_3\text{.}\) It has \(3! = 6\) elements; the identity permutation (\(\pi_1\)), three permutations corresponding to a single exchange of two elements (\(\pi_2,\pi_3,\pi_4\)), and two permutations that permute the three elements (\(\pi_5, \pi_6\)). In the notation introduced above, the six elements are

\begin{align*} e = \pi_1 = \begin{pmatrix} 1 \amp 2 \amp 3\\1 \amp 2 \amp 3 \end{pmatrix}, \qquad \pi_2 = \begin{pmatrix} 1 \amp 2 \amp 3\\2 \amp 1 \amp 3 \end{pmatrix},\qquad \pi_3 = \begin{pmatrix} 1 \amp 2 \amp 3\\3 \amp 2 \amp 1 \end{pmatrix},\\ \pi_4 = \begin{pmatrix} 1 \amp 2 \amp 3\\1 \amp 3 \amp 2 \end{pmatrix}, \qquad \pi_5 = \begin{pmatrix} 1 \amp 2 \amp 3\\3 \amp 1 \amp 2 \end{pmatrix}, \qquad \pi_6 = \begin{pmatrix} 1 \amp 2 \amp 3\\2 \amp 3 \amp 1 \end{pmatrix}. \end{align*}

To construct the multiplication table for \(S_3\text{,}\) we need to multiply elements in \(S_3\text{,}\) where by multiplication here we mean composition of permutations. For instance, the composition \(\pi_4 \circ \pi_5\) can be constructed as follows. Start with \(\pi_5\text{;}\) it takes \(1 \mapsto 3, 2 \mapsto 1, 3 \mapsto 2\text{.}\) Then, combining with the action of \(\pi_4\text{,}\) we get \(1 \mapsto 3 \mapsto 2\text{,}\) \(2 \mapsto 1 \mapsto 1\text{,}\) and \(3 \mapsto 2 \mapsto 3\text{,}\) which is \(\pi_2\text{.}\) Therefore, \(\pi_4 \circ \pi_5 = \pi_2\text{.}\)

In fact, we see explicitly that \(S_3\) is non-Abelian. Consider \(\pi_5 \circ \pi_4\text{.}\) We obtain \(1 \mapsto 1 \mapsto 3\text{,}\) \(2 \mapsto 3 \mapsto 2\) and \(3 \mapsto 2 \mapsto 1\text{,}\) which is \(\pi_3\text{.}\) Therefore \(\pi_5 \circ \pi_4 = \pi_3\text{,}\) hence \(\pi_4 \circ \pi_5 \neq \pi_5 \circ \pi_4\text{.}\)

Subsection 1.8.3 Cycles

Since we are dealing with permutations of set of \(n\) elements, it is clear that after applying a given permutation a certain number of times, we will come back to the initial elements. In other words, consider for instance the element \(1\text{.}\) A given permutation \(\pi\) will take \(1 \to \pi(1)\text{.}\) Applying it again, we will get \(1 \to \pi(1) \to \pi(\pi(1))\text{.}\) After a number of application, say \(r\text{,}\) we will necessarily get back \(\pi^r(1) = 1\text{.}\) The numbers \(1, \pi(1), \pi^2(1), \ldots, \pi^{r-1}(1)\text{,}\) that are reached from \(1\) by \(\pi\) form what we call a “cycle”. More precisely:

Definition 1.8.3. Cycle.

Let \(\pi \in S_n\text{,}\) \(i \in \{1, \ldots, n\}\) and let \(r\) be the smallest positive integer such that \(\pi^r(i) = i\text{.}\) Then the set of \(r\) distinct elements \(\{\pi^k(i) \}_{k=0}^{r-1}\) is called a cycle of \(\pi\) of length \(r\text{,}\) or an \(r\)-cycle generated by \(i\). We denote a given cycle by \((i~ \pi(i)~ \ldots~ \pi^{r-1}(i) )\text{.}\)

It is clear that a given permutation \(\pi\) breaks up the set of \(n\) elements \(\{1,\ldots,n\}\) into disjoint cycles. We can then denote the permutation \(\pi\) by the cycle decomposition of \(\{1,\ldots,n\}\) that it implies.

Consider the permutation \(\pi_5\) for \(S_3\) as in the previous example. Start with \(1\text{.}\) Then \(\pi_5(1) = 3\text{,}\) \(\pi_5^2(1) = \pi_5(3) = 2\text{,}\) and \(\pi_5^3(1) = \pi_5(2) = 1\text{.}\) Thus \(\pi_5\) decomposes \(\{1,2,3\}\) into a single cycle of length \(3\text{.}\) In cycle notation, we write \(\pi_5 = (132)\text{.}\) We could have written \(\pi_5 = (321)\) or \(\pi_5 = (213)\) as well; those are the same permutations. In this notation the numbers defining the cycles can be moved around cyclically without changing anything. Similarly, \(\pi_6\text{,}\) which is the other permutation that exchanges the three elements, has cycle decomposition \(\pi_6 = (123)\text{.}\)

Consider instead the permutation \(\pi_2\text{.}\) Start with \(1\text{.}\) Then \(\pi_2(1) = 2\text{,}\) and \(\pi_2^2(1) = \pi_2(2) = 1\text{.}\) Thus \(1\) generates a \(2\)-cycle given by \((12)\text{.}\) There is another cycle however. Start with \(3\text{.}\) Then \(\pi_2(3)=3\text{,}\) hence \(3\) generates a \(1\)-cycle given by \((3)\text{.}\) Therefore, the set of three elements is broken up into two cycles by \(\pi_2\text{,}\) that is \(\pi_2 = (12)(3)\text{.}\) Similarly, we get \(\pi_3= (13)(2)\text{,}\) \(\pi_4 = (1)(23)\text{,}\) and \(\pi_1=(1)(2)(3)\text{.}\)

With the notion of cycles we can define permutations that are “cyclic”:

Definition 1.8.5. Cyclic permutations.

If \(\pi \in S_n\) has a cycle of length \(r\) and all other cycles of \(\pi\) have only one element, then \(\pi\) is called a cyclic permutation of length \(r\).

In the example of \(S_3\text{,}\) we then have that \(\pi_5\) and \(\pi_6\) are cyclic permutations of length \(3\text{,}\) while \(\pi_2,\pi_3,\pi_4\) are cyclic permutations of length \(2\text{.}\) Thus in \(S_3\) all permutations are cyclic. But for instance in \(S_4\text{,}\) we have the permutation \(\pi = (12)(34)\text{,}\) which is not cyclic.

A particularly useful type of cyclic permutation is of length two:

Definition 1.8.7. Transposition.

A cyclic permutation of length \(2\) (i.e. a permutation that only exchanges two elements) is called a transposition.

To come back to \(S_3\text{,}\) there are three transpositions, namely \(\pi_2, \pi_3\) and \(\pi_4\text{.}\)

Now that we understand cycles, we can easily compute composition of permutations. Given two permutations \(\pi_1\) and \(\pi_2\text{,}\) the composition \(\pi_1 \circ \pi_2\) can be computed easily by “multiplying cycles”.

This is easier understood in terms of an example. Consider the product of cycles \((15)(234)(253)\) in \(S_5\text{.}\) To find the corresponding permutation, we consider each element of \(\{1,\ldots,5 \}\text{,}\) and, starting from the far right of the product of cycles, we keep track of what the element becomes under the action of the cycles. In our case, consider first \(1\text{.}\) The first two cycles on the right leave it invariant, while the last cycle sends its to \(5\text{.}\) Thus \(1 \to 5\text{.}\) Consider \(2\text{.}\) The first cycle sends it to \(5\text{,}\) the second cycle then leaves \(5\) invariant, and then the last cycle sends it to \(1\text{.}\) Thus \(2 \to 1\text{.}\) Consider \(3\text{.}\) Then we get \(3 \to 2 \to 3 \to 3\text{.}\) Consider \(4\text{.}\) We get \(4 \to 4 \to 2 \to 2\text{.}\) Finally, for \(5\) we get \(5 \to 3 \to 4 \to 4\text{.}\) The corresponding permutation is then:

\begin{equation*} \pi = \begin{pmatrix} 1 \amp 2 \amp 3 \amp 4 \amp 5\\ 5 \amp 1 \amp 3 \amp 2 \amp 4 \end{pmatrix}. \end{equation*}

(A consistency check here is that each number \(1\) to \(5\) only appear once in the final result of the permutation, which must be the case.) Equivalently, we can write the resulting permutation in terms of its cycle structure, which is \(\pi=(1542)(3)\text{.}\) Hence we get that

\begin{equation*} (15)(234)(253)=(1542)(3). \end{equation*}

This is how we multiply cycles.

Let us just show in an example that multiplication of cycles and composition of permutations are equivalent. Consider \(\pi_1 = (123)(45)\) and \(\pi_2 = (1)(2)(345)\) in \(S_5\text{.}\) Suppose that we want to compute the composition \(\pi_1 \circ \pi_2\text{.}\) The resulting permutation is easily calculated to be

\begin{equation*} \pi_1 \circ \pi_2=\begin{pmatrix} 1 \amp 2 \amp 3 \amp 4 \amp 5\\ 2 \amp3 \amp 5 \amp 4 \amp 1 \end{pmatrix}. \end{equation*}

We claim that this is equivalent to the product of cycles \((123)(45)(1)(2)(345)\text{.}\) When we consider products of cycles, we can remove cycles of length \(1\text{,}\) since they do not do anything in the product. So we want to compute \((123)(45)(345)\text{.}\) Under this product, we have \(1 \to 1 \to 1 \to 2\text{,}\) \(2 \to 2 \to 2 \to 3\text{,}\) \(3 \to 4 \to 5 \to 5\text{,}\) \(4 \to 5 \to 4 \to 4\text{,}\) \(5 \to 3 \to 3 \to 1\text{,}\) which is indeed the permutation above. In fact, a few minutes of thought will make it clear that the way we defined products of cycles is precisely equivalent to composition of the corresponding permutations.

A very interesting result for the symmetric group is that any permutation can in fact be written as the product of a number of transpositions. This is just saying that every permutation can be done in steps, where in each step we only exchange two objects. Let's see how it goes. We start by studying how a cycle can be written as a product of transpositions:

The proof simply involves multiplying the transpositions on the RHS. Start with \(i_1\text{.}\) Under the product of transpositions, we get \(i_1 \to i_2 \to \ldots \to i_2\text{.}\) Consider \(i_2\text{:}\) we get \(i_2 \to i_1 \to i_3 \to \ldots \to i_3\text{.}\) Iterating, we get that \(i_k \to i_{k+1}\) for all \(k=1,\ldots,r-1\text{,}\) and \(i_r \to i_1\text{.}\) Thus the resulting permutation is the cyclic permutation of length \(r\) that has cycle structure \((i_1 i_2 \ldots i_r)\text{.}\)

Definition 1.8.11. Parity.

We define the parity of the cycle as being even if the number of transpositions in the decomposition is even, and odd if the number if transpositions is odd. Note that even though the decomposition is not unique, the parity of the decomposition is uniquely defined.

We can then apply these results to permutations themselves, not just to individual cycles. We obtain:

In fact, the parity of a permutation can be determined directly from its cycle structure, without having to work out its decomposition into transpositions, since each \(r\)-cycle can always be decomposed into the product of \(r-1\) transpositions.

As an example, consider the permutation \(\pi=(145)(23)(6)\) in \(S_6\text{.}\) Looking at the cycle structure, the \(3\)-cycle is even (can be decomposed into two transpositions), the \(2\)-cycle is of course odd (it is a transposition itself), and the \(1\)-cycle does not contribute to the parity. Thus \(\pi\) is odd, since \(2+1=3\text{.}\) In fact, a decomposition is easy to find following Proposition 1.8.10. We get:

\begin{equation*} \pi = (15)(14)(23)(6). \end{equation*}

Of course, this decomposition is not unique (for instance \((15)(14)(24)(24)(23)(6)\) would also work), but its parity is uniquely defined.

Definition 1.8.14. The alternating group.

The set of even permutations of \(n\) elements is denoted by \(A_n\) and is called the alternating group.

Clearly, \(A_n\) is a subgroup of \(S_n\text{,}\) since the product of two even permutations is even, it contains the identity, and the inverse of an even permutation is also even.

Subsection 1.8.4 Conjugacy classes

Now let us study conjugacy classes of \(S_n\text{.}\) Recall that conjugacy classes are defined as being subsets of elements that are conjugate to each other, where two elements \(x,y \in G\) are conjugate if \(y = g x g^{-1}\) for some \(g \in G\text{.}\)

The main result for \(S_n\) is the following theorem:

To clarify the notation, if we go back to \(S_3\text{,}\) then the three permuations \((12)(3)\text{,}\) \((13)(2)\) and \((1)(23)\) have the same cycle structure, hence are conjugate. The two permutations \((123)\) and \((132)\) are then also conjugate, and the identity permutation \((1)(2)(3)\) is of course only conjugate to itself. Thus there are three conjugacy classes in \(S_3\text{.}\)

We will only show that conjugate permutations have the same cycle structure, and leave the other direction as an exercise. Consider two permutations \(\pi, \sigma \in S_n\text{.}\) We want to check whether \(\sigma \circ \pi \circ \sigma^{-1}\) has the same cycle structure as \(\pi\text{.}\) If \(\pi\) and \(\sigma\) are given by the permutations:

\begin{equation*} \pi = \begin{pmatrix} 1 \amp 2 \amp \ldots \amp n \\ \pi(1) \amp \pi(2) \amp \ldots \amp \pi(n) \end{pmatrix}, \qquad \sigma = \begin{pmatrix} 1 \amp 2 \amp \ldots \amp n \\ \sigma(1) \amp \sigma(2) \amp \ldots \amp \sigma(n) \end{pmatrix}, \end{equation*}

then it follows that

\begin{equation*} \sigma \circ \pi \circ \sigma^{-1} = \begin{pmatrix} \sigma(1) \amp \sigma(2) \amp \ldots \amp \sigma(n) \\ \sigma(\pi(1)) \amp \sigma(\pi(2)) \amp \ldots \amp \sigma(\pi(n)), \end{pmatrix}, \end{equation*}

since \(\sigma^{-1}\) takes the element \(\sigma(i)\) and sends it to \(i\text{.}\) Thus we can see the permutation \(\sigma \circ \pi \circ \sigma^{-1}\) as applying \(\sigma\) to the symbols in the cycle decomposition of \(\pi\text{.}\) The result will generally be different from \(\pi\text{,}\) but its cycle structure will necessarily be the same.

The argument may become clearer with a simple example. Consider \(\pi=(123)(4) \in S_4\text{,}\) and \(\sigma = (12)(34) \in S_4\text{.}\) The corresponding permutations are

\begin{equation*} \pi = \begin{pmatrix} 1 \amp 2 \amp 3 \amp 4 \\ 2 \amp 3 \amp 1 \amp 4 \end{pmatrix}, \qquad \sigma = \begin{pmatrix} 1 \amp 2 \amp 3 \amp 4 \\ 2 \amp 1 \amp 4 \amp 3 \end{pmatrix}. \end{equation*}

The conjugate permutation is then

\begin{equation*} \sigma \circ \pi \circ \sigma^{-1} = \begin{pmatrix} 2 \amp 1 \amp 4 \amp 3 \\ 1 \amp 4 \amp 2 \amp 3 \end{pmatrix}, \end{equation*}

which has cycle structure \(\sigma \circ \pi \circ \sigma^{-1} = (2 1 4)(3)\text{.}\) It is indeed the same cycle structure as \(\pi\text{.}\) In fact, it could have been obtained directly by simply applying \(\sigma\) to the symbols in the cycle decomposition \(\pi = (123)(4)\text{,}\) which gives directly \(\sigma \circ \pi \circ \sigma^{-1} = (2 1 4)(3)\text{.}\)

It follows from Theorem 1.8.15 that all one has to do to find the conjugacy classes in \(S_n\) is to construct the possible cycle structures. This in turn is equivalent to partitioning the set \(\{1,\ldots,n \}\) into disjoint subsets of various lengths. What we now show is that this problem can be reformulated into the problem of finding integer partitions of the positive integer \(n\text{.}\)

Consider a permutation \(\pi \in S_n\) and its cycle decomposition. Let \(\nu_k\) be the number of \(k\)-cycles in its decomposition. We introduce a new notation which gives the cycle structure of the permutation (i.e. the number of cycles of each length): we write \((1^{\nu_1}, 2^{\nu_2}, \ldots, n^{\nu_n})\) to denote that the cycle decomposition of \(\pi\) has \(\nu_1\) cycles of length \(1\text{,}\) \(\nu_2\) cycles of length \(2\text{,}\) and so on.

The total number of elements in the cycle decomposition must of course be \(n\text{.}\) This means that the sum \(\sum_{k=1}^n k \nu_k = n\text{.}\) We can rewrite this sum as:

\begin{equation*} (\nu_1 + \nu_2 + \ldots + \nu_n) + (\nu_2 + \nu_3 + \ldots + \nu_n) + (\nu_3 + \ldots + \nu_n ) + \ldots + (\nu_n) = n. \end{equation*}

We then introduce the notation \(\lambda_j := \sum_{k=j}^n \nu_k\text{,}\) so that the sum above becomes

\begin{equation*} \lambda_1 + \lambda_2 + \lambda_3 + \ldots + \lambda_n = n. \end{equation*}

It is also clear that \(\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n \geq 0\text{,}\) since \(\lambda_1 - \lambda_2 = \nu_1\text{,}\) \(\lambda_2 - \lambda_3 = \nu_2\text{,}\) and so on, and the \(\nu_i\) are by definition non-negative integers.

The result of this combinatorial analysis is that the cycle structure of permutations in \(S_n\) are in one-to-one correspondence with decreasing sequences of non-negative integers \(\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_n\) such that \(\sum_{k=1}^n \lambda_k = n\text{.}\) Such a decreasing sequence of non-negative integers is called a partition of \(n\) (we usually omit the \(\lambda_k\)'s that are zero).

To be precise, we only showed how the \(\lambda_k\)'s can be constructed out of the cycle structure, that is out of the \(\nu_i\)'s. But it works the other way around as well. Given a partition of \(n\text{,}\) that is a sequence of \(\lambda_k\text{,}\) then we define \(\nu_k = \lambda_k - \lambda_{k+1}\text{,}\) with \(\nu_n = \lambda_n\text{.}\) \(\nu_k\) then gives us the number of cycles of length \(k\) in the cycle structure associated to the partition.

This construction will become clearer with an example. Let us construct the conjugacy classes in \(S_4\text{,}\) corresponding to the different cycle structures in \(S_4\text{.}\) This corresponds to different partitions of \(4\text{.}\) The five distinct partitions of \(4\) are easily found to be \(4\text{,}\) \(3+1\text{,}\) \(2+2\text{,}\) \(2+1+1\) and \(1+1+1+1\text{.}\) What this tells us directly is that there are five distinct conjugacy classes in \(S_4\text{.}\)

For fun, let us find out what kind of cycle structures these partitions correspond to. Consider first the partition \(4\text{,}\) which means \(\lambda_1 = 4\text{,}\) \(\lambda_2 = \lambda_3 = \lambda_4 = 0\text{.}\) To get the cycle structure, we compute \(\nu_1 = \lambda_1 - \lambda_2 = 4\text{,}\) \(\nu_2 = \nu_3 = \nu_4 = 0\text{.}\) Thus the corresponding cycle structure consists in \(4\) cycles of length \(1\text{.}\) There is in fact a unique permutation of \(S_4\) with this cycle structure, which is the identity permutation \(\pi = (1)(2)(3)(4)\text{.}\)

Consider the partition \(3+1\text{.}\) We get \(\nu_1 = 2\text{,}\) \(\nu_2 = 1\text{,}\) \(\nu_3=\nu_4=0\text{.}\) So the cycle structure consists in \(2\) cycles of length \(1\text{,}\) and one cycle of length \(2\text{.}\) The corresponding permutations are transpositions, and there are \(6\) of them in \(S_4\text{.}\)

Consider the partition \(2+2\text{.}\) We get \(\nu_1 = 0\text{,}\) \(\nu_2 = 2\text{,}\) \(\nu_3=\nu_4=0\text{.}\) The cycle structure is two cycles of length \(2\text{.}\) There are \(3\) such permutations in \(S_4\text{.}\)

Consider \(2+1+1\text{.}\) We get \(\nu_1=1\text{,}\) \(\nu_2=0\text{,}\) \(\nu_3=1\) and \(\nu_4=0\text{.}\) The cycle structure is one cycle of length \(3\) and one cycle of length \(1\text{,}\) which corresponds to cyclic permutations of length \(3\text{.}\) There are \(8\) such permutations in \(S_4\text{.}\)

Finally, \(1+1+1+1\text{,}\) which gives \(\nu_1 = \nu_2 = \nu_3 = 0\text{,}\) \(\nu_4=1\text{.}\) The cycle structure is a single cycle of length \(4\text{,}\) corresponding to a cyclic permutation of length \(4\text{.}\) There are \(6\) such permutations in \(S_4\text{.}\)

The result is that there are five conjugacy classes in \(S_4\text{,}\) corresponding to five possible cycle structures, corresponding to the five partitions of \(4\text{.}\) Counting the number of elements in each conjugacy classes, we end up with \(1 + 6 + 3 + 8 + 6 = 24 = 4!\text{,}\) which is indeed the order of \(S_4\text{.}\)

For those of you who like combinatorics, it is also fun to count in general the number of permutations of \(S_n\) of a given cycle structure. We will leave that as an exercise, but the result is the following. Consider a cycle structure \((1^{\nu_1}, 2^{\nu_2}, \ldots, n^{\nu_n})\) with \(\sum_k k \nu_k = n\text{.}\) The number of permutation in \(S_n\) with this cycle structure is precisely:

\begin{equation*} \frac{n!}{\prod_{j=1}^n j^{\nu_j} \nu_j !}. \end{equation*}

Let us check that this formula is consistent with what we wrote above in \(S_4\text{.}\) Consider for instance the cycle structure given by one cycle of length \(3\) and one cycle of length \(1\text{.}\) The number of permutations with that cycle structure is \(\frac{4!}{3 \cdot 1! \cdot 1 \cdot 1!} = 8\text{,}\) as written above. Similarly, the number of permutations with one cycle of length \(2\) and two cycles of length \(1\) is \(\frac{4!}{2 \cdot 1! \cdot 1^2 \cdot 2!} = 6\text{,}\) and so on and so forth.

Remark 1.8.17.

Note that partitions of an integer \(n\) can be encoded diagrammatically into Young diagrams. A Young diagram is a finite collection of boxes arranged in left-justified rows, with the rows “weakly decreasing” (i.e., such that each row has the same or shorter length than the row right above it). It is then clear that Young diagrams with \(n\) boxes contain precisely the same information as integer partitions of \(n\text{,}\) with the integers in the partition given by the length of the rows of the Young diagram. Young diagrams are useful for studying representations of the symmetric group, in which case they are upgraded to Young tableaux.

login