Vipul: Created page with "{{group family-specific information| group family = symmetric group| information type = combinatorics| connective = of}} This page describes some general combinatorics that c..."

2012-11-26T00:17:32Z

Created page with "{{group family-specific information| group family = symmetric group| information type = combinatorics| connective = of}} This page describes some general combinatorics that c..."

New page

{{group family-specific information|
group family = symmetric group|
information type = combinatorics|
connective = of}}

This page describes some general combinatorics that can be done with the elements of the [[symmetric group]]s.

==Particular cases==

{| class="sortable" border="1"
! <math>n</math> !! <math>n!</math> (equals order of symmetric group) !! symmetric group of degree <math>n</math> !! 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 <math>\mathcal{B}(n)</math> the set of all ''unordered'' set partitions of <math>\{ 1,2,\dots,n\}</math> into subsets and by <math>P(n)</math> the [[set of unordered integer partitions]] of <math>n</math>. There are natural combinatorial maps:

<math>S_n \to \mathcal{B}(n) \to P(n)</math>

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

Further, if we define actions as follows:

* <math>S_n</math> acts on itself by conjugation
* <math>S_n</math> acts on <math>\mathcal{B}(n)</math> by moving around the elements and hence changing the subsets
* <math>S_n</math> acts on <math>P(n)</math> trivially

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

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

Combinatorics of symmetric groups - Revision history

Vipul: Created page with "{{group family-specific information| group family = symmetric group| information type = combinatorics| connective = of}} This page describes some general combinatorics that c..."