Anzahl Pfade zw. 2 Punkten < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:20 Do 24.07.2014 | | Autor: | Morgyr |
| Aufgabe | Wir betrachten Wege in der Ebene, die sich aus zwei möglichen Einzel-
schritten zusammensetzen: (x; y) [mm] \mapsto [/mm] (x + 1; y) oder (x; y) [mm] \mapsto [/mm] (x; y + 1).
Wieviele Wege vom Punkt (0; 3) zum Punkt (12; 12) gibt es, die strikt oberhalb der Dia-
gonalen verlaufen (die einzige erlaubte Berührung mit der Diagonalen ist der Endpunkt
(12; 12))? |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Zuerst einmal: von (0;0) zu (5;5), Diagonale selbst erlaubt.
Anzahl Pfade entspricht der 5-ten Catalanzahl, denn für jeden Schritt nach oben gibt es auch einen nach rechts. Entsprechend 4 Klammerpaare.
Für Diagonale nicht erlaubt: 4-te Catalanzahl
Startet man nun bei (0;1), (0;2) ändert sich nichts an der Anzahl, denn die ersten zwei Knoten sind in jedem Fall enthalten.
Nun Start bei (0;3). Hier ändert sich was. Schätzungsweise [mm] C_{4}-C_{3}
[/mm]
Bei (0;4) wird es nun haarig. Durch Zeichnung erhalte ich hier 4 Wege. Einzige Erklärung, für jeden möglichen Schritt nach rechts > 1 (in dem Fall 2x) wird einmal [mm] C_{3} [/mm] subtrahiert. Würde 14-5-5=4 bedeuten.
Ist da auch nur ansatzweise irgendwas richtig dran?
Für die eigentlichen Aufgabe würde das dann bedeuten:
[mm] C_{11}-C_{10}
[/mm]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:08 Do 24.07.2014 | | Autor: | Morgyr |
Ai, gidf..hat aber trotzdem paar Anläufe gebraucht, bis ich den Thread gefunden habe.
Vielleicht sollte ich alle anderen Matheforen auch zuspammen..
Nochmals, Vielen Dank ;)
|
|
|
|
![[]](/images/popup.gif){kind=small}
Gitterwege