Gitterweg ohne Berührung der Diagonalen?

Question

Einen schönen Abend und Feier Tag wünsche ich euch :-)

Ich habe folgende Aufgabe:

Wir betrachten Wege in der Ebene, die sich aus zwei möglichen Einzelschritten zusammensetzen: (x, y) → (x + 1, y) oder (x, y) → (x, y + 1).
Wieviele Wege vom Punkt (0, 2) zum Punkt (10, 10) gibt es, die strikt oberhalb der Diagonalen, also oberhalb der Linie von (0, 0) nach (10, 10) mit einziger erlaubter Berührung
im Endpunkt (10, 10), verlaufen?

Im Kurs hatten wir eine ähnliche Aufgabe, nur war der Startpunkt (0,0) und Endpunkt (10,10), dabei habe ich  verstanden, dass das die Catalan-Zahl C(10) entspricht.

Jedoch bin ich mir bei dieser Aufgabe nicht so sicher... Ich habe auch zuerst recherchiert und habe gelesen dass jemand die selbe Aufgabe hatte, jedoch mit dem Startpunkt (0,3) und Endpunkt(12,12), da wurde als Antwort gegeben, dass man die Hauptdiagonale um eins nach oben verschieben sollte und somit dann der Startpunkt (0,2) und Endpunkt (11,11) wäre und die Rechnung C(11)-C(10), aber ich verstehe nicht warum wir die Hauptdiagonale verschieben müssen...

Mein Ansatz:

Ohne es wirklich verstanden zu haben, warum man die Hauptdiagonale um Eins nach oben verschieben muss, würde ich das selbe machen und dabei den Startpunkt (0,1) und Endpunkt(9,9) bekommen. Und rechnen C(9)-C(8).

Ist das richtig ? Oder kann mir jemand erklären, wie ich vorzugehen habe?

Bin für jede Hilfe dankbar :-)

Answer 1

Mal mal das Spielfeld hin: ein Quadrat  (0,0)  (10,0) (10,10)  (0,10)

Der letzte Schritt führt zwangsläufig von (9,10) zu (10,10), ändert also nichts an der Anzahl der Wege.  Also ist der eigentliche Endpunkt (9,10). Die Diagonale darf nicht berührt werden, also darf man sich nur in dem Viereck bewegen: (0,2) (1,2) (9,10), (0,10). Die Gerade von (1,2) bis ((9,10) heißt y=x+1, die verschobene Diagonale.

Nächster Schritt: wegen dem Startpunkt (0,2) haben wir eine Viereck. Wenn man bei (0,1) startet, ändert sich die Anzahl der Wege nicht, weil der erste Schritt von (0,1) nach (0,2) zwangsläufig ist.

Dadurch wird das Spielfeld, in dem man sich bewegen darf, zu einem gleichschenkligen Dreieck, von (0,1) aus 9 nach oben, dann 9 nach rechts, dann auf der Geraden y=x+1 zurück. Seeehr interessant!

Wenn Du jetzt noch das Dreieck um 1 nach unten verschiebst und um 45 Grad nach rechts drehst, sieht es aus wie in

https://de.wikipedia.org/wiki/Catalan-Zahl

unten Dyck-Pfade.

Wir hätten dann C₉

Comments

Vielen Dank für Ihre Antwort :-)

Jetzt hab ich alles verstanden, danke sehr, wenn man das versteht ist das wirklich sehr Interessant und macht auch dabei Spaß :-)

Eine Frage hab ich noch, Sie haben beim "Zweiten Schritt geschrieben: "wegen dem Startpunkt (0,2) haben wir eine Viereck. Wenn man bei (1,0) startet, ändert sich die Anzahl der Wege nicht, weil der erste Schritt von (0,1) nach (0,2) zwangsläufig ist."

Aber warum den bei (1,0) starten ? Oder meinen Sie bei (0,1) starten würde es nichts an die Anzahl der Schirtte ändern ?

Aber ansonsten, vielen Dank :-)

---

habs verbessert!

---

Okay, vielen Dank! :-)