Wichtelproblem extrem

17.04.2011, 15:47	Limbo	Auf diesen Beitrag antworten »
Wichtelproblem extrem Meine Frage: Liebes Forum Ich wende mich an euch mit einem sehr verzwickten Problem. Das Grundproblem lautet zwar anders, aber ich habe es bereits umgewandelt in etwas "Anschaulicheres": Es dreht sich eigentlich um das Wichtelproblem, wo jeder seinen Namen auf ein Zettel schreibt, in eine Urne wirft, und dann blind wieder ein Zettel zieht. Nur bei meinem Problem bilden m Leute m1 Gruppen. Jede Gruppe erhält einen Zettel und schreibt alle Namen seiner Gruppenmitglieder darauf auf und wirft ihn dann in die Urne. Die Urne wird danach mit leeren Zetteln aufgefüllt bis C Zettel in der Urne sind. Danach lösen sich die Gruppen auf und es bilden sich neue Gruppen. Dieses Mal bilden sich m2 Gruppen. Jede Gruppe zieht dann einen Zettel. Nun suche ich die Wahrscheinlichkeit, dass niemand seinen Namen auf dem Zettel seiner Gruppe findet. Jede Gruppe hat mindestens aus einer Person zu bestehen. Alle Personen haben paarweise verschiedene Namen bzw. Namen sind eindeutig bzw. keine zwei Personen haben die selben Namen. Meine Ideen: Es spielt offensichtlich keine Rolle, ob die Urne mit leeren Zetteln oder mit Zetteln mit anderen Namen darauf aufgefüllt wird, da die anderen Namen nicht interessieren. Ebenso könnte man zu den anderen Namen auch Leute erfinden, die sich irgendwie Gruppieren oder Mischen, da auch diese nicht interessieren. Ich glaube ich habe das Problem für m1=m2=m gelöst. Dort hat jede Gruppe ein Mitglied. Dann kann man noch C-m andere Leute dazu erfinden und man kommt zur Wahrscheinlichkeit, das die ersten m Elemente einer Gruppe mit C Elementen keine Fixpunkte einer Permutation darstellen. Dies konnte ich mit $\begin{eqnarray} A_j = \{ f \in S_n \| f(j) = j \} \end{eqnarray}$ für $\begin{eqnarray} j \in \{1,...,m\} \end{eqnarray}$ und dem Inklusion- Exklusion Prinzip lösen. Doch für das andere Problem fehlt mir ein guter Ansatz.
18.04.2011, 16:32	Limbo	Auf diesen Beitrag antworten »
Ich habe das Problem in Zwischenzeit weiter umgewandelt, vielleicht kommt so jemand weiter. Das Problem könnte auch lauten: $\begin{eqnarray} m \end{eqnarray}$ Philosophen verteilen sich auf $\begin{eqnarray} m_1 \end{eqnarray}$ nicht leere Gruppen. Jede Gruppe geht in ein Zimmer. Pro Zimmer maximal eine Gruppe. Insgesamt stehen $\begin{eqnarray} C \end{eqnarray}$ Zimmer zur Verfügung. Später treffen sich die Philosophen wieder und bilden neue nicht leere Gruppen, dieses Mal jedoch $\begin{eqnarray} m_2 \end{eqnarray}$ Gruppen und verteilen sich zufällig auf die $\begin{eqnarray} C \end{eqnarray}$ Zimmer. Pro Zimmer maximal eine Gruppe. Wie gross ist die Wahrscheinlichkeit, dass ein Philosoph zwei Mal im gleichen Zimmer war? Ich habe bereits herausgefunden, dass es $\begin{eqnarray} S_{m,m_1} \end{eqnarray}$ Möglichkeiten gibt, wie sich die m Philosophen auf $\begin{eqnarray} m_1 \end{eqnarray}$ nicht leere Gruppen aufteilen können. Wobei $\begin{eqnarray} S_{m,m_1} \end{eqnarray}$ die Stirling-Zahlen zweiter Art bezeichnen. Zudem glaube ich, dass es keine Rolle spielt, ob beim ersten beziehen der Zimmer die Gruppen und Zimmer nummeriert sind und die Gruppen in das Zimmer mit der selben Nummer wie die Gruppennummer gehen, da die Zimmer nicht unterscheidbar sind. Also gibt es es $\begin{eqnarray} S_{m,m_1} \end{eqnarray}$ Varianten fürs erste Gruppieren. Dann geht jede Gruppe ins entsprechende Zimmer, kommt wieder raus und es gibt wieder unabhängige Gruppen. Fürs zweite Gruppieren gibt es $\begin{eqnarray} S_{m,m_2} \end{eqnarray}$ Varianten. Dann verteilen sich die Gruppen auf die Zimmer, dafür gibt es $\begin{eqnarray} \frac{C!}{(C-m_2)!} \end{eqnarray}$ Varianten. Da das alles unabhängig voneinander passiert, gibt es folglich insgesamt $\begin{eqnarray} S_{m,m_1} S_{m,m_2} \frac{C!}{(C-m_2)!} \end{eqnarray}$ Varianten wie sich die Philosophen insgesamt verteilen können. Weiter bin ich leider noch nicht. Aber ich wäre auch froh um irgendwelche Stichworte, für Dinge die eventuell was damit zutun haben könnten.
19.04.2011, 01:35	Bernadette	Auf diesen Beitrag antworten »
Hmm, lass uns erst mal versuchen ein aehnliches, einfacheres Problem zu loesen. Kann man annehmen, dass die m1 Gruppen gleich gross sind und die m2 Gruppen auch? Zurueck zu der Urne. Nehmen wir auch mal an, dass keine zusaetzlichen Zettel in die Urne geworfen werden und, dass m2<=m1 damit jede Gruppe auch einen Zettel ziehen kann. Sei n die Anzahl von Beteiligten und Ni= n/mi die Anzahl der Gruppenmitglieder. Folglich ist N1<=N2. Betrachten wir den ersten Zug eines Zettels. Die Gruppe die zieht hat N2 Mitglieder, es sind m1 Zettel in der Urne mit jeh N1 unterschliedlichen Namen darauf, wobei ein Name nur auf einem Zettel stehen kann. Sei x die Anzahl der Erfolge (Anzahl von Mitgliedern in der ziehenden Gruppe, die Ihren Namen auf dem gezogenen Zettel wiederfinden). X ist hypergeometrisch verteilt X~(N1,N2,n). Das Problem ist als wuerden n Kugeln in der Urne liegen, jede mit einem Namen drauf, wobei N2 einen Erfolg darstellen und N1 mal gezogen wird. Damit ist P(X=0) berechenbar. Nun ziehen aber m2 Gruppen, wobei sich an der hypergeometrischen Verteilung wegen der Symmetrie in dem Problem nichts aendert. Die letzte Gruppe die zieht hat die gleichen Erfolgschancen, auch wenn weniger Zettel als am Anfang in der Urne sind. Damit ist die Wahrscheinlichkeit, dass kein einziger seinen Namen wiederfindet P(X=0)^m2.
19.04.2011, 04:42	Bernadette	Auf diesen Beitrag antworten »
Sorry, ich habe mich da wohl vermacht. Vergiss den letzten Absatz schnell wieder.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »