TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 148

Angabe

Wie viele Möglichkeite gibt es, k ununterscheidbare Kugeln auf n unterscheidbare Kästchen zu verteilen, wenn jedes Kästchen beliebig viele Kugeln (einschließlich 0) aufnehmen kann?

Lösungsvorschlag von mnemetz

Ich bin mir nicht so sicher ob das so stimmt :-/ --Mnemetz 15:02, 25. Nov 2005 (CET) ?? = also ich weis nicht leute .. aber normalerweiser steht n fuer die Anzahl der Kugeln .. und k fuer die Anzahl der Loecher oder kaestchen.. aber in diesem beispiel steht k fuer die Anzahl der Kugeln und n fuer die Anzahl der Loecher .. ist es nicht so? .. aber es ist aufjedenfall zu Spät jetzt .. :P

Kombination mit Wiederholung

Es liegt eine sogenannte "Kombination mit Wiederholung" vor. Darunter versteht man ein ungeordnetes k-Tupel $\{a_1,a_2,\mathrm{...},a_k\}$ von nicht notwendigerweise verschiedenen Elementen von A. Also liegt eine k-elementige Multimenge mit Elementen von A vor.

Die Anzahl der Kombinationen mit Wiederholungen sind definiert als:

${}^w{C}_n^k=\left(\begin{array}{c}n+k-1\\ k\end{array}\right)$

"Zeichendekodierung" ;-)

• w steht für Wiederholung
• C steht für Kombinationen
• k steht für die Anzahl der Wiederholungen aus den Elementen der Multimenge A
• n steht für die Anzahl der Permutationen von A

Was versteht man darunter?

• A = $a_1,\mathrm{...}{a}_n$ ... n verschiedene Elemente in der Menge
• Multimenge liegt vor, wenn jedes Element $a_r{k}_r$ Mal vorkommt.

Beweis der Kombination mit Wiederholung

Durch vollständige Induktion:

• Elemente $\{a_1,\mathrm{...},a_n\}$ mit $1\le a_1\le a_2\le \mathrm{...}\le a_k\le n$
• Vollständige Induktion ergibt: $1\le a_1<a_2+1<a_3+1<\mathrm{...}<a_k+(k-1)\le n+(k-1)$
  • Es gilt $a_1=b_1,a_2+1=b_2,\mathrm{...},a_k+(k-1)=b_k$
  • wobei $b_k=a_k+(k-1)$
• ${}^w{C}_n^k=|\{a_1,\mathrm{...},a_k)|1\le a_1\le a_2\le \mathrm{...}\le a_k\le n\}|=|\{b_1,\mathrm{...},b_k)|1\le b_1<b_2<\mathrm{...}<b_k\le n+k-1\}|=$
• ${=}^w{C}_{n+k-1}^k=\left(\begin{array}{c}n+k-1\\ k\end{array}\right)$

QED.

Beispiel

• Anzahl der Kugeln k = 6
• Anzahl der Kästchen n = 3

${}^w{C}_n^k=\left(\begin{array}{c}n+k-1\\ k\end{array}\right)$

${}^w{C}_3^6=\left(\begin{array}{c}6+3-1\\ 3\end{array}\right)=\left(\begin{array}{c}8\\ 3\end{array}\right)=\frac{8\ast 7\ast 6}{3!}=\frac{8\ast 7\ast 6}{1\ast 2\ast 3}=8\ast 7=56$

Es gibt also 56 möglichkeiten, 6 Kugeln in drei Löchern zu platzieren.