TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 188

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?

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

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

Reaso: Naja man stellt sich die Ausgangssituation hier etwas anders vor. Du kannst dir vorstellen, dass du n unterschiedliche Typen von Kugeln hast (jene die in Fach 1, Fach 2.... Fach n landen) A={$a_{1},...a_{n}$} Aus diesen n ziehst du im Endeffekt k (k entstspricht ja laut Angabe der Anzahl der Kugeln) mal! -> |A|= Anzahl der Fächer= n -> k=Wie oft musst du das ganze Wiederholen!

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.

---

Achtung, Angaben- oder Rechendreher! Lösung stimmt für 3 Kugeln (k) und 6 Kästchen (n). --PSX 00:00, 6. Jan. 2010 (CET) Der Grund ist die verdrehte Angabe. Wie schon ganz oben beschrieben kann man sich das ganze auch anders vorstellen, nämlich dass man k mal aus einer Urne mit n verschiedenen Kugeltypen zieht. Die Lösung ist dann eine Kombination mit Wiederholung, jedoch sind n und k vertauscht.