Kombinatorik - komplexerer Fall von Ziehen ohne Zurücklegen

10.12.2009, 12:01

Jayne

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!

10.12.2009, 12:46

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...

10.12.2009, 14:00

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.

10.12.2009, 16:17

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.

11.12.2009, 01:41

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: $\begin{eqnarray*} n-1 \end{eqnarray*}$ (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 $\begin{eqnarray*} n-2 \end{eqnarray*}$ Kugeln, davon gegen die Kugeln, die die beiden Sequenzen abschließen nochmal ab, also $\begin{eqnarray*} n-4 \end{eqnarray*}$ Kugeln.
Sonderfall: Beim ersten Zug wurde 1 2 oder n-1 n gewählt...

Da muss noch ein bisschen getüftelt werden Augenzwinkern

11.12.2009, 11:26

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

$\begin{eqnarray*} \begin{pmatrix} n-1 \\ m \end{pmatrix} \end{eqnarray*}$

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...

11.12.2009, 18:05

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!

11.12.2009, 21:09

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

11.12.2009, 22:35

Zellerli

Auf diesen Beitrag antworten »

Also dann formuliere ich mal:
Eine Urne enthält $\begin{eqnarray*} n \end{eqnarray*}$ von $\begin{eqnarray*} 1 \end{eqnarray*}$ bis $\begin{eqnarray*} n \end{eqnarray*}$ nummerierte Kugeln.
Es werden Paare gezogen, bzw. gebildet und zwar nach folgendem Vorgehen:
Eine Kugel wird gezogen. Sie trage die Nummer $\begin{eqnarray*} m \end{eqnarray*}$ . Wenn die Kugel mit der Nummer $\begin{eqnarray*} m+1 \end{eqnarray*}$ noch in der Urne ist, so werden beide entfernt und bilden ein Paar. Ist $\begin{eqnarray*} m+1 \end{eqnarray*}$ 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 $\begin{eqnarray*} n \end{eqnarray*}$ die vollen $\begin{eqnarray*} \frac{n}{2} \end{eqnarray*}$ Paare, für ungerade $\begin{eqnarray*} n \end{eqnarray*}$ entsprechend $\begin{eqnarray*} \frac{n}{2}-1 \end{eqnarray*}$
Im "schlechtesten" Fall hat man auf den Positionen 1, 4, 7, usw. isolierte Kugeln liegen und beispielweise (Fallunterscheidung für verschiedene $\begin{eqnarray*} n \end{eqnarray*}$ spare ich mir) nur $\begin{eqnarray*} \frac{n}{3} \end{eqnarray*}$ Paare.

Und was dann jetzt wie eine hässliche Aufgabe erscheint ist: allgemein zu berechnen, auf wie viele Weisen sich bei $\begin{eqnarray*} n \end{eqnarray*}$ Kugeln eine bestimmte Anzahl $\begin{eqnarray*} a \end{eqnarray*}$ von Paaren bilden lässt.

11.12.2009, 23:07

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 $\begin{eqnarray*} n \end{eqnarray*}$ spare ich mir) nur $\begin{eqnarray*} \frac{n}{3} \end{eqnarray*}$ Paare.

So wie ich das verstanden habe, hat man im ungünstigsten Fall gar kein Paar: Wenn man etwa der Reihe nach $\begin{eqnarray*} n, n-1, \ldots, 1 \end{eqnarray*}$ zieht - so würde ich zumindest deine Verfahrensbeschreibung deuten? verwirrt

EDIT: Oder wird etwa $\begin{eqnarray*} m \end{eqnarray*}$ in die Urne zurückgelegt, falls $\begin{eqnarray*} m+1 \end{eqnarray*}$ nicht mehr drin ist? Das war eben bei dir nicht so deutlich.

11.12.2009, 23:32

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

12.12.2009, 06:59

Auf diesen Beitrag antworten »

Ok, dann kann man die Sache zumindest erstmal rekursiv anpacken: Sei $\begin{eqnarray*} f(n,m) \end{eqnarray*}$ die gesuchte Anzahl aller Konfigurationen von genau $\begin{eqnarray*} m \end{eqnarray*}$ Paaren aus $\begin{eqnarray*} n \end{eqnarray*}$ 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 $\begin{eqnarray*} f(n-2,m-1) \end{eqnarray*}$ Konfigurationen. Im Fall (b) muss (2,3) dabei sein (ansonsten ist man noch nicht fertig), das macht dann $\begin{eqnarray*} f(n-3,m-1) \end{eqnarray*}$ Konfigurationen. Also gilt die Rekursionsgleichung

$\begin{eqnarray*} f(n,m) = f(n-2,m-1)+f(n-3,m-1) \end{eqnarray*}$ für $\begin{eqnarray*} n\geq 4,m\geq 2 \end{eqnarray*}$

mit den Startwerten

$\begin{eqnarray*} f(n,1) = \begin{cases} 1 & \;\mbox{für}\; n=2,\,n=4 \\ 2 & \;\mbox{für}\; n=3 \\ 0 & \;\mbox{sonst} \end{cases} \end{eqnarray*}$ .

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:

$\begin{eqnarray*} f(n,m) = \binom{m+1}{n-2m} \end{eqnarray*}$ für $\begin{eqnarray*} 2m\leq n\leq 3m+1 \end{eqnarray*}$ , sonst Null.

Manchmal ist man aber auch zu blind - naja, es ist ja noch früh am Morgen. Augenzwinkern

13.12.2009, 00:53

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

13.12.2009, 08:46

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 $\begin{eqnarray*} m \end{eqnarray*}$ Zweierblöcke, sowie dann $\begin{eqnarray*} m+1 \end{eqnarray*}$ 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 $\begin{eqnarray*} n-2m \end{eqnarray*}$ Zahlen auf diese $\begin{eqnarray*} m+1 \end{eqnarray*}$ Positionen zu verteilen. Augenzwinkern

14.12.2009, 11:17

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 »

Kombinatorik - komplexerer Fall von Ziehen ohne Zurücklegen

Verwandte Themen