Kombinatorik - komplexerer Fall von Ziehen ohne Zurücklegen

Neue Frage »

Jayne Auf diesen Beitrag antworten »
Kombinatorik - komplexerer Fall von Ziehen ohne Zurücklegen
Hallo Matheboard,

ich hoffe, ich stelle meine Frage im richtigen Forum. Seit einigen Tagen kämpfe ich jetzt mit dem folgenden Problem:

Ich habe n Kugeln, aus denen ich m Paare ziehen möchte, wobei immer Kugel i und Kugel i+1 ein Paar sind. Das heißt, wenn ich Kugel 2 ziehe, so muss auch Kugel 3 gezogen werden. Das heißt auch, dass nur Kugeln 1...n-1 tatsächlich gezogen werden können, denn Kugel n hat keine Paarkugel mehr.

Die Reihenfolge, in der die Kugelpaare gezogen werden, ist nicht wichtig. Kugelpaare können nicht zurückgelegt werden.

Wie die Paare aussehen, ist nicht wichtig. Ich brauche eine Formel, die mir sagt, auf wieviele Weisen ich m Paare aus n Kugeln ziehen kann.

Mein Problem ist, wie ich berücksichtigen kann, dass wenn Kugel i gezogen wurde, Kugel i-1 auch nicht mehr zur Verfügung steht, weil sie ja keine Paarkugel mehr besitzt. Und gleichzeitig auch Kugel i+1 nicht mehr, weil sie ja mit gezogen wurde.

Kugel i-1 fällt aber nicht komplett aus der Berechnung raus, weil ja durchaus Kugel i-2 gezogen werden könnte. i-1 wäre dann ihr Nachbar und würde mitgenommen werden. Das heißt, man kann nicht einfach annehmen, dass man mit jeder Ziehung drei Kugeln rausnimmt.

Danke schon mal im Voraus für die Hilfe!
Zellerli Auf diesen Beitrag antworten »

Ich muss nochmal nachfragen:

Nicht die Kugeln sind nummeriert, sondern du gibst ihnen die Bezeichnung, indem du sie ziehst "ich ziehe jetzt die i-te und die (i+1)-te Kugel".

Naja und dann Frage ich mich, woher du weißt, dass die letzte Kugel keinen Partner hat. Was ist z.B. für n=10 ?

Stelle ich mir das richtig vor:

1 2 3 4 5 6 7 8 9 10 sind z.B. die Kugeln.
Du ziehst jetzt (zufällig in der Reihenfolge) 5mal Paare:
1 2, 3 4, 5 6, 7 8, 9 10
Dann hat die n-te Kugel doch einen Partner...

Irgendwie blicke ich die Angabe noch nicht...
 
 
Jayne Auf diesen Beitrag antworten »

Ja, ich glaube, du meinst die gleiche Aufgabe. Wenn man es so macht, wie du vorschlägst, dann hat die n-te Kugel einen Nachbar. Dann definierst du einfach "9 10" als Paar, nehme ich an. Du müsstest dann quasi immer die Paare "1 2" "2 3" "3 4" etc. betrachten, richtig? Und dann daraus ziehen. Wie berücksichtigst du dann in der Rechnung, dass mit dem Ziehen von "2 3" auch "1 2" und "3 4" wegfallen?


Ich sage hingegen, ein Paar sind immer gezogene Kugel i und zu ihr gehörende Kugel i+1. Dann muss ich ja i=n ausschließen, da Kugel n+1 nicht mehr dabei ist. Damit habe ich die Kugelpaare jeweils durch die "linke" Kugel definiert. Aber es ist das gleiche Problem, nur eine andere Herangehensweise. Mein Bauchgefühl sagt mir, dass deine leichter sein könnte.

So oder so, wichtig ist, dass die Kugeln auf einem Zahlenstrahl angeordnet sind und nicht zusammenrücken können, wenn ein Paar weg ist.

Ich hoffe, dass das jetzt klarer geworden ist.
Jayne Auf diesen Beitrag antworten »

Ich habe meinen Lösungsansatz jetzt soweit verfeinert:

Das Problem ist gelöst, wenn man alle Kombinationen von m Paaren hat, wobei jedes Paar aus zwei Zahlen besteht und keine Zahl doppelt vorkommen darf.

Es gibt insgesamt n-1 Paare von Kugeln.

Ich betrachte zunächst auf wieviele Arten ich m Paare aus n-1 Paaren auswählen kann. Das ist einfach Ziehen ohne Zurücklegen ohne Reihenfolge.

Im zweiten Schritt berechne ich dann, wieviele aus den ausgewählten Paaren mindestens eine Zahl doppelt enthalten und ziehe diese ab.

Jetzt weiß ich aber immernoch nicht, wie ich den zweiten Teil berechnen kann und würde mich freuen, wenn mir jemand auf die Sprünge helfen könnte.
Zellerli Auf diesen Beitrag antworten »

Aaaah ich glaube jetzt verstehe ich.

Die Kugeln tragen de facto Nummern. Es ist nicht so, dass man zwei Kugeln zieht und sagt: "Ich definiere: Das sind Kugel Nummern 1 und 2", sondern man zieht eine Kugel und merkt: OK, das ist die Kugel Nummer 2. Damit ist das Päärchen 1 und 2 gestorben.

Und aus deiner Formulierung im Eingangsbeitrag sehe ich, dass man im Falle der gezogenen 2 sofort auch die 3 mitzieht (also "heraussucht").

Alles klar...

Jetzt sehe ich auch die interessanten Fälle. Z.B. bei 10 Kugeln 4 Päärchen zu haben. Da könnte beispielsweise die 3 und die 8 stehen geblieben sein. Oder aber auch die 5 und die 10.

Das wird richtig hässlich (Beispiel: 10 Kugeln)
Bei 4 Päärchen musst du die Sequenzen betrachten z.B. OOOOXOOXOO
Da ist es am einfachsten, wenn du schaust, wo die X, also die alleinstehenden Kugeln landen können. Wird nur bei allgemein n Kugeln schwieriger...


Mal deiner Methode folgen (aber beide Schritte kombinieren):
Anzahl der Möglichkeiten für die erste Auswahl bei n Kugeln: (alle außer die letzte).
Anzahl der Möglichkeiten für die zweite Auswahl:
In der Sequenz "links" von dem entstandenen Loch: Alle außer die letzte Kugel.
In der Sequenz "rechts" von dem entstandenen Loch: Alle außer die letzte Kugel.
Es sind ohnehin nur Kugeln, davon gegen die Kugeln, die die beiden Sequenzen abschließen nochmal ab, also Kugeln.
Sonderfall: Beim ersten Zug wurde 1 2 oder n-1 n gewählt...

Da muss noch ein bisschen getüftelt werden Augenzwinkern
Jayne Auf diesen Beitrag antworten »

Stimmt, man kann die Sequenzen einzeln betrachten. Auf die Idee war ich nicht gekommen... Oh, ich glaube, das Ergebnis wird so hässlich, dass man es eh nicht mehr interpretieren kann unglücklich

Ist es denn nicht vielleicht doch einfacher, folgendes zu bestimmen:

Gegeben sind n Kugeln, die n-1 Paare bilden, so, dass genau zwei Kugeln genau einem Paar angehören und die anderen n-2 Kugeln jeweils genau zwei Paaren angehören. Es gibt



Möglichkeiten, m Kugelpaare rauszuwählen. Wieviele dieser Möglichkeiten enthalten mindestens eine Kugel doppelt?

Wenn ich mir einen Baum zeichne, dann habe ich im ersten Schritt (n-1) Möglichkeiten. Im zweiten Schritt habe ich (n-1)(n-2) Möglichkeiten an jedem Ast, und davon fallen genau (n-2) weg, also (n-1)(n-2)-(n-2) Möglichkeiten insgesamt. Im dritten dann (n-1)(n-2)(n-3) und davon fallen (n-2)(n-3)+(n-3) weg. Und so weiter, so dass die Gesamtzahl für m Ziehungen dann

(n-1)(n-2)...(n-m)-[(n-1)(n-2)...(n-m+1)+(n-2)(n-3)...(n-m+1)+...+(n-m+1)]

Möglichkeiten ergibt. Da ist aber irgendwo noch ein Fehler drin, glaube ich...
Jayne Auf diesen Beitrag antworten »

Die Aufgabe ist noch nicht gelöst, allerdings möchte ich anmerken, dass ich persönlich die Lösung nicht mehr benötige. Ich habe einen Workaround gefunden und kann es mir gerade leider nicht erlauben, mich weiter "am Thema vorbei" mit diesem Problem zu befassen.

Falls allerdings jemand an dem Problem Spaß hat und sich die Lösung überlegt, würde es mich durchaus interessieren, wie sie aussieht. Vielleicht komme ich ja auch selbst über Weihnachten ja dazu...

So oder so, vielen Dank für die hilfreichen Tipps, Zellerli!
AD Auf diesen Beitrag antworten »

Vielleicht wäre es hilfreich, dass Problem nochmal in kurzer, aber mathematisch hieb- und stichfester Form zu formulieren - vielleicht kannst du das übernehmen, Zellerli? Mir ist es ein wenig zu anstrengend, mich erstmal durch die lange obige Findungsphase zu wühlen, aber es scheint ja ein interessantes, nichttriviales Problem zu sein. Augenzwinkern
Zellerli Auf diesen Beitrag antworten »

Also dann formuliere ich mal:
Eine Urne enthält von bis nummerierte Kugeln.
Es werden Paare gezogen, bzw. gebildet und zwar nach folgendem Vorgehen:
Eine Kugel wird gezogen. Sie trage die Nummer . Wenn die Kugel mit der Nummer noch in der Urne ist, so werden beide entfernt und bilden ein Paar. Ist nicht vorhanden, dann wird keine Kugel entfernt.
Das ganze wird dann wiederholt, bis man "fertig" ist.
Soweit die mathematisch präzisere Formulierung.

So kann es sich dann ergeben, dass einzelne Kugeln isoliert werden und nichtmehr zur Paarbildung beitragen können.
Interessant ist eben, dass sich verschiedene Muster bilden.
Im "besten" Fall hat man für gerade die vollen Paare, für ungerade entsprechend
Im "schlechtesten" Fall hat man auf den Positionen 1, 4, 7, usw. isolierte Kugeln liegen und beispielweise (Fallunterscheidung für verschiedene spare ich mir) nur Paare.

Und was dann jetzt wie eine hässliche Aufgabe erscheint ist: allgemein zu berechnen, auf wie viele Weisen sich bei Kugeln eine bestimmte Anzahl von Paaren bilden lässt.
AD Auf diesen Beitrag antworten »

Zitat:
Original von Zellerli
Im "schlechtesten" Fall hat man auf den Positionen 1, 4, 7, usw. isolierte Kugeln liegen und beispielweise (Fallunterscheidung für verschiedene spare ich mir) nur Paare.

So wie ich das verstanden habe, hat man im ungünstigsten Fall gar kein Paar: Wenn man etwa der Reihe nach zieht - so würde ich zumindest deine Verfahrensbeschreibung deuten? verwirrt

EDIT: Oder wird etwa in die Urne zurückgelegt, falls nicht mehr drin ist? Das war eben bei dir nicht so deutlich.
Zellerli Auf diesen Beitrag antworten »

Ok hab das noch ergänzt in der Formulierung. Ja, da wird dann zurückgelegt, bzw. es entsteht halt einfach kein Paar. Das war im Wesentlichen auch das, was ich Jayne über 3 Posts aus der Nase ziehen musste Augenzwinkern
AD Auf diesen Beitrag antworten »

Ok, dann kann man die Sache zumindest erstmal rekursiv anpacken: Sei die gesuchte Anzahl aller Konfigurationen von genau Paaren aus Zahlen, so dass keine weitere Paarentnahme möglich ist. Das unterteilt sich in die Konfigurationen,

(a) wo Paar (1,2) dabei ist, und
(b) wo Paar (1,2) nicht dabei ist.

Im Fall (a) gibt es Konfigurationen. Im Fall (b) muss (2,3) dabei sein (ansonsten ist man noch nicht fertig), das macht dann Konfigurationen. Also gilt die Rekursionsgleichung

für

mit den Startwerten

.

Jetzt kann man sich überlegen, ob man daraus auch was explizites basteln kann. verwirrt


EDIT: Ok, das ist ja dann auch nicht mehr so schwer:

für , sonst Null.

Manchmal ist man aber auch zu blind - naja, es ist ja noch früh am Morgen. Augenzwinkern
Zellerli Auf diesen Beitrag antworten »

Ja stimmt, das hatte ich auch angemerkt, dass z.B. die Nummer 2 gezogen werden MUSS (entweder 1 2 oder 2 3)
Klar und die Restsequenz hat wieder eine neue Nummer 2, usw.

War ja klar, dass der Rekursions-Arthur das hinkriegt Freude

Gut wenn einer den Überblick behält und das sauber formulieren kann. Bei mir war das zwischenzeitlich chaotisches Gulasch im Kopf Augenzwinkern
AD Auf diesen Beitrag antworten »

Zitat:
Original von Zellerli
War ja klar, dass der Rekursions-Arthur das hinkriegt

Gefällt mir - werd ich mal (zeitweise) so ähnlich als Titel übernehmen. Big Laugh


P.S.: Die angegebene explizite Formel lässt sich natürlich auch direkt kombinatorisch begründen: Man hat Zweierblöcke, sowie dann mögliche Positionen (zwischen den Blöcken sowie an den beiden Enden), an denen jeweils 0 oder 1 Zahl stehen kann. Insgesamt gibt es nun noch genau Zahlen auf diese Positionen zu verteilen. Augenzwinkern
Jayne Auf diesen Beitrag antworten »

Oh, wow. So einfach sieht es dann aus, wenn man erstmal die Lösung vor sich hat... Danke!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »