Verteilung von Kugeln auf Urnen

Studium

\#\{(x_1, \ldots, x_n) \in \mathbb{N}^n : x_1 + \ldots + x_n = k\} = \binom{k-1}{n-1}

Voraussetzung: $n, k \in \mathbb{N},$ $1 \leq n \leq k;$ $Kugeln gleich, Urnen unterscheidbar, keine Urne leer$

$k$: Anzahl der gleichen (nicht unterscheidbaren) Kugeln
$n$: Anzahl der unterscheidbaren Urnen
$x_j$: Anzahl der Kugeln in Urne j, mindestens 1
$\binom{k-1}{n-1}$: Binomialkoeffizient, Anzahl der Verteilungen

k gleiche Kugeln lassen sich auf (k−1 über n−1) Arten so auf n Urnen verteilen, dass keine Urne leer bleibt.

Erklärung

Gezählt werden die Möglichkeiten, $k$ gleiche Kugeln auf $n$ unterscheidbare Urnen zu verteilen. Gleichwertig zählt man die Lösungen der Gleichung $x_1 + \ldots + x_n = k$ in ganzen Zahlen. Es gibt zwei Grundfälle:

Bedingung	Anzahl
keine Urne leer, $x_j \geq 1$	$\binom{k-1}{n-1}$
leere Urnen erlaubt, $x_j \geq 0$	$\binom{n+k-1}{n-1} = \binom{n+k-1}{k}$

Sterne und Striche: Man legt die $k$ Kugeln als Sterne in eine Reihe. Zwischen zwei Sternen gibt es $k - 1$ Lücken. Wählt man $n - 1$ dieser Lücken für Trennstriche aus, entstehen $n$ nichtleere Gruppen. Daher $\binom{k-1}{n-1}$ . Für $k < n$ gibt es keine solche Verteilung.

Der zweite Fall ist die Kombination mit Wiederholung. Man führt ihn auf den ersten zurück: Mit $y_j = x_j + 1$ wird aus $x_1 + \ldots + x_n = k$ mit $x_j \geq 0$ die Gleichung $y_1 + \ldots + y_n = k + n$ mit $y_j \geq 1$ .

Allgemeine Mindestanzahlen $x_j \geq u_j$ behandelt man genauso: Zuerst legt man $u_j$ Kugeln in Urne $j$ , dann verteilt man den Rest frei.

Sind die Kugeln dagegen unterscheidbar, gibt es bei erlaubten leeren Urnen $n^k$ Verteilungen, weil jede Kugel ihre Urne einzeln wählt.

Beispiele

Bonbons: $10$ gleiche Bonbons werden auf $4$ Kinder verteilt, jedes bekommt mindestens eins:

\binom{10-1}{4-1} = \binom{9}{3} = 84

Kontrolle: Jedes Kind erhält zuerst ein Bonbon, die restlichen $6$ werden frei verteilt: $\binom{4 + 6 - 1}{6} = \binom{9}{6} = 84$ .

Gleichung: $x_1 + x_2 + x_3 = 7$ hat in positiven ganzen Zahlen $\binom{6}{2} = 15$ Lösungen.

Mit Mindestanzahl: $x_1 + x_2 + x_3 = 10$ mit $x_1 \geq 2$ , $x_2 \geq 0$ , $x_3 \geq 1$ . Nach dem Vorab-Verteilen bleiben $10 - 2 - 1 = 7$ Kugeln, frei auf $3$ Urnen: $\binom{7 + 3 - 1}{3 - 1} = \binom{9}{2} = 36$ .

Typische Fehler

Die beiden Fälle verwechseln. Dürfen Kinder leer ausgehen, sind es bei $10$ Bonbons und $4$ Kindern $\binom{13}{3} = 286$ Möglichkeiten, nicht $84$ .
Unterscheidbare Kugeln mit dieser Formel zählen. Zehn verschiedene Geschenke auf $4$ Kinder ergeben $4^{10} = 1\,048\,576$ Verteilungen, wenn leere Hände erlaubt sind.
Oben $k$ statt $k - 1$ einsetzen. Die Striche stehen in den $k - 1$ Lücken zwischen den Sternen, nicht an den Rändern, sonst entstünden leere Urnen.

Verteilung von Kugeln auf Urnen