8

I have a bit of a problem. I'm currently reading about permutations, and I have a little exercise that asked me to find all cycle structures in $S_6$. I came up with the following

$ ( -)\\ (- -)\\ (- - -)\\ (- - - -)\\ (- - - - -)\\ (- - - - - -)\\ (- -)(--)\\ (- -)(---)\\ (- -)(----)\\ (- -)(--)(--)\\ (---)(---) $

Now, according to the solutions at the end of my book. The above is correct. Now, I got curious and wanted to check how many elements there is of each cycle structure. And I came up with the following

$ ( -) \text{ 1 element}\\ (- -) \text{ 15 elements}\\ (- - -)\text{ 40 elements}\\ (- - - -) \text{ 90 elements}\\ (- - - - -) \text{ 144 elements}\\ (- - - - - -)\text{ 120 elements}\\ (- -)(--) \text{ 45 elements}\\ (- -)(---) \text{ 60 elements}\\ (- -)(----) \text{ 45 elements}\\ (- -)(--)(--) \text{ 30 elements}\\ (---)(---) \text{ 40 elements} $

However, the above gives me 630 elements in total. Which is wrong since the order of $S_6 $ is $n!$.

The way i've calculated how many elements are by taking how many ways there is fill a given cycle structure with elements, and then dividing out elements due to it not mattering which element is the first in a cycle, or which cycle is the first in a structure. So, for example:

For$(--)(--)$ we have $6\times5\times4\times3 / (2\times2\times2)$, for $(---)$ it would be $6\times5\times4 / 3$ and for $(--)(--)(--)$ it would be $6!/(2\times2\times2\times3)$

I would really appreciate it if somebody could point out my mistake here :-)

JustDanyul
  • 431
  • 4
  • 10
  • 1
    $(--)(--)(--)$ should have $3!$ not $3$ in the denominator. The three transpositions may have any order, and there are $3!$ orders. – vadim123 Nov 22 '14 at 17:14
  • 1
    I'm getting 1, 15, 40, 90, 144, 120, 45, 120, 90, 15, 40. – Mike Nov 22 '14 at 17:14

2 Answers2

4

Almost all your calculations are correct. I'll correct the three which are wrong.

For $(--)(---)$, we choose a number for each slot, yielding $6\times 5\times 4\times 3\times 2$. However we have to divide out by $2\times 3$ because we can cycle the elements within a given cycle without changing the cycle itself. Note that we do not divide by an extra factor of $2$ since $2$-cycles and $3$-cycles are different. Thus we get a total of $120$ elements of the group of this type.

Similarly, the number of elements of type $(--)(----)$ is $6\times 5\times 4\times 3\times 2\times 1/(2\times 4) = 90$.

Finally, for $(--)(--)(--)$, we again pick numbers for each slot, obtaining $6\times 5\times 4\times 3\times 2\times 1$ options. We then divide out by a factor of $2$ for each $2$-cycle, and a factor of $3!$, since this is the number of ways we could have reordered the three $2$-cycles. We get $15$ elements of this type.

With these corrections, the total number of elements of the group sums to $720 = 6!$, as expected.

Alex G.
  • 8,848
4

As we were discussing in chat, if a permutation has cycle type associated to the partition $(n_1,\ldots,n_p)$ of $n$, where $n_1=\ldots=n_{q_1}<n_{q_1+1}=\ldots=n_{q_1+q_2}<\ldots$ then the number of permutation conjugate to this (i.e. of this very same cycle type) is $$\frac{n!}{\prod q_i!\prod n_k}$$

The idea is as follows. First, we take the $n$ numbers in question. We place brackets according to the partition, and we get one such permutation. But since the cycles are disjoint, we can permute the $q_i$ equal cycles in $q_i!$ ways, and since we care about the order in which the $n_i$ appear, we do not permute cycles of different size. Now, inside each cycle we can cyclically permute the numbers in $n_i$ ways, yielding the same cycle. Hence we divide by $\prod q_j!\prod n_i$.

Pedro
  • 122,002