Kombinatorik: Komplizierteres Anordnungsproblem
Hallo,
mich beschäftigt seit einigen Tagen eine Fragestellung aus der Kombinatorik, die ich bislang nicht lösen konnte (nein, es ist keine Aufgabe aus der Schule oder Uni).
Wir alle kennen Aufgaben mit Tichanordnungen, wo zwei Personen zusammensitzen sollen.
Meine Aufgabe sieht aber so aus: Ich habe acht unterscheidbare Personen (A, B, C, D, E, F, G, H). Die Personen A, B, C, D sind miteinander befreundet und wollen deshalb in Zweierpärchen zusammensitzen. Zulässige Lösungen wären also z.B. (C,A,B,G,H,C,D,F oder D,A,G,C,B,F,G,H).
Mein erster Ansatz war, es auf das Problem zurückzuführen, dass zwei Personen zusammensitzen wollen, also (8-2+1)!*2!. Nach dem Inklusionsprinzip, würde ich dann, wenn man die Menge doppelt nimmt, die Überschneidungen rausrechnen. Aber hier komme ich nicht weiter.
Würde mich sehr über Hilfe freuen!
5 Antworten
Eine kleine Überlegung von mir:
Klar ist, dass entweder alle 4 Personen nebeneinander sitzen müssen oder je ein Zweierpärchen; genau 3 geht nicht weil sonst einer alleine bleibt. In jedem Fall haben wir eine Anordnung der Form
x α x β x, wobei α und β jeweils für ein Zweierpärchen stehen und x für Folgen von Leuten aus (E,F,G,H)... Hierbei kann x auch für "keine Person" stehen.
Wenn wir uns das jetzt aber mal angucken, kommen wir auf ein Problem der Form "Wie viele Anordnungen für E,F,G,H,α,β gibt es?"
Nun, da es 6 Personen sind und jede Permutation zulässig ist, kommt man auf 6! Anordnungen.
Nun gibt es also für jede zulässige Wahl von α und β genau 6! Möglichkeiten; daher genügt es diese 6! mit der Anzahl aller zulässigen Wahlen für α und β zu multiplizieren. Wie viele gibt es davon?
Für α wählen wir 4 aus 2 unter Beachtung der Reihenfolge, was uns genau 12 Möglichkeiten beschert. Für β bleiben dann noch 2 Personen übrig, die wir auf 2 Arten anordnen können. Insgesamt also 24 Möglichkeiten.
Daher lautet meine Gesamtlösung 24 * 6! = 17280.
Meine Vorgehensweise (ich hab jetzt erst die anderen Kommentare gelesen) ist übrigens prinzipiell dieselbe wie die von Drainage, ich habe nur andere Buchstaben benutzt :P
Eigentlich sollte das problemlos funktionieren, wenn ich mir das richtig vorstelle. Wie sieht denn deine Simulation aus?
Ich hätte es jetzt folgendermaßen gelöst. Ist bestimmt falsch, weil ich wieder irgendwas übersehen habe, aber die Kollegen Suboptimierer und psychironiker sind dann bestimmt zur Stelle ;)
Also ich habe mir Folgendes vorstellst:
8 Plätze: o o o o o o o o
Wie viele Möglichkeiten gibt es für ein Zweierpaar, sich nebeneinander hinzusetzen? Naja 7, kann man durchzählen.
Erste Problematik, auf die man stößt: Setzt sich das Paar außen hin, also beispeilsweise auf Plätze 1,2, dann sind somit 1,2 und 2,3 für das andere Paar unmöglich, also bleiben denen noch 5 Plätze. Setzt sich Paar 1 innen hin, z.B. 3,4, so sind 3,4; 2,3 und 4,5 unbelegbar fürs andere Paar. Denen bleiben hier also nur noch 4 Plätze übrig. Also muss eine Fallunterscheidung her!
Fall 1 (außen): 2 (Plätze für Paar 1) • 5 (Plätze für Paar 2, siehe oben) • 4! (für den Rest)
o o o o o o o o
Fall 2 (innen): 5 (Plätze für Paar 1) • 4 (Plätze für Paar 2, siehe oben) • 4!
o o o o o o o o
Also Gesamtkombinationen: 2•5•4! + 5•4•4! = 5!(2+4) = 6! = 720
Zweite Problematik: Wer ist Paar 1 und wer ist Paar 2? Naja das dürfte äquivalent zum Problem sein, dass ich 4 verschiedene Personen auf 4 Plätze (nämlich die oben in den Fällen vorbestimmten Plätze) setzen kann. Das sind 4!
Also wird noch draufmultipliziert auf die bisherigen Kombinationen: 4! * 720 = 17280
Hallo Drainage,
erst einmal herzlichen Dank für deine Antwort! Mich treibt darauf aufbauend eine Folgefrage um: Angenommen, wir hätten nun 9 Plätze und auch 9 Personen (also A, B, C, D, E, F, G, H, I). Die übrige Aufgabenstellung wäre unverändert, d.h. A, B, C, D wollen weiterhin zusammensitzen.
Dann hätte ich einfach deine Lösung adaptiert: Fall 1 (außen): 2 (Plätze für Paar 1) • 6 (Plätze für Paar 2, siehe oben) • 5! (für den Rest)
Fall 2 (innen): 6 (Plätze für Paar 1) • 5 (Plätze für Paar 2, siehe oben) • 5!
Gesamtkombinationen: 1440 + 3600 = 5040.
Das ganze muss weiterhin mit 4! multipliziert werden, so dass sich 120960 Lösungen ergeben würden.
Hältst du diese Berechnung für korrekt? Ich bin mir nicht sicher, denn ich habe es mal in einem Programm simuliert und komme auf 129600 Möglichkeiten.
Kannst du mir weiterhelfen?
Ja, also auf den ersten Blick müsste die Rechnung stimmen.
Hier ist nochmal die Fragestellerin. Bei den beispielhaften Lösungen ist mir ein Fehler unterlaufen: Korrekt wären z.B. E,A,B,G,H,C,D,F oder D,A,G,C,B,F,G,H. Die beiden Pärchen müssen also selbst nicht auch zusammensitzen.
Der "Tisch" meiner Lösung ist eine Stuhlreihe, wobei die Reihe ein Anfang und ein Ende hat.
Die Lösung sieht anders aus, wenn der Tisch rund ist, oder wenn die Tischkante ein Rechteck ist und einenander gegenübersitzende Personen "zusammensitzen", oder diese und auch benachbarte. Im Falle einer rechteckigen Tischplatte kommt es dann noch darauf an, ob 3 Paare einander gegenübersitzen und zwei Personen an den Kopfenden, oder die Kopfenden nicht besetzt werden, oder der die Tischplatte ein Quadrat ist, und was jeweils als "zusammensitzen" zählt.
Präzisere Angaben wären also recht hilfreich.
Ich gehe davon aus, dass die Tischplatte eine Rechteck ist, der Tisch
Es gibt 2 * 7 = 14 Möglichkeiten m, wie das Paar AB zusammensitzen kann
Wenn AB am Rand sitzt (4 Möglichkeiten), gibt es jeweils 2 * 5 Möglichkeiten, wie C und D zusammensitzen können (macht insgesamt 40 Möglichkeiten); für die restlichen 10 Möglichkeiten der Position des Paares AB gibt es nur jeweils 2 * 4 = 8 Möglichkeiten für CD (macht insgesamt 80 Möglichkeiten).
Also gibt es 120 Möglichkeiten, wie AB und CD zusammensitzen können.
Entsprechend für AC und BD sowie für AD und BC. Da A (bzw. eine beliebige andere einzeln betrachtete der befreundeten Personen) in genau einem Paar vorkommt, sind das alle Möglichkeiten. Also gibt es 3 * 120 = 360 Möglichkeiten, 4 der 8 Plätze nach Wunsch mit Paaren zu besetzen.
Für jede dieser Möglichkeiten gibt es 4! = 24 Möglichkeiten, die restlichen Plätze zu besetzen. Demgemäß gibt es insgesamt 24 * 360 = 8640 Möglichkeiten...
...falls dein Tisch nicht doch etwas anderes als die angenommen Stuhlreiche aussieht. Gleichwohl müsste sich das Prinzip z.B .auf einen runden Tisch fortsetzen lassen.
Wahrscheinlich hat Drainage Recht.
In meiner Aufstellung der Paare vergaß ich, für jedes Paar XY von Paaren (z.B. X = AB und Y = CD) noch das Paar YX zu bedenken, was die Anzahl noch einmal verdoppelt.
Auch ist Drainages Überlegung sehr viel einfacher; er hält die vier in Paaren zu ordnende Personen zunächst variabel.
Was mir halt spanisch vorkommt, ist, dass meine 17280 fast die Hälfte von 8! sind, also der Gesamtzahl an Setzmöglichkeiten.
Schon blöd, dass man bei solchen Aufgaben absolut kein Gefühl für die richtige Lösung hat...
Uh spannend, ich bin auf das Doppelte von dir gekommen bzw. du auf die Hälfte von mir.
Dein Problem wurde in allgemeinerer Form nochmal aufgegriffen; wir denken gerade über eine Mögliche Lösung nach. Falls du mitlesen und/oder dich beteiligen möchtest, gebe ich dir hier einen Link:
http://www.gutefrage.net/frage/kombinatorik---erweiterte-fragestellung
Auch dir ganz herzlichen Dank für die Antwort!
Eigentlich müsste sich deine Formel doch verallgemeinern lassen als 24 * (n-2)!, wenn die Anzahl an Sitzplätzen = Personen bedeutet und die sonstigen Parameter unverändert bleiben.
Ich habe aber das ganze mit Simulationsergebnissen von mir verglichen und leider bekomme ich da keine Übereinstimmung hin. Ich zerbreche mir den Kopf wieso, aber leider durchdringe ich das (noch) nicht.
Hast du vielleicht einen Ansatz, wie sich das Problem verallgemeinern ließe?