Kombination mit Wiederholung

Studium

N = \binom{n+k-1}{k}

Voraussetzung: $n \geq 1,$ $k \in \mathbb{N}_0$

$N$: Anzahl der Möglichkeiten
$n$: Anzahl der verschiedenen Sorten, aus denen gewählt wird
$k$: Anzahl der gewählten Objekte
$\binom{n+k-1}{k}$: Binomialkoeffizient „n+k−1 über k“

Wer k Objekte aus n Sorten wählt, mit Wiederholung und ohne Reihenfolge, hat (n+k−1 über k) Möglichkeiten.

Erklärung

Gezählt werden Multimengen: Aus $n$ Sorten werden $k$ Objekte gewählt, jede Sorte darf beliebig oft vorkommen, und die Reihenfolge spielt keine Rolle. Im Urnenmodell entspricht das $k$ -maligem Ziehen mit Zurücklegen ohne Reihenfolge.

Herleitung (Sterne und Striche): Eine Auswahl wird als Folge aus $k$ Sternen und $n - 1$ Trennstrichen codiert. Die Sterne vor dem ersten Strich gehören zur Sorte $1$ , die zwischen erstem und zweitem Strich zur Sorte $2$ und so weiter. Bei $n = 3$ und $k = 4$ steht etwa $\star\star|\,|\star\star$ für zweimal Sorte $1$ , keinmal Sorte $2$ , zweimal Sorte $3$ . Jede Auswahl entspricht genau einer solchen Folge der Länge $n + k - 1$ . Man muss nur festlegen, welche $k$ Positionen Sterne sind, daher $\binom{n+k-1}{k}$ .

Gleichwertig ist $\binom{n+k-1}{n-1}$ (Positionen der Striche). Im Gegensatz zu $\binom{n}{k}$ darf hier $k > n$ sein.

Die so gezählten Ergebnisse sind im Allgemeinen nicht gleich wahrscheinlich. Für Laplace-Wahrscheinlichkeiten muss man deshalb meist mit geordneten Tupeln ( $n^k$ ) rechnen.

Beispiele

Eine Eisdiele hat $3$ Sorten. Im Becher sind $4$ Kugeln, die Anordnung ist egal:

N = \binom{3 + 4 - 1}{4} = \binom{6}{4} = 15

Zwei gleich aussehende Würfel werden geworfen, notiert wird nur das Augenpaar ohne Reihenfolge ( $n = 6$ , $k = 2$ ):

N = \binom{6 + 2 - 1}{2} = \binom{7}{2} = 21

Kontrolle: $\binom{6}{2} = 15$ Paare mit verschiedenen Augen plus $6$ Pasche ergibt $21$ .

$10$ gleiche Bonbons werden auf $4$ Kinder verteilt, jedes darf leer ausgehen: $\binom{4 + 10 - 1}{10} = \binom{13}{10} = 286$ .

Typische Fehler

$\binom{n}{k}$ verwenden. Das zählt Auswahlen ohne Wiederholung; beim Eis wäre $\binom{3}{4} = 0$ offensichtlich falsch.
$n^k$ verwenden. $3^4 = 81$ zählt geordnete Auswahlen, bei denen „Vanille, dann Schoko“ und „Schoko, dann Vanille“ verschieden sind.
Die $21$ Augenpaare als gleich wahrscheinlich ansehen. Ein Pasch hat die Wahrscheinlichkeit $\frac{1}{36}$ , ein gemischtes Paar $\frac{2}{36}$ , denn es gibt $6^2 = 36$ gleich wahrscheinliche geordnete Ergebnisse.
$n$ und $k$ in $\binom{n+k-1}{k}$ vertauschen. $n$ ist die Zahl der Sorten, $k$ die Zahl der gewählten Objekte.

Kombination mit Wiederholung