| Autor |
Beitrag |
    
Aleyna
| | Veröffentlicht am Dienstag, den 31. Oktober, 2000 - 20:33: | 
|
An einem runden Tisch mit n Plätzen sitzen k Personen. Man berechne die Wahrscheinlichkeit, dass sie bei rein zufaelliger Platzwahl alle voneinander getrennt sitzen.
Vielen Dank |
Matroid (Matroid)
| | Veröffentlicht am Mittwoch, den 01. November, 2000 - 21:46: |
|
Hi Aleyna,
Du hast wirklich die schönsten Aufgaben. So einfach ist das nicht, wie ich selbst gemerkt habe.
Zuerst habe ich mich gefragt: sind die Stühle numeriert und/oder haben die Personen Namen? Warum ich das
frage?
Nehmen wir an, da sind 4 Stühle und 2 Personen.
Die Personen heißen A und B.
Folgende Sitzordnungen sind z.B. möglich:
frei A frei B
A frei B frei
B frei A frei
Also einmal sitzt A auf Stuhl 1 und das andere mal
auf Stuhl 2 usw. Sollen das verschiedene Möglichkeiten sein?
Wenn die Stühle numeriert sind und die Personen Namen haben, dann kann man die Anzahl der Möglichkeiten
die k Personen auf die n Plätze so zuverteilen, daß nicht 2 auf benachbarten Stühlen sitzen, so zu zählen
versuchen:
Wähle für die erste Person einen Stuhl. Dafür n Möglichkeiten.
Nun ist ein Stuhl besetzt und die beiden benachbarten Stühle kommen nicht mehr in Frage.
Für die zweite Person gibt es also noch n-3 Stühle zur Auswahl.
Aber an dieser Stelle wird es unübersichtlich.
Man kann nicht so einfach sagen, wieviele Stühle jetzt noch für die dritte Person zur Auswahl stehen. Wenn
nämlich die zweite Person genau 2 Plätze von der ersten entfern sitzt, dann sind für die dritte noch n-5
Stühle auswählbar. Wenn aber die zweite Person mehr als 2 Stühle von der ersten entfernt sitzt, dann sind
nur noch n-6 Stühle möglich.
Und weil das so kompliziert wird, nehme ich mal an, daß die Personen keine Namen haben und die Stühle
keine Nummern. Es soll nur auf das Muster aus besetzten und freien Stühlen ankommen.
Dann sehen Lösungen für n=4 und k=2 so aus:
besetzt frei besetzt frei
und weil die Stühle im Kreis stehen und keine Nummern haben, ist das dasselbe wie
frei besetzt frei besetzt.
Und da ist nun die nächste Schwierigkeit.
Oft könnte man zwei Möglichkeit als gleich ansehen, weil durch zyklische Vertauschung die eine zur anderen
wird.
Und wie zählt man das?
Ich mache ein anderes Modell für die Zufallsvariable. Wir denken uns zuerst einen Tisch mit k Stühlen, die
k Personen auf die k Stühle.
Jetzt bringen wir weitere Stühle an den Tisch und zwar so, daß zwischen je zwei Personen genau ein Stuhl
steht.
Das ist die eine Möglichkeit für den Fall n=k.
Wenn nun noch Stühle übrig sind (n - 2k >0), dann können wir diese irgendwo dazwischen stellen. Stellen
wir also den ersten Stuhl irgendwo hin. Es gibt also nun eine Lücke mit 2 leeren Stühlen und k-1 Lücken
mit 1 Stuhl. Egal wo wir den Stuhl hinstellen, das ist so, also haben wir im Grunde nur eine Möglichkeit
den ersten weiteren Stuhl zu stellen.
Durch Hinzustellen aller weiteren Stühle entsteht ein "Lückenmuster": eine Person, dann 1 leerer Stuhl und
noch x{1} weitere leere Stühle, wieder eine Person, dann 1 leerer Stuhl und noch x{2} weitere leere
Stühle usw. bis zu x{k-1} leeren Stühle vor der Person, bei der wir angefangen hatten. Die Anzahl der
weiteren leeren Stühle ist n-2k.
Also gilt Sk-1 i=1 xi = n-2k und mit xi>=0.
Ich betrachte nun den Vektor X = [x1 , x2, ... , xk-1]. Wieviele verschiedene Vektoren kann
man bilden?
Weil der Tisch rund ist, müssen wir uns noch Gedanken machen um Vektoren machen, die eigentlich die
gleiche Möglichkeit beschreiben. Beispiel [1,2,0] ist dasselbe wie [2,0,1] und [0,1,2]. Von diesen
gleichwertigen Möglichkeiten sollen nur die "größte" gezählt werden. Dabei definiere ich "größer" wie
folgt: X ist größer als Y (in Zeichen X>Y), wenn ein 0<i<k existiert mit xj=yj für alle j<i und
xi > yi.
Von den drei Vektoren im obigen Beispiel ist [2,0,1] der größte.
Suche also alle Summenzerlegungen von n-2k in k-1 Summanden. Die Anzahl dieser Summenzerlegungen
sei s(k), wobei durch zyklische Vertauschung ineinander überführbare Zerlegungen als gleich gelten.
Igendwie blicke ich nicht mehr durch.
Soweit so schlecht. Schon wieder bin ich daran gescheitert, daß der Tisch rund ist.
Ich schlage vor, Du siehst Dir mal an, was ich mir bisher ausgedacht habe und hilfst mir hoffentlich weiter. Vielleicht sehe ich die Aufgabe ja zu kompliziert und Du kannst mir noch irgendwelche Hinweise geben.
Gruß
Matroid |
Danni
| | Veröffentlicht am Donnerstag, den 10. Mai, 2001 - 09:28: |
|
Hi,habe hier eine ähnliche Aufgabe:
Eine Gruppe von n Personen, darunter Marta und Grete, setzen sich zufällig an einen runden Tisch.
Wie groß ist die Wahrscheinlichkeit das genau k Personen zwischen Marta und Grete sitzen?
Wenn jemand wenigst einen Ansatz hätte??!
Gruß Danni |
sonny
| | Veröffentlicht am Donnerstag, den 10. Mai, 2001 - 10:12: |
|
Hallo Danny,
setze Marta und Grete auf die entsprechenden Stühle.
Dann gibt es für die anderen noch (n-2)! Möglichkeiten.
Das ist die Anzahl, wenn M und G sich gegenüber sitzen, also links und rechts von M und G k Stühle frei sind (bevor die anderern sich plazieren).
Andernfals können M und G noch vertauscht werden, dann 2(n-2)! Möglichkeiten.
sonny |
sonny
| | Veröffentlicht am Donnerstag, den 10. Mai, 2001 - 10:14: |
|
Hallo Danny,
setze Marta und Grete auf die entsprechenden Stühle.
Dann gibt es für die anderen noch (n-2)! Möglichkeiten.
Das ist die Anzahl, wenn M und G sich gegenüber sitzen, also links und rechts von M und G k Stühle frei sind (bevor die anderern sich plazieren).
Andernfals können M und G noch vertauscht werden, dann 2(n-2)! Möglichkeiten.
sonny |
sonny
| | Veröffentlicht am Donnerstag, den 10. Mai, 2001 - 10:26: |
|
Hallo Danny,
die Möglichkeiten n Personen an einen runden tisch zu setzen sind (n-1)!
Also im 1. Fall
P=(n-2)!/(n-1)!=1/(n-1),
sitzen sie sich nicht genau gegenüber:
P=2/(n-1)
sonny |
Matroid (Matroid)
| | Veröffentlicht am Freitag, den 20. Juli, 2001 - 14:40: |
|
Zur ursprünglichen Aufgabe von Aleyna:
Quote:
An einem runden Tisch mit n Plätzen sitzen k Personen. Man berechne die Wahrscheinlichkeit, dass sie bei rein zufaelliger Platzwahl alle voneinander getrennt sitzen.
Wenn k>n-k gibt es keine Möglichkeit.
Sei nun k<n-k.
Die Anzahl der Möglichkeiten k Personen auf n Plätze an einem runden Tisch zu setzen, nenne ich
zunächst mal T(n,k). T(n,k) ist damit die Anzahl aller Möglichkeiten.
Wenn zwischen je zwei Personen mindestens ein leerer Stuhl stehen soll, dann steht rechts (oder links, ich nehme aber rechts) von jeder Person ein leerer Stuhl. Will ich nur solche Anordnungen erzeugen, dann kann ich das so tun:
Jede Person nimmt zwei Stühle in die Hand. Die restlichen n-2k Stühle werden zunächst beiseite gestellt. Nun gehen alle Personen zum Tisch, setzen sich auf einen ihrer beiden Stühle und stellen den zweiten Stuhl rechts neben sich an den Tisch.
Die restlichen Stühle werden nun zufällig verteilt. Das ergibt an manchen Stellen eben 2 oder mehr leere Stühle zwischen 2 Personen.
Wie zählt man die Möglichkeiten?
Die Anzahl der Möglichkeiten ist T(n-k,k),
denn es sind für Objekte von 2 verschiedenen Arten die Möglichkeiten zu zählen, diese an einem runden Tisch zu platzieren, wobei durch Drehungen aufeinander abbildbare Anordnungen nur einmal zählen.
Der eine Objekttyp ist "Person mit 2 Stühlen", der andere ist "leerer Stuhl".
Die Wahrscheinlichkeit ist als
T(n-k,k) / T(n,k)
Bleibt noch die Berechnung von T(n-k,k) und T(n,k).
Wie das geht, erklärt http://matheplanet.de/default3.html?link=265
Gruß
Matroid |
yellow
| | Veröffentlicht am Samstag, den 21. Juli, 2001 - 08:24: |
|
Hallo Matroid,
kannst Du Dich dann auch mit diesem Problem beschäftigen:
Auf einer Perlenkette ohne ausgezeichnete Stelle sollen a weiße und b schwarze Perlen, die sonst gleich sind, aufgezogen werden. Wieviel Möglichkeiten gibt es?
yellow |
Matroid (Matroid)
| | Veröffentlicht am Samstag, den 21. Juli, 2001 - 12:10: |
|
Hab ich auch im genannten Link besprochen. |
Matroid (Matroid)
| | Veröffentlicht am Samstag, den 21. Juli, 2001 - 13:02: |
|
PS: Schau in Abschnitt 5.6 |
Matroid (Matroid)
| | Veröffentlicht am Samstag, den 21. Juli, 2001 - 13:27: |
|
In http://www.theory.csc.uvic.ca/~cos/inf/neck/NecklaceInfo.html wird eine Formel für Bracelets gegeben. Ein Bracelet ist ein Halsband, das "umgedreht" werden darf.
Da diese Formel aber absolut kompliziert ist, empfehle ich für ein bestimmtes n und k immer die Zählung von invarianten Anordnungen je Gruppenoperation.
Das noch zur Ergänzung. |
|
