Gitterwege ohne Diagonalenberührung

Neue Frage »

post_ex0dus Auf diesen Beitrag antworten »
Gitterwege ohne Diagonalenberührung
Hallo Matheboard smile
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 verwirrt

vielen Dank für eure Hilfen =)
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von post_ex0dus
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.

Ich halte letzteres eher für das größere Problem. Augenzwinkern

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 ).
 
 
post_ex0dus Auf diesen Beitrag antworten »

Hey, erst einmal DANKE für die superschnelle Antwort Big Laugh
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!
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. unglücklich

Genauso ist doch auch aus "alt (0,3)" der Punkt "neu (0,2)" geworden, durch Verminderung der y-Koordinate um 1.
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?
HAL 9000 Auf diesen Beitrag antworten »

Herrje... Finger1

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.
post_ex0dus Auf diesen Beitrag antworten »

super, jetzt habe ich es verstanden! Danke für deine Geduld mit mir Freude
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
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. unglücklich
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)
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. Big Laugh
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Mathemakus
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?

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.
Neue Frage »
Antworten »



Verwandte Themen

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