TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 183

Aus VoWi
Zur Navigation springen Zur Suche springen

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[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={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[Bearbeiten]

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:

 ^wC_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[Bearbeiten]

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)
  •  ^wC_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 \}| =
  • = ^wC_{n + k -1}^k = \begin{pmatrix} n + k - 1 \\ k \end{pmatrix}

QED.

Beispiel[Bearbeiten]

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

 ^wC_n^k = \begin{pmatrix} n + k - 1 \\ k \end{pmatrix}

 ^wC_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.