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?
{{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[Bearbeiten | Quelltext bearbeiten]
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={} 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[Bearbeiten | Quelltext bearbeiten]
Es liegt eine sogenannte "Kombination mit Wiederholung" vor. Darunter versteht man ein ungeordnetes k-Tupel 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:
"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 = ... n verschiedene Elemente in der Menge
- Multimenge liegt vor, wenn jedes Element Mal vorkommt.
Beweis der Kombination mit Wiederholung[Bearbeiten | Quelltext bearbeiten]
Durch vollständige Induktion:
- Elemente mit
- Vollständige Induktion ergibt:
- Es gilt
- wobei
QED.
Beispiel[Bearbeiten | Quelltext bearbeiten]
- Anzahl der Kugeln k = 6
- Anzahl der Kästchen n = 3
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.