Lektion 11.2

Kombinatorik und Binomialkoeffizient

40 min Lesezeit

Nach dieser Lektion kannst du

geordnete und ungeordnete Auswahlen unterscheiden (Permutation, Variation, Kombination),
den Binomialkoeffizienten $\binom{n}{k}$ als Anzahl der $k$ -Teilmengen einer $n$ -Menge deuten,
die Formel $\binom{n}{k} = n! / (k!(n-k)!)$ anwenden und $\binom{n}{k} = \binom{n}{n-k}$ sehen,
den Koeffizienten in der Binomialverteilung als „Anzahl der Trefferpfade“ wiedererkennen.

Drei Bücher auf zwei Plätze im Regal: Die Reihenfolge zählt, $3\cdot 2 = 6$ Möglichkeiten. Drei Bücher, von denen du zwei in die Tasche steckst, ohne Reihenfolge: Das sind weniger, weil „Rot-Blau“ und „Blau-Rot“ dieselbe Tasche sind. Man teilt durch $2$ und erhält $3$ .

Diese Division durch die innere Reihenfolge ist der Binomialkoeffizient. In der Binomialverteilung zählt er, auf wie vielen Pfaden genau $k$ Treffer in $n$ Versuchen stehen.

Vermute zuerst

Aus $\{1,2,3,4\}$ zieht man $2$ Zahlen ohne Beachtung der Reihenfolge, ohne Zurücklegen. Wie viele Paare?

Der Vorfaktor

\binom{n}{k}

P(X=k)

n

= 5

p

= 0,5

a

= 2

b

= 5

Glockenkurve darüberlegen

$P(X = 2)$: 0,3125
$\mu = n \cdot p$: 2,5
$\sigma = \sqrt{n p (1-p)}$: 1,118

Die markierten Säulen gehören zum Ereignis $X = 2$ . Ihre Flächen addiert ergeben $0{,}3125$ . Der Erwartungswert $\mu = 2{,}5$ ist die gestrichelte Linie: Dort liegt der Schwerpunkt des Histogramms.

Ohne den Binomialkoeffizienten wäre jeder Balken nur ein Pfad. Der Koeffizient stapelt alle gleich wahrscheinlichen Anordnungen.

Probier es aus

Bei $n = 5$ , $k = 2$ ist $\binom{5}{2} = 10$ . Zehn Pfade mit genau zwei Treffern, jeder mit Wahrscheinlichkeit $p^2 (1-p)^3$ .
Ändere $n$ . Die Höhe des Balkens bei festem $k$ ändert sich nicht nur wegen $p$ , sondern weil plötzlich mehr Pfade existieren.
Vergleiche $k$ und $n-k$ : Dieselbe Anzahl Pfade, $\binom{n}{k} = \binom{n}{n-k}$ . Die Treffer nur umbenennen in Nieten.

Definition

Zählformeln

Eine Menge mit $n$ Elementen.

Permutationen: alle Anordnungen, $n!$ .
Variationen ohne Wiederholung: geordnete $k$ -Tupel, $n! / (n-k)!$ .
Kombinationen ohne Wiederholung: ungeordnete $k$ -Teilmengen,

$\displaystyle \binom{n}{k} = \frac{n!}{k!\,(n-k)!} = \frac{n\cdot(n-1)\cdots(n-k+1)}{k!}$ .

Es gilt $\binom{n}{k} = \binom{n}{n-k}$ , $\binom{n}{0} = \binom{n}{n} = 1$ , und das Pascalsche Dreieck: $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ .

Mit Wiederholung oder mit Reihenfolge ändert sich die Formel — die Aufgabe muss sagen, ob Reihenfolge zählt und ob zurückgelegt wird.

Schritt für Schritt

$\binom{6}{2}$ ausrechnen

Sechs Leute, zwei Delegierte, ohne Vorsitz.

Geordnet: $6\cdot 5 = 30$ (erst A, dann B, oder umgekehrt).

Schritt 1 von 3

Beispiel

Lotto $6$ aus $49$

Ungeordnet, ohne Wiederholung: $\binom{49}{6}$ .

\binom{49}{6} = 13\,983\,816

Ein Tipp hat also etwa eine Chance von $1$ zu $14$ Millionen, die sechs Richtigen zu treffen (ohne Zusatzzahl). Die Reihenfolge der gezogenen Kugeln spielt für den Tipp keine Rolle, deshalb Kombination, nicht Variation.

Kurz geprüft

Warum steht $k!$ im Nenner von $\binom{n}{k}$ ?

Häufige Fehler

Reihenfolge übersehen

„Zwei von vier Ämtern besetzen, Vorsitz und Stellvertretung“ zählt die Reihenfolge: $4\cdot 3 = 12$ , nicht $\binom{4}{2} = 6$ .

„Zwei von vier in denselben Ausschuss“ zählt sie nicht: $6$ .

Mit Zurücklegen (PIN-Ziffern) ist $10^4$ , nicht $10!$ .

Richtig ist

Drei Fragen: Reihenfolge? Wiederholung? Alles oder nur $k$ ? Dann die passende Formel.

Zusammenfassung

Reihenfolge ja: Permutation / Variation. Reihenfolge nein: Kombination, $\binom{n}{k}$ .
$\binom{n}{k} = n\cdots(n-k+1)/k! = \binom{n}{n-k}$ .
Pascal: eine $k$ -Menge enthält ein festes Element oder nicht.
In $P(X=k) = \binom{n}{k} p^k (1-p)^{n-k}$ zählt der Vorfaktor die Trefferpfade.

Übungen

Aufgabe 1Numerisch

$\binom{5}{2}$ .

Aufgabe 2Numerisch

Auf wie viele Arten kann man $3$ aus $6$ Personen ungeordnet auswählen?

Aufgabe 3Multiple Choice

Die Anzahl der Anordnungen von $5$ verschiedenen Büchern im Regal ist

Aufgabe 4Freitext

Erkläre $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ an einem festen Element $x$ der $n$ -Menge.