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},...,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}={\begin{pmatrix}n+k-1\\k\end{pmatrix}}$

"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},...a_{n}$ ... n verschiedene Elemente in der Menge
• Multimenge liegt vor, wenn jedes Element $a_{r}\qquad k_{r}$ Mal vorkommt.

Beweis der Kombination mit Wiederholung

Durch vollständige Induktion:

• Elemente $\{a_{1},...,a_{n}\}$ mit $1\leq a_{1}\leq a_{2}\leq ...\leq a_{k}\leq n$
• Vollständige Induktion ergibt: $1\leq a_{1}<a_{2}+1<a_{3}+1<...<a_{k}+(k-1)\leq n+(k-1)$
  • Es gilt $a_{1}=b_{1},a_{2}+1=b_{2},...,a_{k}+(k-1)=b_{k}$
  • wobei $b_{k}=a_{k}+(k-1)$
• $^{w}C_{n}^{k}=|\{a_{1},...,a_{k})|1\leq a_{1}\leq a_{2}\leq ...\leq a_{k}\leq n\}|=|\{b_{1},...,b_{k})|1\leq b_{1}<b_{2}<...<b_{k}\leq n+k-1\}|=$
• $=^{w}C_{n+k-1}^{k}={\begin{pmatrix}n+k-1\\k\end{pmatrix}}$

QED.

Beispiel

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

$^{w}C_{n}^{k}={\begin{pmatrix}n+k-1\\k\end{pmatrix}}$

$^{w}C_{3}^{6}={\begin{pmatrix}6+3-1\\3\end{pmatrix}}={\begin{pmatrix}8\\3\end{pmatrix}}={\frac {8*7*6}{3!}}={\frac {8*7*6}{1*2*3}}=8*7=56$

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