Kombinatorik
Wie viele vierstellige PINs gibt es? Auf wie viele Arten können 5 Freunde nebeneinander sitzen? Wie viele Lottotipps sind möglich? Die Kombinatorik ist die Kunst des geschickten Zählens.
Das Zählprinzip
Merke
Besteht eine Auswahl aus mehreren Schritten, multiplizierst Du die Anzahlen der Möglichkeiten der einzelnen Schritte.
Beispiel
Du hast 3 T-Shirts, 2 Hosen und 4 Paar Schuhe. Daraus kannst Du $3 \cdot 2 \cdot 4 = 24$ verschiedene Outfits zusammenstellen.
Anordnungen und Fakultät
Auf wie viele Arten können sich 5 Freunde nebeneinander setzen? Für den ersten Platz gibt es 5 Möglichkeiten, für den zweiten noch 4, dann 3, 2 und 1:
Merke
$n!$ (gesprochen „n Fakultät“) ist das Produkt der Zahlen von 1 bis $n$. Es gibt $n!$ Möglichkeiten, $n$ verschiedene Dinge anzuordnen. Außerdem gilt $0! = 1$.
Die Fakultät wächst rasend schnell: $10! = 3{.}628{.}800$ und $20!$ hat schon 19 Stellen.
Das Urnenmodell – vier Fälle
Viele Aufgaben kannst Du Dir als Ziehen von $k$ Kugeln aus einer Urne mit $n$ verschiedenen Kugeln vorstellen. Entscheidend sind zwei Fragen: Kommt es auf die Reihenfolge an? und Wird zurückgelegt?
| mit Zurücklegen | ohne Zurücklegen | |
|---|---|---|
| mit Reihenfolge | $n^k$ | $\dfrac{n!}{(n-k)!}$ |
| ohne Reihenfolge | $\dbinom{n+k-1}{k}$ | $\dbinom{n}{k}$ |
Mit Reihenfolge, mit Zurücklegen: PIN
Jede der 4 Stellen kann eine der 10 Ziffern sein: $10^4 = 10{.}000$ PINs.
Mit Reihenfolge, ohne Zurücklegen: Siegertreppchen
8 Läufer, Plätze 1 bis 3: $8 \cdot 7 \cdot 6 = \frac{8!}{5!} = 336$ Möglichkeiten.
Ohne Reihenfolge, ohne Zurücklegen: Lotto
Beim Lotto „6 aus 49“ ist egal, in welcher Reihenfolge die Zahlen gezogen werden. Wir teilen deshalb die geordneten Möglichkeiten durch die $6!$ Reihenfolgen:
Die Chance auf sechs Richtige ist also 1 zu knapp 14 Millionen.
Ohne Reihenfolge, mit Zurücklegen: Eisbecher
3 Kugeln Eis aus 5 Sorten, Sorten dürfen sich wiederholen, die Reihenfolge im Becher ist egal: $\binom{5+3-1}{3} = \binom{7}{3} = 35$ Becher.
Der Binomialkoeffizient
Merke
Er gibt an, wie viele Möglichkeiten es gibt, $k$ Dinge aus $n$ auszuwählen, wenn die Reihenfolge keine Rolle spielt.
Tipp: schnell rechnen
Kürze vorher: $\binom{10}{3} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120$. Außerdem gilt $\binom{n}{k} = \binom{n}{n-k}$ – also $\binom{10}{7} = \binom{10}{3}$. Und immer: $\binom{n}{0} = \binom{n}{n} = 1$, $\binom{n}{1} = n$.
Die Binomialkoeffizienten findest Du auch im Pascalschen Dreieck – jede Zahl ist die Summe der beiden darüber:
Typischer Fehler
Bei einer Mannschaftsaufstellung „Kapitän und Stellvertreter“ ist die Reihenfolge wichtig ($25 \cdot 24 = 600$), bei „zwei Klassensprecher gleichberechtigt“ nicht ($\binom{25}{2} = 300$). Lies genau!
Online üben
Stufe 2: mit Reihenfolge, ohne Zurücklegen
-
Aufgabe 1
\(\text{Aus 22 Schülern werden Klassensprecher und Stellvertreter gewählt. Wie viele Möglichkeiten?}\)\(\frac{22!}{(22-2)!} = 22 \cdot 21 = 462\)
-
Aufgabe 2
\(\text{7 Läufer – wie viele Möglichkeiten gibt es für die Plätze 1, 2 und 3?}\)\(\frac{7!}{(7-3)!} = 7 \cdot 6 \cdot 5 = 210\)
-
Aufgabe 3
\(\text{Aus 7 verschiedenen Ziffern wird eine 4-stellige Zahl ohne Wiederholung gebildet. Wie viele gibt es?}\)\(\frac{7!}{(7-4)!} = 7 \cdot 6 \cdot 5 \cdot 4 = 840\)
-
Aufgabe 4
\(\text{Aus 5 verschiedenen Ziffern wird eine 3-stellige Zahl ohne Wiederholung gebildet. Wie viele gibt es?}\)\(\frac{5!}{(5-3)!} = 5 \cdot 4 \cdot 3 = 60\)
Online üben: Binomialkoeffizienten
Stufe 1: n bis 6
-
Aufgabe 1
\(\text{„}6\text{ über }2\text{“}\)\(\text{„}6\text{ über }2\text{“} = \frac{6 \cdot 5}{2 \cdot 1} = 15\)
-
Aufgabe 2
\(\text{„}6\text{ über }5\text{“}\)\(\text{„}6\text{ über }5\text{“} = \frac{6}{1} = 6\)
-
Aufgabe 3
\(\text{„}6\text{ über }4\text{“}\)\(\text{„}6\text{ über }4\text{“} = \frac{6 \cdot 5}{2 \cdot 1} = 15\)
-
Aufgabe 4
\(\text{„}3\text{ über }2\text{“}\)\(\text{„}3\text{ über }2\text{“} = \frac{3}{1} = 3\)
-
Aufgabe 5
\(\text{„}4\text{ über }1\text{“}\)\(\text{„}4\text{ über }1\text{“} = \frac{4}{1} = 4\)
-
Aufgabe 6
\(\text{„}4\text{ über }2\text{“}\)\(\text{„}4\text{ über }2\text{“} = \frac{4 \cdot 3}{2 \cdot 1} = 6\)
Arbeitsblatt: Kombinatorik: Wie viele Möglichkeiten?
Bis zu 8 Aufgaben mit Lösungsblatt zum Ausdrucken – bei jedem Klick neue Aufgaben. Klasse 10–12.
Arbeitsblatt: Binomialkoeffizienten berechnen
Bis zu 15 Aufgaben mit Lösungsblatt zum Ausdrucken – bei jedem Klick neue Aufgaben. Klasse 10–12.
Große Zahlen exakt ausrechnen? Der Kombinatorik-Rechner kann alle vier Fälle des Urnenmodells. Weiter geht es mit der Binomialverteilung, in der der Binomialkoeffizient eine wichtige Rolle spielt.
Weiterlesen: Kombinatorik bei Wikipedia