Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil I/Vorlesung 13



Elementare Kombinatorik

In dieser Vorlesung beschäftigen wir uns mit elementarer Kombinatorik, dabei ist ein wichtiges Ziel, die Binomialkoeffizienten einzuführen, um die allgemeine binomische Formel formulieren und beweisen zu können. Die Kombinatorik beschäftigt sich mit dem systematischen Abzählen (Anzahl bestimmen) von endlichen Mengen. Zwei wichtige Prinzipien haben wir schon kennengelernt, nämlich das Additivitätsprinzip für disjunkte Mengen (Satz 8.13) und das Multiplikativitätsprinzip für Produktmengen (Satz 9.4). In der folgenden Aussage bezeichnen wir zu einer Abbildung

zu die Menge

als Urbildmenge zu .


Es seien und endliche Mengen und es sei

eine Abbildung.

Dann gilt

Da jedes Element auf genau ein Element aus abgebildet wird, liegt eine disjunkte Vereinigung

vor. Nach Satz 8.13 ist daher die Gesamtanzahl der Menge gleich der Summe der Anzahlen der disjunkten Teilmengen.




Die Fakultät
Dieses Tanzpaar hat sich schon gefunden. Für die verbliebenen Personen gibt es insgesamt noch Möglichkeiten (Gemälde von Ernst Ludwig Kirchner).

Bei einem Tanzkurs mit Damen und Herren gilt heute beim Schneewalzer Damenwahl, wobei die Damen in der Reihenfolge ihrer Sitzordnung wählen dürfen. Die erste Dame hat Wahlmöglichkeiten, die zweite Möglichkeiten, die dritte Möglichkeiten, u.s.w., die vorletze Dame hat noch zwei Möglichkeiten und für die letzte Dame verbleibt eine Möglichkeit.


Zu einer natürlichen Zahl nennt man die Zahl

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

Es ist . Man setzt . Für kleine erhält man die folgende Wertetabelle.



Auf einer endlichen Menge mit Elementen

gibt es bijektive Abbildungen von nach .

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[1] 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 gibt, Objekte auf Plätze zu verteilen, oder Möglichkeiten, eine Menge von Objekten abzuzählen (durchzunummerieren).


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.










Die Binomialkoeffizienten

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.



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

der Binomialkoeffizient

Insbesondere sind die Binomialkoeffizienten natürliche Zahlen.

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 Lemma 13.3 und nach Satz 9.4 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 .


Für die Binomialkoeffizienten gilt die Regel

wie unmittelbar aus der Definition folgt. Dies kann man sich auch mit Hilfe von Satz 13.6 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 Satz 13.6.


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.


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)).



Die Binomialkoeffizienten

erfüllen die rekursive Beziehung

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 Satz 13.6 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 .




Der binomische Lehrsatz

Die folgende allgemeine binomische Formel oder binomischer Lehrsatz bringt die Addition, die Multiplikation und die Potenzierung in einem kommutativen Halbring und insbesondere für die natürlichen Zahlen miteinander in Beziehung.


Es sei ein kommutativer Halbring und . Ferner sei eine natürliche Zahl.

Dann gilt

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


Den vorstehenden Satz kann man sich auf folgendermaßen klar machen. Beim Ausmultiplizieren von

muss jeder Summand (in jedem Faktor) mit jedem Summanden multipliziert werden. Für jedes Teilprodukt muss man sich bei jedem Faktor entscheiden, ob man den vorderen Summanden oder den hinteren Summanden nimmt. Die einzelnen Produkte haben die Form , wobei die Anzahl der Faktoren ist, bei denen gewählt wurde und die Anzahl der Faktoren ist, bei denen gewählt wurde. Wenn man fixiert, so kann man sich fragen, auf wie viele Arten das Produkt zustande kommen kann. Eine solche Möglichkeit ist dadurch gegeben, dass man unter den Faktoren bestimmt, an welchen von ihnen gewählt wird. Die Anzahl der Möglichkeiten ist also die Anzahl der -elementigen Teilmengen von , also gleich .



Fußnoten
  1. Man kann auch bei beginnen, dann geht es um die Anzahl der Abbildungen von einer leeren Menge in eine leere Menge. Da gibt es in der Tat eine Abbildung, nämlich die leere Abbildung, was auch der Grund ist, warum man setzt.


<< | Kurs:Grundkurs Mathematik (Osnabrück 2016-2017)/Teil I | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)