• Startseite
• Inhalt
• Index

Binomialkoeffizient

Symmetrie der Binomialkoeffizienten

Ganzzahlige Binomialkoeffizienten sind symmetrisch, wenn alle n und k nichtnegativ sind.

Beweis:

Wir berechnen ganz normal das Binom:

Weiter ausrechnen im Nenner ergibt:

Der rechte Term ist der bereits bekannte Binom, der bewiesen werden sollte.

Geschlossene Darstellung des Binomialkoeffizienten (Proposition)

Wir sehen auf den ersten Blick, der erste Faktor im Nenner (n-k) wird um so kleiner je größer k wird.

Beweis:

Natürlich muss der Binomialkoeffizient ein Pascalsche Dreieck bilden. Deshalb sind alle anomalen Konstellationen ausgeschlossen.

n muss größer oder gleich 0 sein und k muss sich zwischen 0 und n (einschließlich) befinden:

Die Ränder des Pascalschen Dreiecks müssen ausschließlich aus Einsen bestehen, ansonsten liegt ein Fehler vor und die obige Formel ist falsch.

Linker Rand

Beginne ich nun mit dem linken Rand, also dem Fall k = 0. Das ergibt eingesetzt:

Denkt daran: 0! = 1.

Induktionsannahme:

Induktionsschritt:

n wird um 1 vergrößert, was oben in die Klammer der Induktionsannahme geschrieben wird.

Jetzt wird das ausgerechnet nach der Formel aus der Definition des Binomialkoeffizienten. Die Position von n über k ergibt sich immer als Summe der beiden darüber befindlichen Zahlen. Dazu geht man eine Zeile zurück n - 1 und beim ersten Term eine Spalte nach links k -1. Die beiden Zahlen, die sich an der Spaltenposition k - 1 und k befinden, werden addiert.

Diese Formel können wir so nicht gebrauchen. Deshalb formen wir sie um. Wir gehen in die nächste Zeile. Die Zahl an der Spaltenposition k wird gebildet als Summe aus der Zahl der vorherigen Zeile n und der Spaltenposition k -1 (also links neben k) und der Spaltenposition k (also direkt darüber).

In diese umgeformte Formel setzen wir nun für k eine 0 ein. Das soll die Spalte ganz links am äußeren Rand des Pascalschen Dreiecks sein.

Rechnung: Ein negatives k ergibt 0. Ein k = 0 ergibt 1.

Rechter Rand

Der Beweis für die 1 auf dem rechten Rand erfolgt durch Einsetzen von n in die Binomialklammer:

Induktionsannahme:

Induktionsschritt:

Wir erhöhen jedes n um 1. Das setzen wird in die folgende Formel ein, die wir schon kennen:

Statt des k setzen wir n + 1 ein, was diese Formel ergibt:

Ausgerechnet sieht das so aus:

Rechnung:

Gleiches n ergibt 1. Das hätten wir schon bei (n +1) über (n + 1) ersehen können.

Ist der untere Wert größer als der obere Wert ergibt das 0.

Beweis für n = 2

Einsetzen von n = 2 und k =1 in den Binomialkoeffizienten ergibt:

Rechnung:

Denkt an

Man kann auch in die Werte in den Bruch einsetzen:

Beweis für n + 1

Wir brauchen nur die Formel mit dem n + 1

benutzen. Umgestellt sieht sie so aus:

In der linken Klammer steht n + 1. Das ist gleich der Summe der beiden rechten Klammern. Statt der rechten Klammern werden nun die Brüche benutzt und die entsprechenden Werte von n und k eingesetzt. Bei der zweiten Klammer wird das obere Element mit dem Ausrufezeichen versehen. Die Differenz des oberen und unteren Elements sieht so aus:

n – (k – 1) = n – k + 1. Dahinter wird das Ausrufezeichen der Fakultät gesetzt.

Der Bruch wird auf den Hauptnenner gebracht. Das ist nicht so einfach mit den Fakultäten. Mit ihnen zu rechnen ist sehr ungewohnt. Der Hauptnenner ist (n – k + 1)! k!

Um dahin zu kommen, müssen wir die Terme gehörig umformen und geschickt die Fakultätsgesetze nutzen.

Erweitern des ersten Summanden mit (n – k + 1)

Erweitern des zweiten Summanden mit k

Anwenden der Umformungsregel, dass das Fakultätszeichen auf den nächsten Nachfolger einer Fakultät übertragen werden kann.

Der nächste Nachfolger von n! ist (n + 1). Hierhin wird jetzt das Ausrufezeichen gesetzt. Alle anderen Faktoren davor entfallen dann. Das Ausrufezeichen bedeutet ja, dass alle Faktoren von 1 bis n + 1 gebildet werden soll, wenn man (n + 1)! Schreibt.

Beispiel

8! (8+1) = (8+1)! = 9!

(8 + 1) ist der nächste Nachfolger von 8.

Allgemein gesprochen:

Bei dem Ausdruck (n – k) ist der der nächste Nachfolger (n – k + 1). Das Fakultätszeichen wird nun auf diesen Nachfolger übertragen.

(n – k)! (n – k + 1) = (n – k + 1)!

Es ist ganz egal, was vor dem Ausrufezeichen steht. Der nächste Nachfolger muss nur um 1 größer sein, um das Ausrufezeichen zu kriegen.

Bei dem ersten Summanden ändern wir den Nenner. Das Ausrufezeichen soll an den nächsten Nachfolger der Fakultät (n – k)! gesetzt werden, was (n – k + 1)! ergibt.

Die geschweifte Klammer soll den Part des „verschobenen” Fakultätszeichens hervorheben.

Nun soll der zweite Summand umgeformt werden. Auch hier wird die Nachfolgerregel benutzt. Wir brauchen zu dem Ausdruck (k – 1)! einen geeigneten Nachfolger. Das ist natürlich k, denn (k – 1) befindet sich bekanntlich vor k.

Aus (n – 1)! k wird dann k!

Die geschweifte Klammer soll den Part des „verschobenen“ Fakultätszeichens hervorheben.

Hauptnenner:

Der Hauptnenner ist (n – k + 1)! k!

Nun schreibe ich die beiden Summanden mit dem Hauptnenner nebeneinander.

Ausrechnen ergibt:

Das kann man leicht k! ausklammern:

Kinderleicht addieren:

Die Nachfolgerregel anwenden n! (n +1) = (n + 1)!

Das ist es, was wir beweisen wollten. Das n ist im Zähler und Nenner um 1 größer, ansonsten ist der Ausgangsbruch erhalten geblieben.

Aus und Einsetzen von n + 1 in n

wurde

Das sollte bewiesen werden, und es wurde bewiesen.

Kombinatorik

Wichtig! Ihr müsst die Darstellung der Position in einer Tabelle lernen. Sie ist ziemlich einfach zu begreifen, wenn ihr euch klar macht, was eine Zeile und was eine Spalte ist.

Nun zeichne ich mal eine kleine Tabelle. In der Tabelle habe ich links die Zeilen-Nummern und rechts die Spalten-Nummern hingeschrieben. Nur eine einzige Zahl, die 6, habe ich zur Demonstration in das Tabellenblatt geschrieben, damit ihr sofort seht, wie ihre Position bestimmt wird.

Die Zeilen-Nummer und Spalten-Nummer beginnen mit 0. Bitte darauf achten.

Die Zahl 3 befindet sich in Zeile 3 und Spalte 1. Das ist ihre Position in der Tabelle. Man beginnt immer mit der Zeilenangabe.

Die Position kann man einfach mit zwei Indizes beschreiben:

Der Buchstabe ist die Abkürzung für das Wort Position. Der erste Index 3 bezieht sich auf die Zeile. Der zweite Index 1 bezieht sich auch die Spalte.

Das Komma trennt hier die Zeilenangabe von der Spaltenangabe. Es handelt sich hier nicht um eine Dezimalzahl!

Mathematiker lieben Verallgemeinerungen, weshalb die Position allgemein so ausgedrückt werden kann:

Die Variable symbolisiert die Zeilen-Nummer. Die Variable daneben symbolisiert dann die Spalten-Nummer.

Man kann die Position auch mit einem anderen mathematischen Symbol darstellen:

Die Klammer mit den beiden Variablen und heißt Binomialkoeffizient. Der Begriff „bi” bedeutet „zwei“. Der Begriff „nomial“ deutet auf irgendwelche Bezeichnungen („Namen”) hin. Hier sind es die Variablen mit dem Namen und , die die Position eindeutig bestimmen. Oben seht ihr die Zeilenangabe und darunter die Spaltenangabe. Sie entsprechen den Indizes bei .

Die beiden Variablen kann man beliebig verändern, um eine andere Position in der Tabelle anzugeben.

Wollt ihr zur nächsten Spalte „wandern“, schreibt ihr:

Der Term bedeutet also „nächste Spalte”, eine Spalte weiter nach rechts.

Nun wird es ein wenig schwieriger. Wollt ihr zur nächsten Zeile und zur nächsten Spalte „wandern“, schreibt ihr:

Der Term n+1 bedeutet also „nächste Zeile“, eine Zeile runter. Die Bedeutung des Terms k+1 kennt ihr bereits.

Das war jetzt keine Spielerei mit Variablen, sondern führt zu dem abstrakten Kapitel des Binomialkoeffizienten. Wenn ihr euch immer vergegenwärtigt, was das mit dem n und k auf sich hat, dann werdet ihr dieses Kapitel auch verstehen.

Übung:

Bestimmt die Position der Zahl 6 in der Tabelle.

Lösung:

Das war jetzt doch zu einfach.

Übung:

Entwickelt die Positionsbestimmung aus der Schreibweise n+1 und k+1.

Lösung:

Die alte Position war Zeile n=3 und Spalte k=1. Die neue Position ist nun die neue Zeile n+1 = 4 und die neue Spalte k+1 = 2.

Wenn altes n = 3 und altes k = 1, dann ist die neue Position:

Ihr brauchtet statt der beiden Variablen nur die beiden festen Zahlen einsetzen und erhieltet so die neue Position 6.

Erinnert euch immer wieder daran, was n und k bedeuten, nämlich die Angabe der Zeilen-Nummer und der Spalten-Nummer, und stellt euch das vor eurem inneren Auge vor, was in der Tabelle passiert.

Man kann mit Hilfe der Positionsangaben auch Summen bilden.

Die beiden Zahlen 3, die nebeneinander liegen, sollen addiert werden, d.h. die Zahl 3 an der Position und die Zahl 3 an der Position sollen addiert. Dann soll die Summe an die Position geschrieben werden. Das ergibt 3 + 3 = 6.

Die Bildung der Summe über die Index-Position ist schwer zu überblicken.

In der Binomialschreibweise ist die Summenbildung viel einfacher zu durchschauen.

An der Position befindet sich die Zahl 6.

In der allgemeinen Schreibweise sieht das übersichtlicher aus.

Position der ersten Zahl:

Das ist die Ausgangsposition.

Position der zweiten Zahl:

Die zweite Zahl befindet sich also rechts neben der ersten Zahl.

Position der Summe:

Von der Ausgangsposition aus befindet sich die Summe in der nächsten Zeile und nächsten Spalte.

Schreibung als Binomialkoeffizienten:

Die Ausgangsposition der ersten Zahl ist die Zeile und die Spalte . Die zweite Zahl befindet sich rechts daneben, also eine Spalte weiter. Die Summe ist in der nächsten Zeile in der Spalte der zweiten Zahl lokalisiert.

Pascalsches Dreieck

Die Einführung in die Positionsbeschreibung von Tabelleneinträgen könnt ihr jetzt für das Pascalsche Dreieck gebrauchen. Dort werden viele Zahlen aufgelistet, die nach einer bestimmten Regel gebildet werden. Diese Regel stelle ich später vor. Erst mal geht es um die Positionsbestimmung der jeweiligen Zahlen.

Pascalsches Dreieck mit den Zahlen

Positionen der Zahlen im Pascalschen Dreieck

Das kommt euch sicherlich bekannt vor. Oben in der Klammer steht die Zeilenangabe. Darunter befindet sich die Spaltenangabe.

ist die Position in der nullten Zeile und nullten Spalte. Die Zahl an dieser Position, der Spitze dieses Dreiecks, ist immer 1.

Beim Pascalschen Dreieck haben die äußeren Zahlen den Wert 1. Ihre Positionen haben den Spaltenindex (linke Seite des Dreiecks). Die Positionen an der rechten Seite des Dreiecks haben ebenfalls den Wert 1. Ihre Position erkennt ihr daran, dass ist, die Zeilen- und Spaltenangabe ist also gleich.

Die übrigen Zahlen sind Summen und zwar die Summen aus den jeweils darüber liegenden Zahlen, wie dies die Pfeile zeigen.

Summenbildung im Pascalschen Dreieck

Übersichtlichere Darstellung der Summenbildung

Hier könnt ihr schön die Summenbildung nachvollziehen, zwei Zahlen addieren und die Summe unter die zweite Zahl bringen. Das geht alles nach der bereits bekannten Formel

Berechnung des Binomialkoeffizienten

Fakultät

Die Fakultät ist eine besondere Art der Multiplikation. Die Faktoren sind hierbei jeweils um 1 größer als ihr Nachbarfaktor. Das mathematische Zeichen ist ein Ausrufezeichen.

Umgekehrt kann man auch die Faktoren absteigend schreiben.

Allgemein kann man die absteigenden Faktoren so formulieren:

Beispiel

Setzt hier für die Variable n die 5 sein. Die Differenz ergibt die Zahl über der geschweiften Klammer. Der letzte Faktor 1 würde 0 ergeben, wenn er nicht um 1 korrigiert würde.

Rechenkniffe

Die nullte Fakultät 0! hat immer den Wert 1. Das erscheint auf den ersten Blick seltsam. Es ist eine reine Definitionssache, übrigens eine sehr nützliche.

Das Ausrufezeichen kann man von oben nach unten verschieben. Es kann vom größten Faktor wandern zu den kleineren Faktoren oder umgekehrt.

Beispiel

Das Ausrufezeichen wurde zum kleineren Faktor 4 hinbewegt. Die Fakultät von

Macht euch klar, dass (n - 1) der Vorgängerfaktor von n ist. Analog ist (n - 2) der Vorvorgängerfaktor von n.

Richtig schwierig wird es, wenn bei der Fakultät die Differenz aus zwei Variablen besteht. In diesem Fall konzentriert euch auf die Differenz und zieht 1 ab. Dann habt ihr den Vorgängerfaktor.

Ausgangsfaktor: (n - k)

Vorgängerfaktor: (n - k - 1)

Vorgängerfakultät: (n - k - 1)!

Übung:

(n - k) (n - k - 1)! = ?

Lösung:

Durch Verschieben des Ausrufezeichens nach links zum „Ausgangsfaktor“ verschwindet die Vorgängerfakultät.

Dieser Rechenkniff ist wichtig bei Beweisen.

Übung:

Verwandelt bei der folgenden Aufgabe die Vorgängerfakultät in ihren „Ausgangsfaktor“.

Lösung:

Erweitern mit (n - k) ergibt:

Im Nenner ergibt die Verschiebung des Ausrufezeichens bei der Vorgängerfakultät (n - k -1)! nach links zu (n - k):

Der Nenner konnte durch Verschieben des Ausrufezeichens in eine neue Fakultät verwandelt werden. Beim Zähler ist dies nicht möglich.

Ausklammern von Fakultäten

Ausdrücke mit Fakultätszeichen können wie „normale“ Variablen ausgeklammert werden.

Übung:

Klammert bei der folgenden Summe die Fakultät (n -1)! aus.

(n - 1)! k + (n - 1)! (n - k) = ?

Lösung:

Damit ihr die auszuklammernden Terme optisch leichter erkennt, habe ich die Fakultät durch einen Smiley ersetzt.

Faktorisieren des Smileys:

Ersetzen des Smileys durch den ursprünglichen Term ergibt:

Ausrechnen:

Das ist das Ergebnis nach der Verschiebung des Ausrufezeichens.