Transpositionen

Eine Transposition ist ein Zyklus der Länge 2, wie z.B. $(2 4)$. Die Transpositionen sind für die Permutationen das, was die Primzahlen für die natürlichen Zahlen sind, denn es gilt:

Jede Permutation lässt sich als Produkt von Transpositionen darstellen.

Wenn die Permutation $\pi$ in Zyklenschreibweise gegeben ist, und $z=(\pi_1\pi_2\ldots\pi_n)$ ein Zyklus der Länge $n$, dann kann man sich einfach überzeugen, dass $z=(\pi_1\pi_n)(\pi_1\pi_{n-1})\ldots(\pi_1\pi_2)$ die gesuchte Zerlegung. $\qed$

Im Gegensatz zur Primzahlzerlegung ist die Zerlegung einer Permutation in ein Produkt von Transpositionen nicht eindeutig. Jedes solches Produkt kann durch Multiplikation mit einem Transpositionspaar der Form $(\pi_k\pi_l)(\pi_l\pi_k)$ in ein weiteres Produkt überführt werden. Andererseits kann man sich überlegen, dass die Multiplikation einer Permutation mit einer einzelnen Transposition niemals die Permutation selbst ergeben kann.