Anzahl der Permutationen

Sei $M$ eine endliche Menge mit $n$ Elementen. Dann gibt es genau $n!$ ($n$ Fakultät) Bijektionen (Permutationen) von $M$ auf sich selbst.

Der Beweis wird induktiv geführt. Offensichtlich gibt es für eine $1$-elementige Menge genau eine Permutation, die identische Permutation.

Sei $\pi$ eine beliebige Permutation einer $n$-elementigen Menge. Wenn wir uns $\pi$ in Zyklenschreibweise gegeben vorstellen, ist $\pi\circ (n+1)$ sicher eine Permutation einer $(n+1)$-elementigen Menge. Es gibt offensichtlich gleich viele Permutationen dieser Art wie Permutationen mit $n$ Elementen und dies sind nach Induktionsvoraussetzung $n!$.

Sei jetzt $\sigma$ eine beliebige Permutation einer $(n+1)$-elementigen Menge. Dann ist $\sigma= \matrix{{1 \cdots j \cdots {n+1}}{{\sigma(1)} \cdots {n+1} \cdots i}}$ für gewisse $i$ und $j$. Und weiter gilt $(i \, {n+1})\circ \sigma= \matrix{{1 \cdots j \cdots {n+1}}{{\sigma(1)} \cdots {n+1} \cdots i}}=$ $\matrix{{1 \cdots j \cdots {n+1}}{{\sigma(1)} \cdots i \cdots {n+1}}}$ und wir haben die Permutation in die obige Form überführt. Damit gibt es $n+1$ Möglichkeiten Permutationen mit $n+1$ Elementen in Permutationen mit $n$ Elementen zu überführen. Also ist die Anzahl: $(n+1)\cdot n=(n+1)!$. $\qed$