Number of permutations for a cycle-type

In the proof that the alternating group $A_5$ is a simple group, we first write cycle-types of the conjugacy classes of $S_5$ which correspond to cycle-types $$1, 2^1, 2^2, 3^1, 2^13^1, 4^1, 5^1$$ and clearly the permutations of cycle-types $1, 2^2, 3^1, 5^1$ are even.

But then my lecture notes state that there is $1$ permutation of cycle type $1$, $15$ of type $2^2$, $20$ of type $3^1$ and $24$ of type $5^1$ making $60$ in total. My question is how did they find the number of permutations for each cycle-type?

A follow up question is that my lecture notes then state that: 'The problem is that these classes are in $S_n$, and two permutations could conceivably be conjugate in $S_n$ but not in $A_n$.'

Is this because it could be possible that the element $f \in G$ which 'links' two elements in the same conjugacy classes could be in $S_n$ but not in $A_n$?

Thanks!

Solution 1:

We can turn sequences $(a_1,\cdots,a_n)$ of distinct elements of $\{1,\cdots,n\}$ into permutations of a given cycle type by simply placing parentheses around consecutive entries in a way that matches the desired type. Every permutation can be obtained this way; simply write down its cycle decomposition and remove the parentheses as appropriate to go backwards. So we have a surjection from these sequences into the permutations with desired type. But the map is not injective; one permutation may be obtained from multiple sequences. How many sequences? We shall count.

Fix the permutation of our cycle type in one-line notation, and assume our scheme for partitioning sequences with parentheses around consecutive terms involved the largest parts first, with multi-plicity. For any part of the partition, the elements can be cycled at whim inside the part without altering the overall fixed permutation. Each cycling process is independent, so multiplying the number of cycle actions all together with multiplicity we get $\lambda_1^{m_1}\cdots\lambda_k^{m_k}$ as the number of sequences resulting from cyclings.

Finally, for each $\lambda_i$, we can permute the $m_i$ distinct parts of size $\lambda_i$, and these switcharoos are independent of each other, and independent of all the internal cyclings as well. The number of permutations of the $\lambda_i$-parts is of course $m_i!$. This suffices to count the preimage of a permutation.

The number of sequences (which is $n!$) overcounts the number of permutations of the given type by a factor of $\lambda_1^{m_1}\cdots\lambda_k^{m_k}m_1!\cdots m_k!$, each $m_i!$ for switching the parts around of the sequences.

Therefore, the number of permutations from $S_n$ with cycle type $\lambda_1^{m_1}\cdots\lambda_k^{m_k}$ is given by

$$\frac{n!}{\lambda_1^{m_1}\cdots\lambda_k^{m_k}m_1!\cdots m_k!}.$$

Solution 2:

For your first question, here's a start to counting how many cycles of a given type. Let me show you how to count cycles of type $3^1$ and $2^2$ in $S_4$, and hopefully you can generalize the calculations to your case. To compute the number of cycles of type $3^1$, first count the number of ways you can pick $3$ numbers to be in the $3$-cycle and $1$ number for the remaining $1$-cycle. There are ${4 \choose 3} = 4$ ways to do this. Once you've chosen which numbers to go in your cycles, how many ways can you order the numbers? Well, in the $1$-cycle, there's clearly only one way. But in the $3$-cycle, there are $2$ ways. Why? Because you can choose any of the $3$ numbers to go in the first position of the cycle, then you have $2$ choices for the number in the second position, and then the third number is set. That seems like $6$ choices, but you have to remember that you can write the same cycle in $3$ different ways, depending on which number you choose to write first. So there are really only $3! / 3 = 2$ $3$-cycles that use any particular choice of $3$ numbers. So to recap, there are $4$ ways to distribute the numbers $1,2,3,4$ into the cycles and for each such distribution, there are $2$ different permutations we can make. In total, there are $4 \cdot 2 = 8$ cycles of type $3^1$. If you trace through the argument carefully, you can see that it tells you how to write the cycles down: $(123), (132), (124), (142), \dots$.

For type $2^2$, we first figure how to partition the numbers $1,2,3,4$ into $2$ groups of $2$. There are ${4 \choose 2} = 6$ ways to do this if we keep track of which order they are in, but we have to divide by $2$ if we don't care about the order, which we don't in the case of cycle types. The reason we don't care order is that, for example, $(14)(23)$ and $(23)(14)$ represent the same permutation. So there are only $6 / 2 = 3$ ways to partition the numbers. And once we do that, there's only one way to produce a $2$-cycle now that we have specified the numbers that go in. So there are $3$ cycles of type $2^2$: $(12)(34), (13)(24), (14)(23)$.

As for your second question, you are correct. In general, if you have a group $G$ and a subgroup $H$, and if you consider two elements $h_1, h_2 \in H$, it is possible that they are conjugate in $G$, say $h_2 = g h_1 g^{-1}$ for some $g \in G$, but that there is no such $g \in H$, meaning that they are no longer conjugate in $H$. Kannapan's link tells you when this occurs in general for the pair $(S_n,A_n)$.