Gitterwege ohne Diagonalenberührung |
| 02.11.2013, 11:12 | post_ex0dus | Auf diesen Beitrag antworten » | ||
Gitterwege ohne Diagonalenberührung
Sitze an einer Kombinatorik-Aufgabe und verzweifle seit einigen Stunden: In einem 13 x 13 Gitter (Koordinaten 0-12) soll die Anzahl aller möglichen Wege gefunden werden, um vom Startpunkt zum Punkt (12/12) zu gelangen. In einer vorherigen Aufgabe war die Bedingung angegeben, dass die Hauptdiagonale nicht überschritten werden darf. Hierbei bin ich (wohl auch richtig) auf die Catalan-Zahlen gekommen, da man sich einen Schritt nach oben wie eine geöffnete und einen Schritt nach rechts wie eine geschlossene Klammer vorstellen kann, und das Klammerniveau nicht negativ werden darf. Jetzt hat meine neue Aufgabe allerdings die Bedingung, dass die Wege strikt oberhalb der Hauptdiagonalen verlaufen sollen und der einzige Berührpunkt mit der Diagonalen der Endpunkt (12/12) ist. Außerdem startet man am Punkt (0/3), was aber wohl das kleinere Problem darstellt. Kann ich die Formel für die Catalanzahlen irgendwie anpassen, sodass sie ein Klammerniveau von minimal 1 zulässt oder wie soll ich da heran gehen 
vielen Dank für eure Hilfen =) |
||||
| 02.11.2013, 12:10 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Ich halte letzteres eher für das größere Problem. 
Durch "Verschiebung" der Hauptdiagonalen um Eins nach oben entspringt dieses Problem wohl der ursprünglichen Aufgabe (d.h. Berührung der Hauptdiagonale) mit Startpunkt (0,2) und Endpunkt (11,11). Und diese Anzahl müsste gleich sein: Denn jeder Weg beginnend von (0,0) (Anzahl ) führt über (0,1), und dann entweder über (0,2) (gesuchte Anzahl) oder über (1,1) (Anzahl ). |
||||
| 02.11.2013, 12:56 | post_ex0dus | Auf diesen Beitrag antworten » | ||
Hey, erst einmal DANKE für die superschnelle Antwort 
also die Idee, dass es sich nur um eine nach oben verschobene diagonale handelt ist ja super, darauf bin ich nicht gekommen! dass der Startpunkt dann (0,2) ist, habe ich verstanden, aber wie kommst du auf den Endpunkt (11/11)? Ich habe probleme damit, weil der eigentliche Endpunkt nach der Verschiebung ja sozusagen im verbotenen Bereich unter der Diagonale liegt. Die Berechnung habe ich aber verstanden! Nochmal danke! |
||||
| 02.11.2013, 12:58 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Im "alten" Koordinatensystem ist es der Punkt (11,12), aber durch die Verschiebung der Hauptdiagonale (und damit in der Folge die Verschiebung des Koordinatensystems) wird daraus (11,11). Wie du darauf kommst, dass der "unterhalb der Diagonale" liegen soll, entzieht sich meinem Verständnis. 
Genauso ist doch auch aus "alt (0,3)" der Punkt "neu (0,2)" geworden, durch Verminderung der y-Koordinate um 1. |
||||
| 02.11.2013, 13:18 | post_ex0dus | Auf diesen Beitrag antworten » | ||
sorry wenn ich mich dumm anstelle, aber wieso ist er im alten koordinatensystem bei (11,12)? er ist dort doch laut Aufgabenstellung bei (12,12) und wenn ich die Hauptdiagonale verschiebe ist er bei (12,11).. wo liegt mein Fehler? |
||||
| 02.11.2013, 13:22 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Herrje... 
Wenn du oberhalb (oder evtl. noch auf) der Diagonale bleiben musst, dann ist der erste Wegpunkt nach dem Start (0,0) zwangsläufig (0,1), denn (1,0) darfst du ja nicht passieren, weil er unterhalb der Diagonale liegt. Genauso ist (11,12) zwangsläufig der vorletzte Punkt auf dem Weg nach (12,12), d.h. man muss dort vorbeikommen. Und von dem, nur von dem Punkt "alt (11,12)" rede ich!!! Also kurz: Die Anzahl der Wege von (0,0) nach (12,12) über der Diagonale entspricht der Anzahl der Wege von (0,1) nach (11,12) über der Diagonale. |
||||
| Anzeige | ||||
|
|
||||
| 02.11.2013, 13:31 | post_ex0dus | Auf diesen Beitrag antworten » | ||
super, jetzt habe ich es verstanden! Danke für deine Geduld mit mir 
|
||||
| 17.11.2017, 11:00 | LE2234 | Auf diesen Beitrag antworten » | ||
| Andere Aufgabenstellung Hallo guten Tag, der Beitrag ist zwar schon etwas älter aber wir haben eine ähnliche Aufgabenstellung bei uns ist allerdings der Startpunkt bei (3,0). Könnt ihr mir vielleicht einen Tipp geben wie ich hier vorgehen könnte. Weil so einfach verschieben geht ja gar nicht. Außerdem habe ich doch auf der Strecke von (3,0) bis (12,12) keine korrekte Klammerung mehr. Liebe Grüße |
||||
| 17.11.2017, 11:53 | HAL 9000 | Auf diesen Beitrag antworten » | ||
"Ähnlich" reicht nicht - bitte nennen die genaue Aufgabenstellung. Denn es kann hier ja wohl kaum um Wege über der Hauptdiagonalen gehen, wo doch bereits dein Startpunkt (3,0) unter der Hauptdiagonalen liegt.
|
||||
| 18.11.2017, 18:07 | Mathemakus | Auf diesen Beitrag antworten » | ||
| Die Aufgabe Ich gehe mal stark davon aus, dass es die gleiche Aufgabe ist, die ich auch noch erledigen muss. Die wäre: Wieviele mögliche Wege vom Punkt (3,0) zum Punkt (12,12) gibt es, die strikt unterhalb der Diagonalen, also unterhalb der Linie von (0,0) nach (12,12) verlaufen und den Punkt (12,12) berühren? Mögliche Schritte: (x,y)->(x+1,y) oder (x,y)->(x,y+1) |
||||
| 18.11.2017, 18:12 | Mathemakus | Auf diesen Beitrag antworten » | ||
| Mein Ansatz Mein Ansatz wäre gewesen: Ich betrachte die möglichen Wege von (1,0) -> (12,11) und ziehen davon die möglichen Wege von (1,0) -> (3,2) ab. Das wäre mein naiver Ansatz gewesen.
|
||||
| 20.11.2017, 21:23 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Das entspricht doch genau dem Originalproblem "Weg von (0,3) zu (12,12) strikt oberhalb der Hauptdiagonale", nur an der Hauptdiagonalen gespiegelt! Damit ist die Anzahl gleich der, die oben schon berechnet wurde. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|