Beweis
Es sei
eine
-elementige Menge und
-
![{\displaystyle {}T\subseteq M\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a0d4707f9014812afc656bd6b6c91c5056343b4e)
eine
-elementige Teilmenge. Wir betrachten die Menge aller bijektiven Abbildungen
-
die zusätzlich
auf
(und damit)
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
-
![{\displaystyle {}{\binom {n}{k}}={\frac {n!}{k!(n-k)!}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d841c2893bad914acd6db0e48b57a91dfb1f1b9)
die Anzahl der
-elementigen Teilmengen von
.