Combinatorics of symmetric groups

From Groupprops
Jump to: navigation, search
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 \mathcal{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 \mathcal{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 \mathcal{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 \mathcal{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 \mathcal{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.