Elementare Kombinatorik und der binomische Lehrsatz

Die Zählprinzipien

Die Elemente einer endlichen Menge zu zählen ist die elementarste Operation der Arithmetik, solange sich die Menge Element für Element durchgehen lässt. Sind die Elemente aber die Arten, eine zusammengesetzte Auswahl zu treffen, etwa zehn Bücher in einem Regal anzuordnen oder aus dreißig Personen eine dreiköpfige Vertretung zu wählen, so wird das Aufzählen undurchführbar, und man erhält die Anzahl, indem man die Auswahl in Teile oder in Stufen zerlegt. Die ganze elementare Kombinatorik beruht auf zwei Prinzipien, die aus einer genauen Definition dessen bewiesen werden, was Zählen bedeutet.

Die Elemente einer Menge zählen heißt, sie zu nummerieren: jeder Zahl von $1$ bis $n$ ein Element zuzuordnen, ohne eines zu wiederholen und ohne eines auszulassen. Man sagt, eine Menge $A$ hat $n$ Elemente, wobei $n$ eine natürliche Zahl ist, wenn es eine Bijektion der Menge $\{1, 2, \ldots, n\}$ auf $A$ gibt, das heißt eine Funktion, die verschiedene Zahlen auf verschiedene Elemente abbildet und alle Elemente von $A$ erreicht; die leere Menge hat $0$ Elemente, und eine Menge ist endlich, wenn sie leer ist oder $n$ Elemente hat für eine natürliche Zahl $n$. Bijektionen, ihre Verkettung und ihre Umkehrfunktion werden in der Lektion über Mengen, Relationen und Funktionen untersucht.

Vorausgesetzte Tatsache (Anzahl der Elemente). Ohne Beweis wird vorausgesetzt, dass die Anzahl der Elemente einer endlichen Menge wohldefiniert ist: Eine Menge kann nicht zugleich $m$ Elemente und $n$ Elemente haben, falls $m \neq n$. Ebenso wird vorausgesetzt, dass jede Teilmenge einer endlichen Menge endlich ist.

Beide Tatsachen werden durch Induktion über $n$ bewiesen; die erste ist im Grunde das Schubfachprinzip, nach dem es keine Funktion gibt, die die $n + 1$ Zahlen von $\{1, \ldots, n + 1\}$ auf verschiedene Zahlen von $\{1, \ldots, n\}$ abbildet. Ihre Beweise sind lang und liefern keine Ideen, die später gebraucht werden, und deshalb werden sie vorausgesetzt. Ohne die erste hätte der Ausdruck „die Anzahl der Elemente“ keinen Sinn, und ein kombinatorischer Beweis, der ein und dieselbe Menge auf zwei Arten zählt, könnte nicht schließen, dass die beiden Ergebnisse gleich sind.

Durch Induktion über die Anzahl der Teile überträgt sich die Regel auf jede endliche Anzahl paarweise disjunkter Mengen: Die Vereinigung von $A_1, \ldots, A_r$ mit $n_1, \ldots, n_r$ Elementen hat $n_1 + \cdots + n_r$ Elemente, weil die Vereinigung der ersten $r + 1$ die der ersten $r$ mit der letzten ist, die mit ihnen keine gemeinsamen Elemente hat. Aus ihr folgt die zweite Regel, die die in Stufen getroffenen Auswahlen zählt.

Ebenso überträgt sich die Produktregel durch Induktion über die Anzahl der Stufen auf jede endliche Anzahl von ihnen: Eine Auswahl in $r$ Stufen, die jeweils auf $n_1, n_2, \ldots, n_r$ Arten getroffen werden können, kann auf $n_1 n_2 \cdots n_r$ Arten getroffen werden. Zum Beispiel gibt es im Dezimalsystem, das in der Lektion über Stellenwertsysteme untersucht wurde, $9 \cdot 10 \cdot 10 = 900$ dreistellige Zahlen, weil die erste Ziffer nicht $0$ sein kann und die beiden anderen frei sind. Man beachte, dass die Produktregel verlangt, dass die Anzahl der Möglichkeiten jeder Stufe nicht von der vorherigen Wahl abhängt, auch wenn die Möglichkeiten selbst davon abhängen; ist diese Bedingung verletzt, so unterscheidet man Fälle, in denen sie erfüllt ist, und addiert deren Ergebnisse mit der Summenregel.

Die aufeinanderfolgenden Stufen einer Auswahl stellt man mit einem Baumdiagramm dar: Von einem Anfangspunkt, der Wurzel, gehen so viele Äste aus, wie die erste Stufe Möglichkeiten hat; vom Ende jedes Astes so viele, wie die zweite hat, und so weiter. Jeder Weg von der Wurzel bis zu einem Endpunkt, einem Blatt, ist eine vollständige Auswahl, und die Produktregel zählt die Blätter, ohne sie zu zeichnen.