Wie viele Wege der Länge n gibt es von (0|0) nach (0|0)?

+1 Punkt
565 Aufrufe
Meine Frage:

Wie viele Wege im Gitter längs der Linien gibt es von (0|0) nach (0|0)? Mehrfachdurchläufe erlaubt.
Gefragt 25 Sep 2012 von Gast jf8811
Dazu müsste man das dazu gehörige Gittersystem kennen, um diese Frage zu beantworten.
Hi, es ist das Koordinatengitter, wie Julian vermutet hat.

2 Antworten

0 Daumen

Hmm, meinst du vielleicht das Koordinatengitter? Also einfach eine Art "Manhatten-Straßenführung" der folgenden Form:

Koordinatengitter

 

Naja, das ist glaub ich relativ schwer geschlossen aufzuschreiben.

Um so etwas herauszufinden, hilft es, einfach erstmal die Lösungen für die ersten paar n hinzuschreiben.

 

Erstmal ist klar: für ungerades n ist die Antwort stets 0. Denn jedes mal, wenn man einen Zug macht, wechselt man von einer ungeraden zu einer geraden Zahl. Man beginnt aber bei 0, um also auch bei 0 zu enden, benötigt man eine gerade Anzahl von Zügen. Das gilt sowohl in einer Dimension als auch in zweien.

Also:

n=1: #Wege = 0

n=2: Hier kann man immer nur einmal weg und wieder hingehen, das in vier Richtungen also gilt: #Wege = 4

n=3: #Wege = 0

n=4: Hier kann man immer um ein Viereck herum gehen und das im Uhrzeigersinn und gegen den Uhrzeigersinn in jede Richtung, das macht 8 Wege. Außerdem kann man einfach zwei Wege weg und wieder zurückgehen, sind nochmal vier Wege. Dazu kommen dann noch die Wege der Form (0,0)->(0,1)->(0,0)->(0,1)->(0,0) Das sind ingesamt 4*4=16 Wege. Macht insgesamt #Wege = 28, allerdings bin ich mir da noch nichtmal völlig sicher, mag sein, dass ich was vergessen hab.

n=5: #Wege = 0

n=6: Puh, das ist schon ziemliche Arbeit. Erstmal vier Rechtecke pro Richtung:

Dazu dann viermal drei Schritte weg und drei Schritte zurück.

Außerdem jede Möglichkeit mit zweimal in eine Richtung... halt, das wird zu aufwändig!

Vielleicht lieber etwas anderes:
Noch mal ganz systematisch von Anfang an:

n=2: Wir haben beim ersten Schritt 4 Möglichkeiten. Wenn wir eine davon nehmen, befinden wir uns im Abstand 1 und müssen den nächsten Schritt zurücknehmen, also gibt es insgesamt 4 Möglichkeiten.

n=4: Wir haben beim ersten Schritt 4 Möglichkeiten. Beim zweiten Schritt haben wir wieder 4 Möglichkeiten, davon bringt uns jeweils 1 in den Abstand 1 und 3 in den Abstand 2. Wir haben damit für die ersten beiden Schritte 4*1+4*3 Möglichkeiten.

Bei den 4*1 bleiben uns jetzt wieder vier Möglichkeiten eine Richtung zu wählen, der nächste Schritt muss zurückführen, diese werden also insgesamt zu 4*1*4*1 Möglichkeiten.

Bei den 4*3 Möglichkeiten müssen wir noch einmal unterscheiden: Von den dreien war eine "weiter auf der Achse bleiben" und die anderen beiden "nach links/rechts abbiegen".
Falls wir auf der Achse geblieben sind, bleibt uns nichts anderes übrig, als zurückzugehen und zwar den gerade Weg, also gilt für diese, dass es 4*1*1*1 Möglichkeiten gibt. Bei den anderen beiden gibt es genau zwei Wege, die uns zurückführen, also gibt es da 4*2*2*1 Möglichkeiten. Insgesamt sind das:

4*1*4*1 + 4*1*1*1 + 4*2*2*1 = 36

Ich hatte oben offenbar ein paar Möglichkeiten vergessen und zwar z.B. die folgende: (0,0)->(0,1)->(1,1)->(0,1)->(0,0)

 

Für höhere n wird auch das beliebig hoffnungslos. Worum gehts dir denn überhaupt?

Beantwortet 25 Sep 2012 von Julian Mi Experte X

Erstmal danke für die Antwort - ich bin der Fragesteller und habe mich jetzt auch registriert.

 

Es ist das Koordinatengitter gemeint, so wie du es gezeichnet hast.

Wir haben gerade in der Schule Binomialkoeffizienten behandelt, ich denke, es hat was damit zu tun.

Auf jeden Fall wissen wir ja jetzt, dass der Weg eine gerade Länge hat, wenn es ihn gibt. Also können wir sagen n=2*m. Wir wissen, dass es als erstes 4Möglichkeiten gibt, Aber wie stehts jetzt auf dem Weg zurück? Wieviele Möglichkeiten gibts da?

Hmm, ich glaube nicht, dass der Binomialkoeffizient einem da weiterhilft.

Einfach deshalb, weil ich keine Folge von Binomialkoeffizienten kenne/mir vorstellen kann, die mit 4, 36, ... beginnt.

 

Wenn ich irgendwann mal ein bisschen mehr Zeit hab, mach ich das noch für n=6, vielleicht erkennt man ja dann was.

 

Könnte ja bisher z.B. 4(n-1)2 sein. Aber das wäre mMn ein bisschen zu einfach. Um das zu bestätigen, müsste für n=6 100 rauskommen. Uiuiui, das könnte dauern, dass zu zeigen.

Für die ersten m "Züge" gibt es ja 4m Möglichkeiten. 4m = (22)= 22m. Wir hatten irgendeine Formel... (n über 0)+(n über 1)+(n über 2)+...+(n über n) = 2n oder so ähnlich - kommt man damit weiter?

Die Frage ist ja jetzt, wie viele Möglichkeiten es dann für die nächsten m Züge gibt...

ich wär dir auf jeden Fall dankbar, wenn du mir helfen könntest!

Binomialkoeffizienten kommen rein, wenn man 'kürzeste Wege" zählt.

Es gibt "(|k| + |h|) tief |k| "  Wege der Länge |k| + |h| vom Punkt P(0/0) zum Punkt Q(k| h) und natürlich gleich viele zurück zu P(0/0).

Dabei geht es um die Anordnungsmöglichkeiten von |k|  Elementen auf |k| + |h| Stellen, nämlich |k| Schritte horizontal, die restlichen sind dann automatisch die |h| Schritte vertikal.

Die Summe der Binomialkoeffizienten in der n-ten Zeile des Pascaldreiecks ist 2n

Aber du erlaubst ja hier auch Umwege.

Vielleicht hilft das trotzdem irgendwie weiter.

Hallo,

Ich habe meine Lehrerin gefragt, wie das hier gehen soll. Sie hat gemeint, ich soll noch weiterknobeln - als ich dann aber gebettelt hab ;-) hat Sie mir das Ergebnis verraten. Es ist (n über n/2)². Ich soll jetzt noch auf den Lösungsweg kommen... bin aber gerade am verzweifeln...

(n über n/2)² wäre ja (n über n/2) Möglichkeiten  für einen Hinweg und (n über n/2) Möglichkeiten für den Rückweg.

Ich schreibe 'tief' statt 'über', weil das kein Bruch ist.

n=2

Hinweg (2 tief 1) =2 Möglichkeiten. Rückweg 2 Möglichkeiten ist aber irgendwie Blödsinn. Es sind ja 4 Hinwege und zu jedem nur 1 Rückweg. Also kommt man irgendwie anders als mit Hin- und Rückweg auf (n über n/2)²

 

Wir wissen bisher:

Ein Weg von (0/0) wieder zu (0/0) hat zuerst mal eine Länge von n=2m. 

Ich nehme mal für die Anzahl Schritte in die 4 Richtungen nach r rechts, o oben, l links resp. u unten die Buchstaben a,b,c resp. d

Sicher ist a=c und b=d. Und 2a + 2b =n oder a+b = n/2

Nun kann man auf einem Weg der Länge n

r, o, l und u in gegebener Anzahl auf

(n tief a) ((n-a) tief b)((n-a-b) tief c)*1 Arten anordnen.

(n tief a) ((n-a) tief b)((n/2) tief a)*1

 

Ein Beispiel

n=8, a=1 -------------> c=1, b=d=3

(8 tief 1)(7 tief 3)(4 tief 1) = umformung

Die Darstellung mit den beiden Quadraten scheint die einfachste zu sein.

Jetzt müsstest du die Fälle für a=0 bis 4 addieren und auf ersichtliche Weise 'deine' (8 tief 4)2 erhalten.

 

Im Allgemeinen dann für a=0 bis m=n/2.

Leuchtet das ein und hilft dir das jetzt weiter? Ich hoffe mal...

 

0 Daumen

Da ich wenigstens etwas ausklammern kann, das in Richtung des Resultates geht, zähle ich jetzt so:

n ist gerade

Die Hälfte der n Schritte gehen in positiver Richtung, die andere Hälfte in negativer Richtung.

Ich wähle zuerst (n tief n/2) '+' Positionen, die restlichen automatisch '-' Positionen.

Von den n/2 + verlaufen der Reihe nach 0, 1,2,… als Schritte nach rechts und dazu von den n/2 - verlaufen n/2, n/2-1, n/2-2…als Schritte nach oben. Rest nach links und unten ist dadurch schon festgelegt.

Für das Beispiel n=8 läuft das  auf 

Pascaldreieck

= 70 * 70

heraus. Die 5 Summanden stammen aus der 4. Zeile des Pascaldreiecks, sind aber quadriert.

Tatsächlich sind beide Faktoren gleich.

Jetzt noch irgendwie schlau begründen und auf n verallgemeinern.

Anmerkung. Ich hoffe es ist ungefähr nachvollziehbar. Lies bitte meine Anmerkungen bei der andern Lösung.

Beantwortet 26 Sep 2012 von Lu Experte C
Klingt gut.

Allerdings hab ich den ersten teil mit dem + und - noch nicht ganz verstanden... kannst du den noch mal erklären? Vielleicht mit n=2m?

Aber die Summe der Binomialkoeffizienten kann ich dir sagen, warum die gleich (8 über 4) ist. Schau mal hier: http://de.wikipedia.org/wiki/Binomialkoeffizient#Vandermondesche_Identit.C3.A4t bei Vandermondensche Identität. Ist das richtig?

Ansonsten viele Dank!

Ich hab mir inzwischen überlegt, wie ich

Identitätbeweisen kann.

Links steht ja die Anzahl Möglichkeiten von 8 Plätzen 4 auszuwählen.

Rechts kann man die ja auch so abzählen :

Man nimmt keinen der ersten 4 und 4 der nächsten 4 

oder

man nimmt einen der ersten 4 und 3 der nächsten 4

oder 

man nimmt 2 der ersten 4 und 2 der nächsten 4

oder…

man nimmt alle 4 ersten und keinen weiteren.

Bei und dann rechnet man MAL bei oder PLUS.

Da man alles aufgezählt hat, steht rechts und links die gleiche Zahl. wzbw.

Danke noch für den Link. Ich schau da noch rein.

Ja, so in der Art kann man das beweisen. Kannst du mir jetzt noch den Teil am Anfang mit + und - erklären? Man kann doch auch nach rechts oder links gehen? Oder was meinst du mit positiv und negativ?
Also n ist ja 2m.

Da man am Schluss wieder in (0/0) ist kommen gleich viele Schritte also m Schritte in positiver (nach rechts r oder oben o) wie in negativer Richtung (nach links l oder unten u) vor.

Nun kann man einen Weg so beschreiben: Dieser hier hat die Länge n=16

Am besten zeichnest du den mal auf (3 nach links, 5 nach oben, 2 nach unten, 2 nach rechts… )

l l l o o o o o u u r r u u r u

Darin sind die + und - so verteilt

- - - +++++ - - + + - - + + -                m=8 + und gleich viele -

und dann eine Sorte der -Stellen und eine Sorte der +Stellen belegen:

l l l ooooo - - ++ - - + -

es werden z.B. in den m '- Stellen' x horizontale (nach links hier: 3) ausgewählt,  in den m '+ Stellen' m-x vertikale (nach oben hier: 5) ausgewählt, die restlichen x '+Stellen' gehen dann nach rechts, die '- Stellen' nach unten.

Noch zum Link zu Wikipedia.

(x+y)n = xxxxxxxx…x + yxxxxxxxx..x + xyxxx..x+ …+ yn

Alle Summanden haben genau n Faktoren. Es kommen alle Faktorenabfolgen als Summanden genau einmal vor.

(n tief 1) mal ist ein y in einem Summanden

(n tief k) mal sind genau k y in einem Summanden.

 

Wenn man nun eine Abzählung vornehmen will, wo's darum geht, dass in einer Abfolge von n Stellen k ausgewählt werden müssen, kann man (n tief k) verwenden.

 

Puh, danke!

 

Ich werde jetzt mal versuchen, das zu verstehen ;-) wenn ich noch Fragen hab, meld ich mich wieder!
Danke!
Bitte! Wenn du am Schluss alles der Reihe nach aufgeschrieben hast, ist ' s wahrscheinlich ganz logisch.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und ohne Registrierung

x
Made by Memelpower
...