Sei $S_n=\{\sigma:M\to M\;\vert\;\sigma\text{ ist bijektiv}\}$ die symmetrische Gruppe auf der $n$-elementigen Menge $M=\{1,\ldots,n\}$. Spezielle Elemente sind die Transpositionen $\tau=(i,j):M\to M$, die $i$ und $j$ vertauschen ($i\ne j$) und die restlichen Elemente von $M$ auf sich selbst abbilden. Der folgende Satz fasst die uns interessierenden Eigenschaften der symmetrischen Gruppe $S_n$ zusammen.
Satz. Jedes Element von $S_n$ für $n>1$ ist ein Produkt von Transpositionen. Die Abbildung
\begin{align*} \mathrm{sign}:S_n&\to \{\pm1\}\\ \sigma&\mapsto \prod_{i < j}\frac{\sigma(i)-\sigma(j)}{i-j}\end{align*} ist multiplikativ $ \mathrm{sign}(\sigma\circ\pi)= \mathrm{sign}(\sigma) \cdot\mathrm{sign}(\pi)$. Für eine Transposition $\tau$ gilt $ \mathrm{sign}(\tau)=-1$.
Beweis. Wir beweisen die erste Aussage mittels Induktion nach $n$. Die symmetrische Gruppe $S_2$ besteht aus Transposition $\tau=(1,2)$ und der identischen Abbildung $id=\tau^2$.
Im Induktionsschritt identifizieren wir $S_{n-1}$ mit der Untergruppe der Permutationen von $M=\{1,\ldots,n\}$, die das Element $n$ fest lassen. Sei nun $\sigma\in S_n$ und $\sigma(n)=i$. Dann ist mit $\tau=(i,n)$ die Permutation $\tau\circ\sigma$ in der Untergruppe $S_{n-1}$ und nach Induktionsvoraussetzung Produkt von Transpositionen. Folglich gilt das auch für $\sigma=\tau\circ\tau\circ\sigma$. Damit ist die erste Aussage bewiesen.
Nun zur Abbildung $\mathrm{sign}$. Zunächst müssen wir uns klar machen, dass das angegebene Produkt immer den Betrag $1$ hat: Für je zwei verschiedene Elemente $l,m\in M$ taucht der Faktor $|l-m|$ in dem Produkt
\[\prod_{i \lt j}\frac{|\sigma(i)-\sigma(j)|}{|i-j|}\] sowohl im Zähler als auch im Nenner genau einmal auf. Also ist $\mathrm{sign}(\sigma)=(-1)^{a(\sigma)}$, wo $a(\sigma)$ die Anzahl der Paare $(i,j)\in M\times M$ mit $i\lt j$ beschreibt, für die gilt $\sigma(i)\gt \sigma(j)$. Man nennt $a(\sigma)$ die Anzahl der Fehlstellen.
Es sei $P$ die Menge der Paare $(i,j)\in M\times M$ mit $i\not= j$. Wir nennen eine Teilmenge $H\subset P$ ein Halbsystem, wenn es von den Paaren $(i,j)$ und $(j,i)$ jeweils genau eines enthält. Für jede Permutation $\sigma\in S_n$ ist das Produkt
\[\prod_{(i,j)\in
H}\frac{\sigma(i)-\sigma(j)}{i-j}\] unabhängig vom Halbsystem $H$, also gleich $\mathrm{sign}(\sigma)$. Denn wird $(i,j)$ durch $(j,i)$ ersetzt, so ändert sich in dem entsprechenden Faktor sowohl im Zähler wie auch im Nenner das Vorzeichen. Ist $H$ ein Halbsystem, so ist für $\pi\in S_n$ auch $\pi(H)=\{(\pi(i),\pi(j))\;|\;(i,j)\in H\}$ ein Halbsystem. Die Multiplikativität der Signums-Abbildung folgt aus der Gleichungskette
\begin{align*}\mathrm{sign}(\sigma\pi)&=
\prod_{(i,j)\in H}\frac{\sigma\pi(i)-\sigma\pi(j)}{i-j}\\
&=\prod_{(i,j)\in H}\left(\frac{\sigma\pi(i)-\sigma\pi(j)}{\pi(i)-\pi(j)}\cdot
\frac{\pi(i)-\pi(j)}{i-j}\right)\\
&=\left(\prod_{(i,j)\in H}\frac{\sigma\pi(i)-\sigma\pi(j)}{\pi(i)-\pi(j)}\right)\cdot
\left(\prod_{(i,j)\in H}\frac{\pi(i)-\pi(j)}{i-j}\right)\\
&=\left(\prod_{(k,l)\in
\pi(H)}\frac{\sigma(k)-\sigma(l)}{k-l}\right)\cdot
\left(\prod_{(i,j)\in H}\frac{\pi(i)-\pi(j)}{i-j}\right)\\
&=\mathrm{sign}(\sigma)\cdot \mathrm{sign}(\pi).
\end{align*} Ist $\tau=(k,l)$ eine Transposition, so müssen wir zur Bestimmung von $sign(\tau)$ die Anzahl $a(\tau)$ der Fehlstellen zählen, das heißt die Zahl der Paare $(i,j)$ mit $i \lt j$ und $\tau(i)\gt\tau(j)$. Wir nehmen $k \lt l$ an. Dann ist das Paar $(i,j)=(k,l)$ schon mal eine Fehlstelle. Andere Fehlstellen treten nur paarweise auf: Für $k \lt m \lt l$ ist sowohl $(k,m)$ als auch $(m,l)$ jeweils eine Fehlstelle. Weitere Fehlstellen gibt es nicht. Also ist die Anzahl von Fehlstellen ungerade und die Behauptung bewiesen.
qed