3.3 Die Fakultät und der Binomialsatz
3.3.1 Fakultät
Definition 3.24 (Fakultät).
Die Funktion ist definiert durch
Die Zahl wird als –Fakultät oder –Faktorielle bezeichnet.
Insbesondere (nämlich per Definition des Produkts) gilt also die rekursive Formel
für alle . Wir werden dieser Funktion in vielen weiteren Funktionen und Ausdrücken begegnen. Sie hat jedoch auch für sich gesehen eine (kombinatorische) Bedeutung.
Lemma 3.25 (Kardinalität der Menge der Permutationen einer endlichen Menge).
Für ist die Kardinalität der Menge der bijektiven Abbildungen (auch Permutationen von genannt).
Intuitiv ausgedrückt gibt es also genau verschiedene Möglichkeiten die Menge zu sortieren oder auch Möglichkeiten für die verschiedenen Reihenfolgen, wenn alle nummerierte Bälle zufällig aus einer Urne gezogen werden.
Bemerkung.
Zu bildet die Menge zusammen mit der Verknüpfung von Elementen eine Gruppe (die symmetrische Gruppe).
Beweis von Lemma 3.25. Wir beweisen die Aussage per Induktion. Für gibt es genau eine (bijektive) Abbildung , was den Induktionsanfang darstellt.
Angenommen die Aussage des Lemmas gilt bereits für ein . Wir betrachten nun eine Permutation von . Falls gilt, so erhalten wir mittels Einschränkung auf eine bijektive Abbildung in . Umgekehrt können wir für jedes eine Fortsetzung mit definieren. Daher wissen wir also per Induktionsannahme, dass es Abbildungen mit gibt. Wir bezeichnen die Menge aller solcher Permutation in mit
so dass .
Die Menge lässt sich wie folgt partitionieren:
für . Wir behaupten nun, dass die Mengen auf der rechten Seite alle Kardinalität haben (für ist dies bereits bekannt, da ). Dies impliziert
und damit nach vollständiger Induktion das Lemma.
Sei fix und sei die bijektive Abbildung, die und vertauscht und sonst wirkungslos ist, das heisst, die Abbildung
Falls nun die Eigenschaft hat, dann bildet das Element auf ab. Die Abbildung
ist somit wohldefiniert. Sie ist auch bijektiv, da die Abbildung
eine Inverse darstellt. (Wieso?) Dies beweist die obige Behauptung, was den Beweis des Induktionsschritts abschliesst. □
3.3.2 Binomialkoeffizienten
Für mit definieren wir den Binomialkoeffizienten , als „ über “ ausgesprochen, durch
Ersetzen wir bei gleichbleibendem im Binomialkoeffizienten durch , so vertauschen sich bloss die beiden Ausdrücke im Nenner und wir erhalten
für alle mit .
Proposition 3.26 (Additionseigenschaft der Binomialkoeffizienten).
Für alle mit gilt und
Insbesondere ist für alle mit .
Beweis.Wir verwenden die Definition der Binomialkoeffizienten und erhalten
sowie
durch Erweiterung mit beziehungsweise .
Die letzte Aussage ergibt sich aus den ersten beiden Aussagen und Induktion nach . In der Tat entsteht die jeweils nächste Zeile im Pascal Dreieck (siehe Bild 3.2), indem man an den Rändern jeweils eine und dazwischen die Summen aus der vorherigen Zeile niederschreibt. □
Wichtige Übung 3.27 (Kombinatorische Bedeutung der Binomialkoeffizienten).
Beweisen Sie, dass die Zahl für mit die möglichen Resultate bei der Auswahl einer -elementigen Teilmenge von darstellt. Formaler ausgedrückt: Zeigen Sie, dass es genau Teilmengen von gibt, die Elemente besitzen. Berechnen Sie (beziehungsweise falls Sie aus Deutschland stammen oder falls Sie aus Österreich stammen).
Obige kombinatorische Bedeutung liefert sowohl eine Interpretation als auch einen kombinatorischen Beweis von (3.3): Angenommen wir haben Bälle mit den Zahlen bis beschriftet, doch hat der letzte Ball die Farbe rot und alle anderen die Farbe blau. Sei nun . Für jede der Möglichkeiten Bälle aus den Bällen auszuwählen fällt nun zuerst auf, ob der rote Ball ausgewählt wurde oder nicht. In dem ersten Fall haben wir den roten Ball gemeinsam mit einer der Auswahlmöglickeiten für Bälle aus den blauen Bällen. Im zweiten Fall sehen wir eine der Auswahlmöglichkeiten für Bälle aus den blauen Bällen. Dies definiert also eine Bijektion zwischen den Auswahlmöglichkeiten für aus und der (disjunkten) Vereinigung der Auswahlmöglichkeiten für aus und den Auswahlmöglichkeiten für aus , wodurch (3.3) nochmals bewiesen wird.
3.3.3 Der binomische Lehrsatz
Die Geschichte des binomischen Lehrsatz ist zum einen ziemlich verzweigt und zum anderen ziemlich lang. Die erste Formulierung eines Spezialfalls des binomischen Lehrsatzes wird bereits Euklid zugeschrieben. Der binomische Lehrsatz und die Binomialkoeffizienten waren den Hindus im ersten Jahrtausend vermutlich bekannt, die erste, relativ exakte Formulierung geht wahrscheinlich auf den persischen Mathematiker Al-Karaji zurück, der den Lehrsatz mit einer groben Variante von vollständiger Induktion bewies. Wir verweisen unter anderem auf [?] für mehr Details.
Beweis des binomischen Lehrsatzes. Wir verwenden vollständige Induktion über . Für gilt die Aussage, da
Angenommen die Aussage des Satzes gilt für ein . Dann erhalten wir
unter Verwendung von (zwei) Indexverschiebungen und der Additionsformel (3.3). □
Übung 3.29 (Summe der Binomialkoeffizienten).
Zeigen Sie für jedes die Identitäten
Übung 3.30 (Eine weitere Summe).
Verwenden Sie den binomischen Lehrsatz, um die Identität
für alle zu beweisen. Dies verallgemeinert die erste Aussage aus Übung 3.29, wieso? Können Sie einen kombinatorischen Beweis für diese Aussage finden?
Übung 3.31 (Das Multinomialtheorem).
In dieser Übung möchten wir in Analogie zum binomischen Lehrsatz (Satz 3.28) Ausdrücke der Form für komplexe Zahlen und untersuchen. Wir betrachten dazu sogenannte Multiindizes . Ist ein Multiindex, und , so definieren wir
sowie
Zeigen Sie für alle und das Multinomialgesetz
3.3.4 Summen von Potenzen
In diesem Teilabschnitt wollen wir mit Hilfe des Binomialsatzes Lemma 1.3 für beliebige Potenzen verallgemeinern.
Proposition 3.32 (Summe von Potenzen).
Für jedes gibt es rationale Konstanten , so dass
für alle gilt.
Anders ausgedrückt ist die Summe der -ten Potenzen gleich den Funktionswerten eines Polynoms mit Grad und Leitkoeffizient ausgewertet bei . Wir werden dies im Kapitel 4 verwenden, um Flächeninhalte unter Graphen von Polynomen zu berechnen.
Beweis.Wir behaupten, dass es zu jedem Polynom mit Grad und führendem Koeffizienten ein Polynom mit Grad und führendem Koeffizienten gibt, so dass
für alle gilt. Die Aussage der Proposition ergibt sich aus dieser Behauptung als einfacher Spezialfall. Der Vorteil der verallgemeinerten Behauptung ist, dass wir diese etwas eleganter mittels vollständiger Induktion beweisen können.
Falls ist, so ist konstant, obige Summe ist gleich für das Polynom . Dies ist bereits der Induktionsanfang.
Angenommen wir haben die Behauptung für Polynome vom Grad bereits bewiesen. Wir verwenden nun den Binomialsatz (Satz 3.28) für den Ausdruck
und erhalten
für ein Polynom mit Grad . Auf Grund der Induktionsannahme gibt es ein zugehöriges Polyom mit Grad so dass für alle gilt. Wir summieren nun (3.4) und verwenden eine Teleskopsumme um
und damit auch
für alle zu erhalten. (Wieso sind wir hier nicht schon fertig?)
Sei nun ein beliebiges Polynom mit Grad und führendem Koeffizienten . Dann ist ein Polynom mit Grad . Nach Induktionsannahme gibt es daher ein Polynom mit Grad so dass für alle gilt. Gemeinsam mit Obigem ergibt sich nun
für alle , wobei Grad und führenden Koeffizienten hat. Dies beweist nun den Induktionsschritt und damit auch die Behauptung sowie die Proposition. □
3.3.5 Eine Summe von Binomialkoeffizienten*
In diesem Teilabschnitt diskutieren wir in Kürze eine Summationsformel für Binomialkoeffizienten entlang von Diagonalen im Pascal Dreieck. Insbesondere ergibt sich mit dieser Summationsformel ein anderer Beweis für Proposition 3.32.
Per Definition erzeugen die Funktionen den Vektorraum der Polynome und bilden in der Tat sogar eine Basis von . (Wieso?) Für das Problem in Proposition 3.32 ist diese Basis jedoch nicht besonders gut geeignet. Stattdessen ist die Basis definiert durch
und allgemeiner durch
(3.5) |
für alle deutlich besser dafür geeignet.
Übung 3.33 (Eine besser geeignete Basis).
Zeigen Sie, dass die in Gleichung (3.5) definierten Polynome tatsächlich eine Basis von bilden.
Proposition 3.34 (Summe von Binomialkoeffizienten).
Für jedes ist ein Polynom mit rationalen Koeffizienten vom Grad , welches Leitkoeffizient und Nullstellen besitzt. Für jedes gilt des Weiteren für alle (siehe auch das Bild 3.4) und wir haben die Summenformel
für alle .
Übung 3.35.
Diese Übung liefert einen Beweis zu Proposition 3.34.
- (i)
- Beweisen Sie alle Behauptungen der Proposition bis auf die Summationsformel.
- (ii)
- Beweisen Sie die Summationsformel für alle mit Hilfe von folgendem Bild im Pascal Dreieck (hier für ).
- (iii)
- Beweisen Sie die Summationsformel, indem Sie die Menge aller -elementigen Teilmengen von mit Hilfe des Maximums partitonieren. Sie können auch das Applet 3.36 verwenden.
Applet 3.36 (Kombinatorischer Beweis).
Es wird für kleine Wahlen von und die in obigem kombinatorischem Beweis gefundene Bijektion dargestellt.
Wenn wir auf die sehr befriedigende kombinatorische Interpretation der Summenformel in Proposition 3.34 verzichten wollen, so können wir die Summenformel auch sehr einfach im Pascal-Dreieck sehen und mit Induktion beweisen.
Übung 3.37 (Summe der Binomialkoeffizienten mittels Induktion).
Beweisen Sie die letzte Aussage in Proposition 3.34 mittels vollständiger Induktion.
Übung 3.38.
Beweisen Sie Proposition 3.32 mit vollständiger Induktion wie folgt:
- (i)
- Zeigen Sie, dass
für gewisse und alle gilt.
- (ii)
- Verwenden Sie Proposition 3.34 für die linke Seite von (i) und multiplizieren Sie aus.
- (iii)
- Verwenden Sie nun die Induktionsannahme um den Beweis abzuschliessen.