Binomialkoeffizient/Explizit/Teilmengenanzahl/Fakt/Beweis

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

Insbesondere ist ein Teiler von und es ist

die Anzahl der -elementigen Teilmengen von .