Übungsaufgaben Binomialkoeffizient

Mit diesen Aufgaben kannst du den Umgang mit dem Binomialkoeffizienten üben. Wie ist er definiert? Wie kann man ihn ohne Taschenrechner berechnen? Wo wird er angewendet?

  1. Wie ist die Fakultät n! einer natürlichen Zahl definiert? Berechne 5! und 6! im Kopf und 9! mit dem Taschenrechner. → Lösung
  2. Wie ist der Binomialkoeffizient \({n\choose k}\) definiert?
  3. Berechne ohne Taschenrechner:
    1. \({5\choose 3}\)
    2. \({8\choose 5}\)
    3. \({6\choose 0}\)
  4. Zeige, dass folgendes gilt:
    1. \({n\choose k} = {n\choose n-k}\)
    2. \({n\choose 2} = \frac{n\cdot(n-1)}2\)
    3. \({n\choose 3}=\frac{n\cdot(n-1)\cdot(n-2)}{1\cdot 2\cdot 3}\)
    4. \({n\choose 4}=\frac{n\cdot(n-1)\cdot(n-2)}{1\cdot 2\cdot 3\cdot 4}\)
    5. \({n\choose k}=\frac{n\cdot(n-1)\cdot\ldots\cdot(n-k+1)}{1\cdot 2\cdot\ldots\cdot k}\) („k Faktoren von oben und k Faktoren von unten“)
  5. Berechne mit Hilfe der Regeln aus der vorigen Aufgabe:
    1. \({9\choose 6}\)
    2. \({14\choose 12}\)
  6. Wie viele verschiedene Möglichkeiten gibt es, aus n Dingen k auszuwählen, und zwar ohne Berücksichtigung der Reihenfolge? Etwas mathematischer gefragt: Wie viele k-elementige Teilmengen hat eine n-elementige Menge? Begründe!
  7. Aus den 24 Schülern der Klasse soll ein fünfköpfiger Ausschuss gebildet werden, der die nächsten Klassenfahrt plant. Wie viele Möglichkeiten gibt es, diesen Ausschuss zusammenzustellen?
  8. Begründe:
    1. Eine n-elementige Menge hat insgesamt \(2^n\) Teilmengen.
    2. \({n\choose 0}+{n\choose 1}+{n\choose 2}\ldots+{n\choose n}=2^n\)
  9. Binomialkoeffizent und Pascalsches Dreieck:
    1. Zeichne ein Pascalsches Dreieck mit fünf Zeilen.
    2. Nach welcher Regel werden die Einträge eines Pascalschen Dreiecks berechnet?
    3. Welcher Zusammenhang besteht zwischen einem Pascalschen Dreieck und den Binomialkoeffizienten?
    4. Formuliere mit Hilfe von 2. und 3. eine Rechenregel für Binomialkoeffizienten.
  10. Welcher Zusammenhang besteht zwischen dem Binomialkoeffizienten und den binomischen Formeln?

Lösungen

Aufgabe 1

Die Fakultät einer Zahl n ist das Produkt der ersten n natürlichen Zahlen:

$$n!=1\cdot 2\cdot 3\cdot…\cdot n$$

Also ist:

  • \(5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120\)
  • \(6!=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6=5!\cdot 6\)

Allgemein gilt für natürliche Zahlen: \(n!=(n-1)!\cdot n\). Mit dieser Regel kann man die Fakultät auch mathematisch definieren, und zwar mit einer induktiven Definition. Man legt fest, dass 0! = 1 sein soll. Und dann definiert man, wie man aus einer gegebenen Fakultät die Fakultät des Nachfolgers bestimmen kann, nämlich als \((n+1)!=n!\cdot (n+1)\). Auf diese Weise ist die Fakultät für jede natürliche Zahl definiert.

Aufgabe 2

Der Binomialkoeffizient \({n\choose k}\) (sprich: „n über k“) ist wie folgt definiert:

$${n\choose k}=\frac{n!}{(n-k)!\cdot k!}$$

Dabei sind n und k natürliche Zahlen wobei \(n\ge k\) gelten soll, damit \(n-k\) nicht negativ ist.

bestimmt die Anzahl der Möglichkeiten, aus n Elementen k auszuwählen, und zwar ohne Berücksichtigung der Reihenfolge und ohne Wiederholung. Wir erklären hier, warum das so ist, wie man ihn berechnet und besprechen einige Rechenregeln. Und am Ende des Artikels verstehen wir sogar, woher dieser etwas sperrige Name kommt.

Definition des Binomialkoeffizienten

Der Binomialkoeffizient \({n\choose k}\) (sprich: „n über k“) ist für natürliche Zahlen n und k definiert als:
$${n\choose k}=\frac{n!}{(n-k)!\cdot k!}$$
Dabei soll \(n\ge k\) sein, da sonst der Ausdruck \((n-k)!\) nicht definiert ist.

Beispiele zur Berechnung des Binomialkoeffizienten

Hier kommen einige Rechenbeispiele:

  1. \({5\choose 3}=\frac{5!}{(5-3)!\cdot 3!}=\frac{120}{2\cdot 3}=20\)
  2. Es ist \({n\choose n}=\frac{n!}{0!\cdot n!}=\frac{n!}{1\cdot n!}=1\). Anschaulich gesprochen gibt es genau eine Möglichkeit, aus n Dingen n auszuwählen.
  3. Es ist \({n\choose 0}=\frac{n!}{(n-0)!\cdot 0!}=\frac{n!}{n!\cdot 1}=1\). Anschaulich gesprochen gibt es genau eine Möglichkeit, aus n Dingen 0 auszuwählen, nämlich die leere Menge.
  4. Außerdem gilt \({n\choose k}={n\choose n-k}\), wie man durch Einsetzen in die Definition leicht feststellt. Im Nenner vertauschen sich nämlich genau die Faktoren. Dies kann man wie folgt plausibel machen: Statt aus n Dingen k auszuwählen, kann ich auch die n−k Dinge festlegen, die ich nicht auswähle.

Rechenregel: Binomialkoeffizient im Kopf berechnen

Mit der folgenden Regel kann man den Binomialkoeffizenten häufig ohne Taschenrechner bestimmen:
$${n\choose k}=\frac{n\cdot(n-1)\cdot\ldots\cdot(n-k+1)}{1\cdot 2\cdot\ldots\cdot k}$$

Anschaulich gesprochen sagt die Regel: Im Zähler stehen k Faktoren „von oben“, und im Nenner stehen k Faktoren „von unten“. Beispiel:

$${8\choose 3}=\frac{8\cdot 7\cdot 6}{1\cdot 2\cdot 3}=8\cdot 7=56$$

Man kann die Regeln auch kombinieren:

$${14\choose 12}={14\choose 2}=\frac{14\cdot 13}{1\cdot 2}=7\cdot 13=91$$

Übrigens kann man bei der Berechnung des Binomialkoeffizienten immer alle Faktoren im Nenner wegkürzen. Es kommt also immer eine natürliche Zahl heraus.

Binomialkoeffizient zählt Teilmengen

Der Binomialkoeffizient \({n\choose k}\) bestimmt die Anzahl der Möglichkeiten, aus n Elementen k auszuwählen – ungeordnet und ohne Wiederholung. Etwas mathematischer ausgedrückt: Eine Menge mit n Elementen hat \({n\choose k}\) k-elementige Teilmengen. Warum ist das so?

Dazu eine Beispielaufgabe: Aus den 24 Schülern der Klasse soll ein fünfköpfiger Ausschuss gebildet werden, der die nächsten Klassenfahrt plant. Wie viele Möglichkeiten gibt es, diesen Ausschuss zusammenzustellen?

Wir stellen uns vor, wir wählen die Schüler der Reihe nach aus. Dafür gibt es
$$24\cdot 23\cdot 22\cdot 21\cdot 20 =\frac{24!}{19!}$$
Möglichkeiten. Dann hätten wir aber die Schüler geordnet ausgewählt und jede Teilmenge vielfach gezählt. Die Auswahl ABCDE soll aber die gleiche sein wie CAEDB. Da man die fünf ausgewählten Schüler auf 5! Arten anordnen kann, müssen wir obiges Ergebnis noch durch 5! teilen und erhalten als Endergebnis:
$$\frac{24!}{19!\cdot 5!}=\frac{24!}{(24-5)!\cdot 5!}={24\choose 5}$$

Zusammenfassend können wir sagen, dass in dem Binomialkoeffizienten
$${n\choose k}=\frac{n!}{(n-k)!\cdot k!}$$
die Fakultäten folgende Bewandtnis haben:

  • n! gibt die Anzahl Möglichkeiten an, alle n Elemente geordnet auszuwählen.
  • k! gibt die Anzahl Möglichkeiten an, die k ausgewählten Elemente untereinander zu vertauschen.
  • (n-k)! gibt die Anzahl Möglichkeiten an, die übrigen n-k Elemente untereinander zu vertauschen.

Insgesamt liefert \({n\choose k}\) die Anzahl Möglichkeiten, aus n Dingen k ungeordnet auszuwählen, und damit die Anzahl k-elementiger Teilmengen einer n-elementigen Menge.

Anzahl Teilmengen gesamt

Wie viele Teilmengen hat eine n-elementige Menge insgesamt? Wenn wir eine Teilmenge zusammenstellen, gehört jedes Element dazu oder nicht – das sind n Entscheidungen mit jeweils zwei Möglichkeiten. Also gibt es insgesamt
$$\underbrace{2\cdot 2\cdot\ldots\cdot 2}_n=2^n$$
Teilmengen einer n-elementigen Menge. Die Anzahl k-elementiger Teilmengen haben wir oben schon als \({n\choose k}\) bestimmt, und da jede Teilmenge zwischen 0 und n Elemente besitzt, haben wir folgende Gleichung hergeleitet:
$${n\choose 0}+{n\choose 1}+{n\choose 2}\ldots+{n\choose n}=2^n$$
Beispiel für n = 3:
$${3\choose 0}+{3\choose 1}+{3\choose 2}+{3\choose 3}=8$$

Pascalsches Dreieck

Wenn wir die Binomialkoeffizienten nach dem folgenden Schema als Dreieck anordnen, stellen wir fest, dass jede Zahl in dem Schema gleich der Summe der beiden Zahlen darüber ist:

$$\begin{array}{c}
{0\choose 0}
\\
{1\choose 0} {1\choose 1}
\\
{2\choose 0} {2\choose 1} {2\choose 2}
\\
{3\choose 0} {3\choose 1} {3\choose 2} {3\choose 3}
\\
{4\choose 0} {4\choose 1} {4\choose 2} {4\choose 3} {4\choose 4}
\end{array}$$

$$\begin{array}{c}
{1}\qquad
\\
{1}\qquad {1}\qquad
\\
{1}\qquad {2}\qquad {1}\qquad
\\
{1}\qquad {3}\qquad {3}\qquad {1}\qquad
\\
{1}\qquad {4}\qquad {6}\qquad {4}\qquad {1}\qquad
\end{array}$$

Das Pascalsche Dreieck stellt also eine Möglichkeit dar, Binomialkoeffizienten schnell zu bestimmen. Es gelten folgende Regeln:

  • In Zeile n des Dreiecks steht in Spalte k der Wert \({n\choose k}\), also die Anzahl aller k-elementigen Teilmengen einer n-elementigen Menge. Dabei beginnt die Nummerierung von Zeilen und Spalten bei 0.
  • Die Zeilensumme der n-ten Zeile ist \(2^n\).
  • Die Zahl an jeder Position des Dreiecks ist die Summe der beiden Zahlen darüber. Diese Regel lässt sich wie folgt als Formel beschreiben:
    $${n\choose k}+{n\choose k+1}={n+1\choose k+1}$$

Pascalsches Dreieck und binomische Formeln

Eine weitere Anwendung erfährt das Pascalsche Dreieck bei den binomischen Formeln. Schauen wir uns einmal die Zeile 2 (die Zählung beginnt bei 0!) des Pascalschen Dreiecks mit den Einträgen 1,2,1 an. Diese Zahlen entsprechen den Koeffizienten der ersten binomischen Formel. Koeffizient ist übrigens der Fachbegriff für die Faktoren vor den Variablen, in der binomischen Formel fettgedruckt dargestellt:
$$(a+b)^2=\mathbf 1a^2+\mathbf 2ab+\mathbf 1b^2$$

Die binomische Formel gibt es auch für höhere Potenzen. In der dritten Potenz sieht sie wie folgt aus, wobei wieder die Koeffizienzen fettgedruckt sind:
$$(a+b)^3=\mathbf 1a^3+\mathbf 3a^2b+\mathbf 3ab^2+\mathbf 1b^3$$
Hier stammen die Koeffizienten aus der dritten Zeile des Pascalschen Dreiecks und sind demzufolge die Binomialkoeffizienten
$${3\choose 0}, {3\choose 1}, {3\choose 2}, {3\choose 3}\text.$$

Diese Regel gibt es auch für alle höheren Potenzen und trägt den Namen „Binomischer Lehrsatz„. Die Koeffizienten stammen dabei aus der n-ten Zeile des Pascalschen Dreiecks:
$$(a+b)^n={n\choose 0}a^nb^0+{n\choose 1}a^{n-1}b^1+{n\choose 2}a^{n-2}b^2+\ldots+{n\choose n-1}a^1b^{n-1}+{n\choose n}a^0b^n$$

Und damit können wir nun auch erklären, warum die Binomialkoeffizienten \(n\choose k\) diesen Namen tragen: weil sie die Koeffizienten im binomischen Lehrsatz darstellen! Und das ist doch ein wunderbarer Abschluss dieses Textes.

Schreibe einen Kommentar