Beziehung Catalan-Zahlen Dyck-Pfade |
| 20.02.2013, 19:56 | Necross123 | Auf diesen Beitrag antworten » |
| Beziehung Catalan-Zahlen Dyck-Pfade Ich weiß dass die Anzahl aller Dyck-Pfade der länge 2n (also Pfade in einem Gitterpunktweg von (0,0) nach (2n,0) wo die 2. Komponente in jedem Punkt >=0 ist) den Catalan-Zahlen entsprechen. f(n) bezeichne nun die Anzahl der Dyck-Pfade der Länge 2n. Ich weiß jetzt nur nicht wie ich die Rekursion, die gilt (weil sie den Catalan Zahlen entspricht), argumentieren soll. Meine Ideen: Mit f(0)=1 Ich hab mir schon überlegt, dass ich einen Dyckpfad der Länge 2n in 2 Pfade, mit den Längen 2k und 2n-2k irgendwie zerlegen kann(aber wie genau weiß ich nicht), nur wie ich zum Ergebnis kommen soll weiß ich nicht. |
||
| 02.03.2013, 15:15 | Necross123 | Auf diesen Beitrag antworten » |
Hat niemand eine Idee? Ich häng an dem Problem jetzt schon Tage und komm einfach nicht weiter. Hab mir auch die Pfade bis zu n=4 aufgezeichnet und komme trozdem nicht auf eine Idee. |
||
| 02.03.2013, 15:58 | Necross123 | Auf diesen Beitrag antworten » |
Habe das Problem selbst lösen können. Für Interessierte: Jeden Pfad der Länge 2n kann man wie folgt aufspalten: "rauf"+Pfad1+"runter"+Pfad2, wobei Pfad1 die Länge 2k (0<=k<=n-1) und Pfad2 die Länge 2n-2-2k hat. Anmerkung: in meinem ersten Post habe ich bei der Rekursion einen Fehler gemacht, hinten gehört "-k" statt "+k". |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
