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

Aus VoWi
Wechseln zu: Navigation, Suche

Wieviele Möglichkeiten gibt es, 23 verschiedengroße Kugeln so zu färben, dass 9 rot, 5 schwarz, 4 blau, 4 grün sind und eine weiß ist?

Lösungansatz von Superlufti[Bearbeiten]

Das schaut wie eine Permutation mit Multimengen aus (siehe Beispiel im Skriptum auf Seite 21 (3 Gläser mit Bier,Bier und Wein)):

also

P=\frac{23!}{9!*5!*4!*4!*1!}=1,03*10^{12}

Lösungansatz von W wallner[Bearbeiten]

Hallo!

Laut Angabe sind es verschiedengroße Kugeln, deshalb kann man IMHO nicht die (auf den ersten Blick naheliegende) Formel für Permutation von Multimengen hernehmen.

Zum einfacheren Verständnis meines Ansatzes erklär ich es vorher mit kleineren Zahlen. Angenommen wir haben 6 verschiedene Kugeln (die wir durch ihre Größe unterscheiden können), und wir wollen 3 davon rot, 2 grün und eine blau färben. Alle 6 Kugeln liegen am Anfang in einem Topf.

Als erstes ziehen wir 3 Kugeln aus dem Topf und färben diese rot. Das ist einen Kombination ohne Wiederholung und wir haben dafür \begin{pmatrix} 6 \\ 3\end{pmatrix} = 20 Möglichkeiten.

Als nächstes wollen wir die 2 Kugeln ziehen, die wir grün färben. Es sind nur mehr 3 Kugeln im Topf, weil wir ja vorher schon 3 entnommen haben. Also haben wir \begin{pmatrix} 3 \\ 2\end{pmatrix} = 3 Möglichkeiten.

Zum Schluss ziehen wir die letzte verbleibende Kugel und färben sie blau. Dafür haben wir \begin{pmatrix} 1 \\ 1\end{pmatrix} = 1 Möglichkeit.

Insgesamt ergibt das \begin{pmatrix} 6 \\ 3\end{pmatrix} * \begin{pmatrix} 3 \\ 2\end{pmatrix} * \begin{pmatrix} 1 \\ 1\end{pmatrix} = 20 * 3 * 1 = 60 verschiedene Möglichkeiten.

Mit den Werten aus der Angabe erhält man 
\begin{pmatrix} 23 \\ 9\end{pmatrix} *
\begin{pmatrix} 14 \\ 5\end{pmatrix} *
\begin{pmatrix} 9 \\ 4\end{pmatrix} *
\begin{pmatrix} 5 \\ 4\end{pmatrix} *
\begin{pmatrix} 1 \\ 1\end{pmatrix} =
sehr sehr viele Möglichkeiten.

Die Reihenfolge in der man die Farben wählt, spielt keine Rolle. Es gilt 
\begin{pmatrix} 23 \\ 9\end{pmatrix} *
\begin{pmatrix} 23-9 \\ 5\end{pmatrix} =
\begin{pmatrix} 23 \\ 5\end{pmatrix} *
\begin{pmatrix} 23-5 \\ 9\end{pmatrix}
.

mfg, --W wallner

Lösungsbemerkung von alex newtron[Bearbeiten]

Sowohl die Lösung von Superlufti als auch die Lösung von W Wallner stimmen. Die Formel für die Permutation einer Multimenge passt insofern, als dass die Reihenfolge der Kugeln innerhalb der Farbe ja keinen Unterschied macht. Die Anzahl der Permutationen erhöht sich z.B. nicht, wenn man die Reihenfolge innerhalb der Farbe rot vertauscht. Wohl aber erhöht sich die Anzahl der Permutationen dadurch, dass man die Reihenfolge von den Farben bestimmen kann. Dies ist analog zu dem Beispiel aus der VO (Anzahl der Reihenfolgen, 2 Gläser Bier, 1 Glas Schnaps, 1 Glas Wein zu trinken = 4!/(2!1!1!) = 12). Die 4 Gläser könnten z.B. alle unterschiedlich groß sein, dennoch ist es m.E. im Resultat nicht unterscheidbar, in welcher Reihenfolge man die Biergläser rot gestrichen (oder getrunken) hat; auch W Wallner verwendet ja das Prinzip, die jeweiligen Kugeln der betreffenden Farbe *gleichzeitig* aus dem Topf zu entnehmen. Die chronologische Abfolge der Entnahme und Färbung der Kugeln innerhalb einer Farbgruppe spielt somit keine Rolle.

Es zeigt sich weiters, dass nach Umformen von den Binomialkoeffizienten von W Wallner in die Form
P=\frac{n!}{k!(n-k!)}
und Ausmultiplizieren derselben sich die Koeffizienten alle dahingehend wegkürzen, sodass man wieder zum Resultat P=\frac{23!}{9!*5!*4!*4!*1!}=1,03*10^{12} gelangt, womit der Ansatz von Superlufti feinstens bewiesen wäre.

Eine andere Möglichkeit wäre natürlich, dass beide Lösungsansätze falsch sind. Wenn die Größe der Kugeln im Endresultat keinen Unterschied macht, stellt sich die Frage, warum in der Angabe explizit auf die Unterscheidbarkeit hingewiesen wurde. Eventuell muss man die chronologische Reihenfolge bzw. Größe der Kugeln doch berücksichtigen, womit eine andere Formel/Ergebnis gesucht ist.

Warum die Kugeln verschieden groß sind (anonyme Anmerkung)[Bearbeiten]

Wenn alle Kugeln gleich groß (also ununterscheidbar) wären, gäbe es nur genau eine Möglichkeit, sie wie angegeben zu färben...

EDIT: das stimmt doch wohl wirklich nicht, 3 ununterscheidbare kugeln könnten trotzdem zb: rot schwarz weiss | schwarz weiss rot ... auf unterschiedliche arten gefärbt werden. nämlich im falle dieser angabe (wenn sie nicht unterscheidbar wären) genau (k1+k2+....+kn)/k1!k2!....kn! mal

EDIT EDIT: Die Anmerkung stimmt sehr wohl, denn drei Kugeln, die man nicht unterscheiden kann, haben keine Reihenfolge. Deshalb macht rot schwarz weiss | schwarz weiss rot keinen Unterschied. Und das ist auch der Grund, warum die unterschiedliche Größe in der Angabe steht.

EDIT EDIT EDIT: Der wesentliche Unterschied ist eher, ob es großRot mittelRot kleinRot oder kleinRot großRot mittelRot ist. Wären alle gleich, würden einfach 3 rote Kugeln dort liegen. Wenn sie verschiedene Farben haben, macht das aber auch bei gleich großen Kugeln einen Unterschied, sie sind ja nicht ununterscheidbar.

Links zu anderen Lösungen des gleichen Beispiels[Bearbeiten]