Binomialkoeffizient/Lehrsatz/Textabschnitt

Aus Wikiversity


Definition  

Zu einer natürlichen Zahl nennt man die Zahl

die Fakultät von (sprich Fakultät).


Definition  

Es seien und natürliche Zahlen mit . Dann nennt man

den Binomialkoeffizienten über “.

Von der Definition her ist es nicht sofort klar, dass ein Teiler von ist und dass es sich somit bei den Binomialkoeffizienten um natürliche Zahlen handelt. Dies folgt aus der folgenden Beziehung.



Satz  

Die Anzahl der -elementigen Teilmengen in einer -elementigen Menge ist

der Binomialkoeffizient

Insbesondere sind die Binomialkoeffizienten natürliche Zahlen.

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 .


Bemerkung  

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.


Beispiel  

In der vierelementigen Menge gibt es

zweielementige Teilmengen. Diese sind



Beispiel  

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.


Das Dreieck der Binomialkoeffizienten war in Indien und in Persien schon um 1000 bekannt,
in China heißt es Yanghui-Dreieck (nach Yang Hui (um 1238-1298)),
in Europa heißt es das Pascalsche Dreieck (nach Blaise Pascal (1623-1662)).



Lemma  

Die Binomialkoeffizienten

erfüllen die rekursive Beziehung

Beweis  

Es ist


Wir geben noch einen zweiten Beweis für diese Aussage, der sich an der inhaltlichen Beschreibung 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 .

Die folgende allgemeine binomische Formel bringt die Addition und die Multiplikation in einem Körper miteinander in Beziehung.


Satz  

Es seien Elemente in einem Körper. Ferner sei eine natürliche Zahl.

Dann gilt

Beweis  

Wir führen Induktion nach . Für steht einerseits und andererseits . Es sei die Aussage bereits für bewiesen. Dann ist