Binomialkoeffizient/Teilmengenanzahl/Fakt/Beweis2

Beweis

Es sei ${}M$ eine ${}n$-elementige Menge und

${}T\subseteq M\,$

eine ${}k$-elementige Teilmenge. Wir betrachten die Menge aller bijektiven Abbildungen

${\{1,\ldots ,n\}}\longrightarrow M,$

die zusätzlich ${}\{1,\ldots ,k\}$ auf ${}T$ (und damit) ${}\{k+1,\ldots ,n\}$ auf ${}M\setminus T$ abbilden. Nach Fakt und nach Fakt gibt es ${}k!\cdot (n-k)!$ solche Abbildungen. Insgesamt gibt es ${}n!$ bijektive Abbildungen von ${}{\{1,\ldots ,n\}}$ nach ${}M$. Daher ist

${}{\left({\text{Anzahl der }}k{\text{-elementigen Teilmengen von }}M\right)}\cdot k!\cdot (n-k)!=n!\,.$

Insbesondere ist ${}k!\cdot (n-k)!$ ein Teiler von ${}n!$ und es ist

${}{\binom {n}{k}}={\frac {n!}{k!(n-k)!}}\,$

die Anzahl der ${}k$-elementigen Teilmengen von ${}M$.

Zur bewiesenen Aussage