Beweis
Es sei
eine
-elementige Menge und
eine
-elementige Teilmenge. Wir betrachten die Menge aller bijektiven Abbildungen
-
die zusätzlich
auf
und
(deshalb)
auf
abbilden. Nach
Fakt
und nach
Fakt
gibt es
solche Abbildungen. Insgesamt gibt es
bijektive Abbildungen von
nach
. Daher ist
-
![{\displaystyle {}{\left({\text{Anzahl der }}k{\text{-elementigen Teilmengen von }}M\right)}\cdot k!\cdot (n-k)!=n!\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ed621dec38db218102ac51e249eb6454fec1797)
Insbesondere ist
ein
Teiler
von
und es ist
-
die Anzahl der
-elementigen Teilmengen von
.