Binomialkoeffizient/Explizit/Teilmengenanzahl/Fakt/Beweis

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 (deshalb) ${}\{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

${\frac {n!}{k!(n-k)!}}$

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

Zur bewiesenen Aussage