Wie viele mögliche Wege gibt es in einem nxn Gitter von (0,0) nach (n,n) mit folgenden Einschränkungen:?

Es sind nur Schritte nach rechts und nach oben erlaubt und alle gültigen Wege müssen genau EINMAL die Hauptdiagonale überschreiten,ansonsten bleiben sie strikt unterhalb/oberhalb der Hauptdiagonalen.

Meine Idee: Ohne sämtliche Einschränkungen gibt es ja (2n über n) möglichkeiten von (0,0) nach (n,n), wenn wir jetzt schritte nach oben als eine offene Klammer definieren "(" und Schritte nach rechts als eine schließende Klammer ")" dann entsprechen diese Möglichkeiten genau der Anzahl der perfekten Klammerungen (da die Anzahl öffnender und schließender Klammern n ist) und somit der n-ten Catalan Zahl := (1/n+1) (2n über n) https://de.wikipedia.org/wiki/Catalan-Zahl

Weil Catalan-Zahlen geben generell die Anzahl der möglichen Schritte von (0,0) nach (n,n) an,die strikt unter der Hauptdiagonalen verlaufen. Aber hier ist es ja genau dasselbe oder ? Weil ab einem beliebigen Schnittpunkt (i,j) mit der Hauptdiagonalen muss man oberhalb der Hauptdiagonalen bleiben, das ganze kann man dann aufgrund der symmetrie (nxn) spiegeln und hat wieder diesen Fall.

Also das wäre zumindest so meine Idee, aber wie beweist man das formal und kann man die Möglichkeiten auch ohne die Catalan-Zahlen bestimmen und so auf die Lösung kommen ?

Mfg

Studium, Schule, Mathematik, Logik, Physik, Statistik, Stochastik, Universität, Kombinatorik

Meistgelesene Fragen zum Thema Statistik