A permutation is an automorphism in Set. More explicitly, a permutation of a set XX is an invertible function from XX to itself.


The group of permutations of XX (that is the automorphism group of XX in SetSet) is the symmetric group (or permutation group) on XX (a finite group). This group may be denoted S XS_X, Σ X\Sigma_X, or X!X!. When XX is the finite set [n][n] with nn elements, one typically writes S nS_n or Σ n\Sigma_n; note that this group has n!n! elements.

In combinatorics, one often wants a slight generalisation. Given a natural number rr, an rr-permutation of XX is an injective function from [r][r] to XX, that is a list of rr distinct elements of XX. Note that the number of rr-permutations of [n][n] is counted by the falling factorial n(n1)(nr+1)n(n-1)\dots(n-r+1). Then an nn-permutation of [n][n] is the same as a permutation of [n][n], and the total number of such permutations is of course counted by the ordinary factorial n!n!. (That an injective function from XX to itself must be invertible characterises XX as a Dedekind-finite set.)

Concrete representations

Via string diagrams

Via cycle decompositions

Every permutation π:XX\pi : X \to X generates a cyclic subgroup π\langle \pi \rangle of the symmetric group S XS_X, and hence inherits a group action on XX. The orbits of this action partition the set XX into a disjoint union of cycles, called the cyclic decomposition of the permutation π\pi.

For example, let π\pi be the permutation on [6]={0,,5}[6] = \{0,\dots,5\} defined by

π=00 13 24 35 42 51\pi = \array{0 \mapsto 0 \\ 1 \mapsto 3 \\ 2 \mapsto 4 \\ 3 \mapsto 5 \\ 4 \mapsto 2 \\ 5 \mapsto 1}

The domain of the permutation is partitioned into three π\langle\pi\rangle-orbits

[6]={0}{1,3,5}{2,4}[6] = \{0\} \cup \{1,3,5\} \cup \{2,4\}

corresponding to the three cycles

0π01π3π5π12π4π20 \underset{\pi}{\to} 0 \qquad 1 \underset{\pi}{\to} 3 \underset{\pi}{\to} 5 \underset{\pi}{\to} 1 \qquad 2 \underset{\pi}{\to} 4 \underset{\pi}{\to} 2

Finally, we can express this more compactly by writing π\pi in cycle form, as the product π=(0)(135)(24)\pi = (0)(1\,3\,5)(2\,4).


Relation to the field with one element

One may regard the symmetric group S nS_n as the general linear group in dimension nn on the field with one element GL(n,𝔽 1)GL(n,\mathbb{F}_1).


Revised on August 31, 2015 05:38:24 by Noam Zeilberger (