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
1 Antwort
Hier meine Gedanken, ebenfalls nicht formal zu Ende gebracht, aber vielleicht hilft es dir weiter:
Meiner Meinung nach wäre noch zu präzisieren, ob ein Pfad auch nur die Hauptdiagonale berühren und später erst "echt" überschreiten kann. Wenn ja, soll derjenige Pfad auch dazu gehören, der gleich zu Beginn die Hauptdiagonale "überschreitet"? Ich meine in beiden Fällen: ja.
Man kann jeden solchen Pfad in zwei Teilpfade zerlegen, einen bis zum Berührungs- bzw. Schnittpunkt und einen ab dem Schnittpunkt, das hast du ja schon geschrieben. Allerdings ist dieser Vorgang nicht eindeutig. Ein Pfad der immer unterhalb der Hauptdiagonale bleibt, diese aber mehrmals berührt, kann auf mehrere Arten zu einem Pfad "umgebaut" werden, der genau einmal die Hauptdiagonale überschreitet.
Am Ende sollte man also mehr als C(n) Pfade erhalten.
Man kann die Anzahl Pfade über alle möglichen Berührungs- bzw. Schnittpunkte summieren, das ergibt folgende Formel:
Summe von j = 0 bis n über P(j) * P(n-j)
Hierbei ist P(j) die Anzahl der Pfade von (0,0) bis (j,j), die unter der Diagonalen verlaufen (und diese allenfalls mehrfach berühren). Wie du schon sagt ist P(j) = C(j), die j-te Catalan-Zahl.
Dann hätten wir:
Summe von j = 0 bis n über C(j) * C(n-j), was die "Rekursionsformel von Segner" ist,
Ergebnis: C(n+1).
>>Meiner Meinung nach wäre noch zu präzisieren, ob ein Pfad auch nur die Hauptdiagonale berühren und später erst "echt" überschreiten kann
Das wäre nicht erlaubt,erlaube Pfade verlaufen alle strikt unter der Hauptdiagonalen, bis zum Schnittpunkt und danach strikt oberhalb der Hauptdiagonalen
>>Wenn ja, soll derjenige Pfad auch dazu gehören, der gleich zu Beginn die Hauptdiagonale "überschreitet"?
Das habe ich ganz außer Acht gelassen,aber ja der Pfad müsste ja dazu gehören,man kann ja gleich zu Beginn die Hauptdiagonale überschreiten
Hmm also war es mit Berührung ? Na gut das macht es noch komplizierter, wie soll man das dann noch modellieren mit dem strikt unterhalb,man könnte die Hauptdiagonale um eins nach unten verschieben,mit Berührung entspricht das dann unserem Problem,nur die Koordinaten werden dann transformiert, das wäre dann von (0,-1) bis (n-1,n-1) also C(n-1)
Bist du dann sicher mit deiner Aussage "Weil Catalan-Zahlen geben generell die Anzahl der möglichen Schritte von (0,0) nach (n,n) an, die strikt unter der Hauptdiagonalen verlaufen"? Wenn ich mir das in Wikipedia so anschaue, dann wäre Berührung erlaubt.