Combinatorics of symmetric groups

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

This page describes some general combinatorics that can be done with the elements of the symmetric groups.

Particular cases

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

Partitions, subset partitions, and cycle decompositions

Denote by $B (n)$ the set of all unordered set partitions of ${1, 2, \dots, n}$ into subsets and by $P (n)$ the set of unordered integer partitions of $n$ . There are natural combinatorial maps:

$S_{n} \to B (n) \to P (n)$

where the first map sends a permutation to the subset partition induced by its cycle decomposition, which is equivalently the decomposition into orbits for the action of the cyclic subgroup generated by that permutation on ${1, 2, \dots, n}$ . The second map sends a subset partition to the partition of $n$ given by the sizes of the parts. The composite of the two maps is termed the cycle type, and classifies conjugacy classes in $S_{n}$ , because cycle type determines conjugacy class.

Further, if we define actions as follows:

$S_{n}$ acts on itself by conjugation
$S_{n}$ acts on $B (n)$ by moving around the elements and hence changing the subsets
$S_{n}$ acts on $P (n)$ trivially

then the maps above are $S_{n}$ -equivariant, i.e., they commute with the $S_{n}$ -action. Moreover, the action on $B (n)$ is transitive on each fiber above $P (n)$ and the action on $S_{n}$ is transitive on each fiber above the composite map to $P (n)$ . In particular, for two elements of $B (n)$ that map to the same element of $P (n)$ , the fibers above them in $S_{n}$ have the same size.

There are formulas for calculating the sizes of the fibers at each level.