Beweis des Hauptsatzes.

Wir wissen schon: Die Anzahl der Permutation von {1,2,...,n} ist n!

Sei f eine Permutation.

(a) Bilde die Permutationen f⁰, f¹, f², ..., f^n!

(b) Es gibt 0 ≤ i < j ≤ n! mit fⁱ = f^j.

(c) Ist fⁱ = f^j mit 0 < i < j, so auch f^i-1 = f^j-1.

(d) Also gilt f⁰ = f^j-i (mit 0 ≤ i < j).

Zusatz: Wegen j ≤ n!, ist j-i ≤ n!