The set of all permutations of an n-element set is denoted by Sn.
This is a "group"
(with respect to the composition of maps).
For n > 2, all the groups Sn are non-commutative (thus quite complicated).
Note: Every finite group is subgroup of some group Sn, thus we see:
the groups Sn are in some sense the most complicated ones.
But we have considered only individual permutations (and their powers).
The powers of a fixed permutation form a commutative subgroup of Sn.
(This means: The non-commutativity of the group Sn did not play a role.)
What was essential? The possible cycle lengths!
- | The order 8 of the doubling transformation d8 (Photo booth). |
- | Fixed points (thus cycles of length 1) (Secret Santa, Treize). |
- | Cycles of large length (100 prisoners). |
To work with permutations provides many further surprises!
(For example, those of the Catalan combinatorics.)