Conjugacy class size formula in symmetric group

From Groupprops
Jump to: navigation, search

Statement

Suppose n is a natural number and \lambda is an unordered integer partition of n such that \lambda has a_j parts of size j for each j. In other words, there are a_1 1s, a_2 2s, a_3 3s, and so on. Let c be the conjugacy class in the symmetric group of degree n comprising the elements whose cycle type is \lambda, i.e., those elements whose cycle decomposition has a_j cycles of length j for each j. Then:

\! |c| = \frac{n!}{\prod_j (j)^{a_j}(a_j!)}

Note that those j where a_j = 0 contribute a 1 in the denominator and can be ignored from the product, while for those j where a_j = 1, the a_j! term can be omitted.

Equivalently, if C is the centralizer of any element of c, then:

\! |C| = \prod_j (j)^{a_j}(a_j!)

These are equivalent because size of conjugacy class equals index of centralizer, which follows from the identification of the conjugacy class with the left coset space of the centralizer via the action of the group on itself as automorphisms by conjugation.

Related facts

Examples

Illustrative examples

For instance, consider n = 23 with the partition 23 = 3 + 3 + 3 + 3 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1. There are four 3s, three 2s, and five 1s. An example element with this cycle type is given by the cycle decomposition:

\! (1,2,3)(4,5,6)(7,8,9)(10,11,12)(13,14)(15,16)(17,18)

The size of the conjugacy class corresponding to this partition is:

\! \frac{23!}{[(3)^4(4!)][(2)^3(3!)][(1)^5(5!)]}

Here's another example: 13 = 5 + 4 + 4. There is one 5 and two 4s, and we get:

\! \frac{13!}{[(5)^1(1!)][(4)^2(2!)]}

When a particular j has a_j = 1 (i.e., it occurs only once in the partition) then the corresponding term divided is j^1(1!) = j, so the above can be written more briefly:

\! \frac{13!}{[5][(4)^2(2!)]}

Similarly, consider 15 = 5 + 4 + 3 + 3. We get:

\! \frac{15!}{[5][4][(3)^2(2!)]}

Comprehensive treatment of small degrees

In the right column links in the table below, you can see tabulated information on the sizes of conjugacy classes, as well as how the formula is applied to the cycle sizes to compute each specific size. The cases n = 3,4,5 are embedded below.

Degree Symmetric group List of conjugacy class sizes Element structure page Section on conjugacy class structure interpreted as symmetric group
3 symmetric group:S3 1,2,3 element structure of symmetric group:S3 element structure of symmetric group:S3#Interpretation as symmetric group
4 symmetric group:S4 1,3,6,6,8 element structure of symmetric group:S4 element structure of symmetric group:S4#Interpretation as symmetric group
5 symmetric group:S5 1,10,15,20,20,24,30 element structure of symmetric group:S5 element structure of symmetric group:S5#Interpretation as symmetric group
6 symmetric group:S6 1,15,15,40,40,45,90,90,120,120,144 element structure of symmetric group:S6 element structure of symmetric group:S6#Interpretation as symmetric group
7 symmetric group:S7 1,21,70,105,105,210,210,280, 420,420,504,504,630,720,840 element structure of symmetric group:S7 element structure of symmetric group:S7#Interpretation as symmetric group
8 symmetric group:S8 1, 28, 105, 112, 210, 420, 420, 1120, 1120, 1120, 1260, 1260, 1344, 1680, 2520, 2688, 3360, 3360, 3360, 4032, 5040, 5760 element structure of symmetric group:S8 element structure of symmetric group:S8#Interpretation as symmetric group

n = 3

Partition Partition in grouped form Verbal description of cycle type Elements with the cycle type in cycle decomposition notation Elements with the cycle type in one-line notation Size of conjugacy class Formula for size Even or odd? If even, splits? If splits, real in alternating group? Element order Formula calculating element order
1 + 1 + 1 1 (3 times) three fixed points () -- the identity element 123 1 \! \frac{3!}{(1)^3(3!)} even; no 1 \operatorname{lcm} \{ 1, 1, 1 \}
2 + 1 2 (1 time), 1 (1 time) transposition in symmetric group:S3: one 2-cycle, one fixed point (1,2), (1,3), (2,3) 213, 321, 132 3 \! \frac{3!}{(2)(1)} odd 2 \operatorname{lcm} \{ 2,1 \}
3 3 (1 time) 3-cycle in symmetric group:S3: one 3-cycle (1,2,3), (1,3,2) 231, 312 2 \! \frac{3!}{3} even; yes; no 3 \operatorname{lcm} \{ 3 \}
Total (3 rows -- 3 being the number of unordered integer partitions of 3) -- -- -- -- 6 (equals 3!, the size of the symmetric group) -- odd: 3
even;no: 1
even; yes; no: 2
order 1: 1, order 2: 3, order 3: 2 --


n = 4

Partition Partition in grouped form Verbal description of cycle type Elements with the cycle type Size of conjugacy class Formula for size Even or odd? If even, splits? If splits, real in alternating group? Element order Formula calculating element order
1 + 1 + 1 + 1 1 (4 times) four cycles of size one each, i.e., four fixed points () -- the identity element 1 \! \frac{4!}{(1)^4(4!)} even; no 1 \operatorname{lcm}\{ 1,1,1,1 \}
2 + 1 + 1 2 (1 time), 1 (2 times) one transposition (cycle of size two), two fixed points (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) 6 \! \frac{4!}{[(2)^1(1!)][(1)^2(2!)]}, also \binom{4}{2} odd 2 \operatorname{lcm}\{2,1,1 \}
2 + 2 2 (2 times) double transposition: two cycles of size two (1,2)(3,4), (1,3)(2,4), (1,4)(2,3) 3 \! \frac{4!}{(2)^2(2!)} even; no 2 \operatorname{lcm}\{2,2 \}
3 + 1 3 (1 time), 1 (1 time) one 3-cycle, one fixed point (1,2,3), (1,3,2), (2,3,4), (2,4,3), (3,4,1), (3,1,4), (4,1,2), (4,2,1) 8 \! \frac{4!}{[(3)^1(1!)][(1)^1(1!)]} or \! \frac{4!}{(3)(1)} even; yes; no 3 \operatorname{lcm}\{3,1 \}
4 4 (1 time) one 4-cycle, no fixed points (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3), (1,4,3,2) 6 \! \frac{4!}{(4)^1(1!)} or \frac{4!}{4} odd 4 \operatorname{lcm} \{ 4 \}
Total (5 rows, 5 being the number of unordered integer partitions of 4) -- -- -- 24 (equals 4!, the order of the whole group) -- odd: 12 (2 classes)
even; no: 4 (2 classes)
even; yes; no: 8 (1 class)
order 1: 1 (1 class)
order 2: 9 (2 classes)
order 3: 8 (1 class)
order 4: 6 (1 class)
--


n = 5

Partition Partition in grouped form Verbal description of cycle type Representative element with the cycle type Size of conjugacy class Formula calculating size Even or odd? If even, splits? If splits, real in alternating group? Element order Formula calcuating element order
1 + 1 + 1 + 1 + 1 1 (5 times) five fixed points () -- the identity element 1 \! \frac{5!}{(1)^5(5!)} even; no 1 \operatorname{lcm}\{1 \}
2 + 1 + 1 + 1 2 (1 time), 1 (3 times) transposition: one 2-cycle, three fixed point (1,2) 10 \! \frac{5!}{[(2)^1(1!)][(1)^3(3!)]} or \! \frac{5!}{(2)(1)^3(3!)}, also \binom{5}{2} in this case odd 2 \operatorname{lcm}\{2,1 \}
3 + 1 + 1 3 (1 time), 1 (2 times) one 3-cycle, two fixed points (1,2,3) 20 \! \frac{5!}{[(3)^1(1!)][(1)^2(2!)]} or \! \frac{5!}{(3)(1)^2(2!)} even; no 3 \operatorname{lcm}\{3,1\}
2 + 2 + 1 2 (2 times), 1 (1 time) double transposition: two 2-cycles, one fixed point (1,2)(3,4) 15 \frac{5!}{[2^2(2!)][1^1(1!)]} or \! \frac{5!}{2^2(2!)(1)} even; no 2 \operatorname{lcm}\{2,1 \}
4 + 1 4 (1 time), 1 (1 time) one 4-cycle, one fixed point (1,2,3,4) 30 \! \frac{5!}{[4^1(1!)][1^1(1!)]} or\! \frac{5!}{(4)(1)} odd 4 \operatorname{lcm}\{4,1\}
3 + 2 3 (1 time), 2 (1 time) one 3-cycle, one 2-cycle (1,2,3)(4,5) 20 \! \frac{5!}{[3^1(1!)][2^1(1!)]} or \! \frac{5!}{(3)(2)} odd 6 \operatorname{lcm}\{3,2 \}
5 5 (1 time) one 5-cycle (1,2,3,4,5) 24 \frac{5!}{5^1(1!)} or \! \frac{5!}{5} even; yes; yes 5 \operatorname{lcm} \{ 5 \}
Total (7 rows, 7 being the number of unordered integer partitions of 5) -- -- -- 120 (equals order of the group) -- odd: 60 (3 classes)
even;no: 36 (3 classes)
even;yes;yes: 24 (1 class)
[SHOW MORE]