Kombinatorik/Elementar/Einführung/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Definition  

Zu einer natürlichen Zahl nennt man die Zahl

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




Lemma  

Auf einer endlichen Menge mit Elementen

gibt es bijektive Abbildungen von nach .

Beweis  

Wir zeigen etwas allgemeiner, dass es zwischen zwei endlichen Mengen und , die beide Elemente besitzen, bijektive Abbildungen gibt. Dies zeigen wir durch Induktion nach , wobei der Fall klar ist. Die Aussage sei nun für schon bewiesen und es liegen zwei -elementige Mengen und vor. Es sei ein fixiertes Element. Dann gibt es für die Bilder genau Möglichkeiten, nämlich die Anzahl der Menge . Wenn dies festgelegt ist, so entsprechen die bijektiven Abbildungen von nach mit

den bijektiven Abbildungen von nach . Nach Induktionsvoraussetzung gibt es solche bijektiven Abbildungen. Daher ist die Anzahl der bijektiven Abbildungen zwischen und gleich


Gleichbedeutend damit ist, dass es Möglichkeiten, Objekte auf Plätze zu verteilen bzw. Möglichkeiten, eine Menge von Objekten abzuzählen.


Beispiel  

Wir möchten eine vollständige Liste von allen bijektiven Abbildungen von der Menge in die Menge in der Form von Wertetabellen angeben. Wegen

gibt es sechs solche Abbildungen. Es gibt keine natürliche Reihenfolge dieser Abbildungen, dennoch kann man hier mehr oder weniger systematisch vorgehen. Beispielsweise kann man den Wert an der Stelle zuerst festlegen und dann die möglichen Kombinationen für und durchgehen. Dies führt auf die folgenden Wertetabellen.










Definition  

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

den Binomialkoeffizienten über “.

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



Lemma  

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 .



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.


Diesen Bruch 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.

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 einer -elementigen Teilmenge von , das ergibt den Summanden .