= Permutation
{title2=$\sigma:S\to S\text{ bijective}$}
{wiki}
A <permutation> of a <set> $S$ is a <bijection> $\sigma:S\to S$: every element has exactly one <image> and every element appears exactly once as an <image>. For a <finite set>, a <permutation> can also be recorded as an ordering of all its elements, once a reference order has been chosen. For three distinct letters $A,B,C$, the six orderings are
$$
ABC,\quad ACB,\quad BAC,\quad BCA,\quad CAB,\quad CBA.
$$
There are three choices for the first letter, two unused letters for the second, and one for the third. Every path in the tree gives one complete ordering, and every ordering has one such path, so the <rule of product> gives $3\cdot2\cdot1=3!=6$, a <factorial>.
\Image[/factorial-permutation-choice-tree.png]
{title=The full choice tree for the six <permutations> of three distinct letters: three first choices, two second choices, and one third choice}
\b[Ordering versus mapping.] Label the reference positions $1,\ldots,n$. An ordering <tuple> $(a_1,\ldots,a_n)$ of these labels describes the <function> $\sigma(i)=a_i$; conversely, reading the <images> $\sigma(1),\ldots,\sigma(n)$ recovers the ordering. For example,
$$
\sigma=\begin{pmatrix}1&2&3&4\\3&1&4&2\end{pmatrix}
$$
means $1\mapsto3$, $2\mapsto1$, $3\mapsto4$, $4\mapsto2$. Its ordered image list is $(3,1,4,2)$, whereas its <cycle decomposition of a permutation> is $(1\,3\,4\,2)$: starting at $1$, follow its successive images back to $1$. Parentheses in the latter expression encode arrows around a <permutation cycle>, rather than an image list in reference order. https://math.mit.edu/~fgotti/docs/Courses/C.%20Combinatorial%20Analysis/11.%20Permutations%20I/Permutations%20I.pdf[Felix Gotti, MIT 18.211, lecture 11, pages 1–2: arrangements, bijections and cycles]{ref}
The two viewpoints answer different useful questions about the same object. An ordering tells us which object occupies each position; a <bijection> tells us where each label is sent and allows successive rearrangements through <function composition>. All <permutations> of $n$ labels form the <symmetric group>, whose <subgroups> are <permutation groups>. The counting viewpoint supplies $n!$ possibilities, a <factorial>; the mapping viewpoint reveals how rearrangements combine.
\b[Composition convention.] Apply the rightmost <permutation> first:
$$
(\sigma\tau)(i)=\sigma(\tau(i)).
$$
For the displayed $\sigma=(1\,3\,4\,2)$ and the <transposition> $\tau=(1\,2)$, direct evaluation gives
$$
\sigma\tau=\begin{pmatrix}1&2&3&4\\1&3&4&2\end{pmatrix}=(2\,3\,4),\qquad
\tau\sigma=\begin{pmatrix}1&2&3&4\\3&2&4&1\end{pmatrix}=(1\,3\,4).
$$
For instance, $(\sigma\tau)(1)=\sigma(2)=1$, but $(\tau\sigma)(1)=\tau(3)=3$. Thus <function composition> of <permutations> need not be <commutative>; the omitted labels in these <permutation cycles> are <fixed points>.
Back to article page
