Proof of Theorem.

We know already: The number of permutations of {1,2,...,n} is n!

Let f be a permutation.

(a) Consider the permutations f⁰, f¹, f², ..., f^n!

(b) There exist 0 ≤ i < j ≤ n! with fⁱ = f^j.

(c) Is fⁱ = f^j with 0 < i < j, then also f^i-1 = f^j-1.

(d) Therefore f⁰ = f^j-i (and 0 ≤ i < j).

Also: Since j ≤ n!, we have j-i ≤ n!