Exercise:
Zeigen Sie: Für n in mathbbN ist n! die Kardinalität der Menge mathcalS_n der bijektiven Abbildung sigma: ...n rightarrow ...n auch Permutationen von ...n genannt.

Solution:
Intuitiv ausgedrückt gibt es also genau n! verschiedene Möglichkeiten die Menge ...n zu sortieren oder auch n! Möglichkeiten für die verschiedenen Reihenfolgen wenn alle n nummerierte Bälle zufällig aus einer Urne gezogen werden. Beweis per Induktion: Induktionsverankerung: bf n: Es gibt genau eine bijektive Abbildung rightarrow bf Induktionsschritt: Angenommen die Aussage gilt bereits für n in mathbbN bf Induktionsannahme. Man betrachtet nun eine Permutation sigma von ...n+. Falls sigma n+ n+ gilt so erhält man mittels Einschränkung auf ...n eine bijektive Abbildung overlinesigma :k in ...n rightarrow ...n in mathcalS_n. Umgekehrt kann man für jedes simga overlinesigma in mathcalS_n eine Fortsetzung overlinesigma in mathcalS_n+ mit sigma n+ n+ definieren. Daher weiss man also per Induktionsannahme dass es n! Abbildungen sigma n+ mit sigma n+ n+ gibt. Man bezeichne die Menge aller solchen Permutationen in mathcalS_n+ mit H overlinesigma in mathcalS_n+ | sigma n+ n+ s.d. |H|n! Die Menge mathcalS_n+ lässt sich wie folgt partitionieren mathcalS_n+ bigsqcup^n+_k P_k textmit P_k tau in mathcalS_n+| tau n+ k für k ...n+. Man behauptet nun dass die Mengen P_k auf der rechten Seite alle Kardinalität n! haben für kn+ bereits bekannt da P_n+H. Dies impliziert |mathcalS_n+| n! n+ n+! und damit das Lemma. Sei k in ...n fix und sei delta_k : ...n+ rightarrow ...n+ die bijektive Abbildung die k und n+ vertauscht und sonst wirkungslos ist das heisst die Abbildung delta_k : ...n+rightarrow ...n+ cases kquad textfalls l n+ n+quad textfalls l k lquad textfalls l notin kn+ cases Falls nun tau in mathcalS_n+ die Eigenschaft tau n+k hat dann bildet sigma delta_k circ tau in mathcalS_n+ das Element n+ auf n+ ab. Die Abbildung Phi : tau in P_k mapsto delta_k circ tau in H sigma in mathcalS_n+ | sigma n+ n+ ist somit wohldefiniert. Sie ist auch bijektiv da die Abbildung sigma in H P_n+ mapsto delta_k circ sigma tau in P_k eine Inverse darstellt. Dies beweist die obige Behauptung was den Beweis des Induktionsschritts abschliesst.