Elementare Kombinatorik/Binomialkoeffizienten/N/Einführung/Textabschnitt
Die Anzahl der -elementigen Teilmengen in einer -elementigen Menge ist
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 .
Der Satz beinhaltet, dass ein Teiler von ist und somit ist der Bruch eine natürliche Zahl. Diese bekommt einen eigenen Namen und ein eigenes Symbol.
Es seien und natürliche Zahlen mit . Dann nennt man
den Binomialkoeffizienten „ über “.
Für die Binomialkoeffizienten gilt die Regel
wie unmittelbar aus der Definition folgt. Dies kann man sich auch mit Hilfe von Fakt klar machen. Die Komplementabbildung
auf einer -elementigen Menge ist bijektiv und bildet -elementige Teilmengen auf -elementige Teilmengen ab.
Den Binomialkoeffizienten kann man auch als
schreiben, da die Faktoren aus auch in vorkommen und daher kürzbar sind. In dieser Darstellung stehen im Zähler und im Nenner gleich viele Faktoren. Gelegentlich ist es sinnvoll, auch negative oder zuzulassen und in diesen Fällen die Binomialkoeffizienten gleich zu setzen. Dies passt zur Interpretation in Fakt.
In der vierelementigen Menge gibt es
zweielementige Teilmengen. Diese sind
In einer -elementigen Menge gibt es genau
-elementige Teilmengen. Es gibt also so viele mögliche Zahlenkombinationen beim Lotto „Sechs aus 49 “. Der Kehrwert von dieser Zahl ist die Wahrscheinlichkeit, beim Lotto sechs Richtige zu haben. Es werden dabei die Teilmengen gezählt, nicht die möglichen Ziehreihenfolgen. Die Anzahl der möglichen Ziehreihenfolgen ist
zu jeder sechselementigen Teilmenge gibt es mögliche Ziehreihenfolgen die auf diese Teilmenge führen.
Wir geben noch einen zweiten Beweis für diese Aussage, der sich an der inhaltlichen Beschreibung der Binomialkoeffizienten als Teilmengenanzahl orientiert.
Es sei eine -elementige Menge und ein fixiertes Element. Nach Fakt ist die Anzahl der -elementigen Teilmengen von gleich . Eine solche Teilmenge enthält entweder oder aber nicht. Im ersten Fall entspricht dann eine solche Teilmenge einer -elementigen Teilmenge von , das ergibt den Summanden . Im zweiten Fall entspricht eine solche Teilmenge einer -elementigen Teilmenge von , das ergibt den Summanden .