Element structure of symmetric groups

This article gives specific information, namely, element structure, about a family of groups, namely: symmetric group.
View element structure of group families | View other specific information about symmetric group

The symmetric group on a set is the group, under multiplication, of permutations of that set. The symmetric group of degree $n$ is the symmetric group on a set of size $n$. For convenience, we consider the set to be $\{ 1,2, \dots, n \}$.

This article discusses the element structure of the symmetric group of degree $n$.

Here are links to more detailed information for small values of degree $n$.

$n$	$n!$ (order of symmetric group)	symmetric group of degree $n$	element structure page
0	1	trivial group	--
1	1	trivial group	--
2	2	cyclic group:Z2	--
3	6	symmetric group:S3	element structure of symmetric group:S3
4	24	symmetric group:S4	element structure of symmetric group:S4
5	120	symmetric group:S5	element structure of symmetric group:S5
6	720	symmetric group:S6	element structure of symmetric group:S6
7	5040	symmetric group:S7	element structure of symmetric group:S7
8	40320	symmetric group:S8	element structure of symmetric group:S8
9	362880	symmetric group:S9	element structure of symmetric group:S9
10	3628800	symmetric group:S10	element structure of symmetric group:S10

Conjugacy class structure and cycle type

General result

Further information: Cycle type, cycle type determines conjugacy class, conjugacy class size formula in symmetric group

The cycle type of a permutation on a set of size $n$ is defined as the corresponding unordered integer partition of $n$ into the sizes of the cycles in the cycle decomposition. For instance, the permutation $(1,2,3,4,5)(6,7,8)(9,10,11,12)$ has cycle type $5 + 3 + 4$.

It turns out that there is a bijection between the set of conjugacy classes in the symmetric group of degree $n$ and the set of unordered integer partitions via the cycle type map, because cycle type determines conjugacy class.

The size of a conjugacy class corresponding to a cycle type with $a_j$ parts of size $j$, is:

$\frac{n!}{\prod_j (j)^{a_j}(a_j!)}$

See also conjugacy class size formula in symmetric group.

Particular cases

FACTS TO CHECK AGAINST SPECIFICALLY FOR SYMMETRIC GROUPS AND ALTERNATING GROUPS:
Please read element structure of symmetric groups for a summary description.
Conjugacy class parametrization: cycle type determines conjugacy class (in symmetric group)
Conjugacy class sizes: conjugacy class size formula in symmetric group
Other facts: even permutation (definition) -- the alternating group is the set of even permutations | splitting criterion for conjugacy classes in the alternating group (from symmetric group)| criterion for element of alternating group to be real

Degree	Number of conjugacy classes	List of conjugacy class sizes	Pairs of (partition,conjugacy class size)	More details
1	1	1	(1,1)	--
2	2	1,1	(2,1), (1+1,1)	--
3	3	1,2,3	(1+1+1,1), (3,2), (2+1,3)	link
4	5	1,3,6,6,8	(1+1+1+1,1), (2+2,3), (4,6), (2+1+1,6), (3+1,8)	link
5	7	1,10,15,20,20,24,30	(1+1+1+1+1,1), (2+1+1+1,10), (2+2+1,15), (3+2,20), (3+1+1,20), (5,24), (4+1,30)	link
6	11	1,15,15,40,40,45,90,90,120,120,144	Too long to list	link
7	15	1,21,70,105,105,210,210,280, 420,420,504,504,630,720,840	Too long to list	link
8	22	1, 28, 105, 112, 210, 420, 420, 1120, 1120, 1120, 1260, 1260, 1344, 1680, 2520, 2688, 3360, 3360, 3360, 4032, 5040, 5760	Too long to list	link
9	30	1, 36, 168, 378, 756, 945, 1260, 2240, 2520, 2520, 3024, 3360, 7560, 7560, 9072, 10080, 10080, 11340, 11340, 15120, 15120, 18144, 18144, 20160, 24192, 25920, 25920, 30240, 40320, 45360	Too long to list	link
10	42	1, 45, 240, 630, 945, 1260, 3150, 4725, 5040, 6048, 8400, 18900, 18900, 22400, 25200, 25200, 25200, 25200, 50400, 50400, 50400, 56700, 56700, 56700, 60480, 72576, 75600, 86400, 90720, 120960, 120960, 151200, 151200, 151200, 172800, 181440, 201600, 226800, 226800, 259200, 362880, 403200	Too long to list	link

Case $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	--

Case $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)	--

Case $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] order 1: 1 (1 class) order 2: 25 (2 classes) order 3: 20 (1 class) order 4: 30 (1 class) order 5: 24 (1 class) order 6: 20 (1 class)

Groupings of conjugacy classes

Based on number of cycles

Further information: probability distribution of number of cycles of permutations, expected number of cycles of permutation equals harmonic number of degree

We can partition the set $S_n$ based on the number of cycles of each permutation. Since the number of cycles depends only on the cycle type, i.e., on the conjugacy class, this descends to a partition of the set of conjugacy classes in $S_n$. The number of cycles can be any number $k$, with $1 \le k \le n$.

• The number of elements of $S_n$ with exactly $k$ cycles is denoted $|s(n,k)|$ and is termed the unsigned Stirling number of the first kind with parameters $n$ and $k$. This is in contrast with the Stirling number of the second kind, which is the number of partitions of a set of size $n$ into $k$ nonempty subsets. The probability of $k$ cycles is thus $|s(n,k)|/n!$. Further information: probability distribution of number of cycles of permutations
• The expected number of cycles in an element of $S_n$ is the harmonic number $H_n,$ defined as $1 + 1/2 + \dots + 1/n$. This is approximately $\log n$ for lrage $n$. Further information: expected number of cycles of permutation equals harmonic number of degree

Based on number of fixed points

Further information: probability distribution of number of fixed points of permutations, expected number of fixed points of permutation equals one

We can partition the set $S_n$ based on the number of fixed points of each permutation. Since the number of fixed points depends only on the cycle type, i.e., on the conjugacy class, this descends to a partition of the set of conjugacy classes in $S_n$. The number of fixed points can be any number $r$, with $0 \le r \le n$ and $r \ne n - 1$.

• The number of elements with $r$ fixed points is $\binom{n}{r}D_{n-r}$ where $D_{n-r}$ is the derangement number, i.e., the number of permutations on a set of size $n - r$ with no fixed points. Further information: probability distribution of number of fixed points of permutations
• The expected number of fixed points is one. Further information: expected number of fixed points of permutation equals one

Other kinds of classifications/groupings of elements not invariant under conjugation

All of these require a total ordering on the set on which the group acts. For convenience, we assume a symmetric group of degree $n$ acting the usual way on the set $\{ 1,2,3, \dots, n \}$.

For most of these, it is useful to think of the permutation as a string of length $n$ given by its one-line notation.

Looking at increase/decrease patterns

Here, we take a permutation $\sigma$on the set $\{ 1,2, \dots, n \}$ and obtain from it a binary string of length $n - 1$ with letters $I$ and $D$ as follows: if the $(k+1)^{th}$ letter in the one-line notation of $\sigma$ is greater than the $k^{th}$ letter, we write an $I$ in the $k^{th}$ letter of the binary string, and if it is smaller, we write a $D$ in the $k^{th}$ letter of the binary sequence. The increasing parts are called rises and the decreasing parts are called runs, so this is also called the rise-run pattern.

We can partition the set of permutations based on the rise/run patterns. Essentially, we are looking at the fibers of the map described above from $S_n$ to the set $\{ I, D \}^{n-1}$ of size $2^{n-1}$.

We may further be interested in grouping these fibers further by creating equivalence classes in $\{ I, D \}^{n-1}$. One common way of doing so is to look at the number of occurrences of $I$ and $D$. The number of permutations that map to strings with $k$ $I$s is termed the Eulerian number $A(n,k)$.

The Robinson-Schensted correspondence

The Robinson-Schensted correspondence encodes a permutation using a ordered pair of Young tableaux of size $n$ the same shape -- the position tableau and the shape tableau. This establishes a bijection between the set $S_n$ and the disjoint union, over all Young diagrams with $n$ boxes, of ordered pairs of Young tableaux of that shape. It turns out that for each Young diagram (which corresponds to an unordered integer partition), there is a corresponding representation of $S_n$, and this representation has the same degree as the number of Young tableaux whose shape is that Young diagram.

The algorithm used in the correspondence is termed the bumping algorithm (there are many essentially equivalent variants).

The Bruhat ordering

Further information: Bruhat ordering on symmetric groups

This is an ordering based on a generating set for $S_n$, namely, the generators are of the form $s_i = (i,i+1)$. There are $n - 1$ such generators. The Bruhat length of an element of $S_n$ is the length of the shortest word for it in terms of those letters. We also define a partial ordering on all elements of $S_n$ based on whether a shortest word for one can be obtained from a shortest word for the other by multiplying on the left and right by $s_i$s. The Bruhat ordering is the precise opposite to an entry-wise comparison ordering of the score matrices. The largest element in the Bruhat ordering is the antidiagonal permutation, given by $(1,n)(2,n-1) \dots$. its Bruhat length is $\binom{n}{2}$.

The partially ordered set we obtain via the Bruhat ordering exhibits two important symmetries: a symmetry corresponding to conjugation by the antidiagonal (which essentially means reversing the order) and a symmetry corresponding to a left-right interchange. There is also an anti-symmetry of the lattice obtained by left multiplication by the antidiagonal element .