Binomialkoeffizient/Explizit/Teilmengenanzahl/Fakt/Beweis

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

Es sei eine -elementige Menge und 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

Insbesondere ist ein Teiler von und es ist

die Anzahl der -elementigen Teilmengen von .

Zur bewiesenen Aussage