Dyck-Pfade

Neue Frage »

13.11.2017, 18:14	FelNa1109	Auf diesen Beitrag antworten »
Dyck-Pfade Ein Dyck-Pfad der Länge $\begin{eqnarray} 2n \end{eqnarray}$ ist ein Gitterweg mit $\begin{eqnarray} 2n \end{eqnarray}$ Schritten aus $\begin{eqnarray} \left\{ (1,1),(1,-1)\right\} \end{eqnarray}$ , der in $\begin{eqnarray} (0,0) \end{eqnarray}$ startet, in $\begin{eqnarray} (2n,0) \end{eqnarray}$ endet und keinen Punkt unterhalb der x-Achse besucht (Kontakte aber erlaubt!) Bestimmen Sie die erzeugende Funktion bzgl. der Anzahl aller Dyck-Pfade der Länge $\begin{eqnarray} 2n \end{eqnarray}$ . Wieviele Pfade der Länge 10 gibt es? (Tipp: Douglas Adams) Ich habe mir das bis jetzt nur etwa so gedacht: Wir müssen ja um von $\begin{eqnarray} (0,0) \end{eqnarray}$ nach $\begin{eqnarray} (2n,0) \end{eqnarray}$ zu gelangen eine Strecke von genau $\begin{eqnarray} 2n \end{eqnarray}$ zurück legen. Da wir vom Nullpkt. zu einem Pkt. gehen, der eine Entfernung von 2n zu diesem hat und ebenfalls direkt auf der x-Achse liegt, benötigen wir n Schritte der Form $\begin{eqnarray} (1,1) \end{eqnarray}$ und n weitere Schritte der Form $\begin{eqnarray} (1,-1) \end{eqnarray}$ . Ein "Weg" nach $\begin{eqnarray} (2n,0) \end{eqnarray}$ ist also dadurch definiert, wie oft wir nach "oben" bzw. nach "unten" gehen. Also ist die Anzahl aller Wege, bei denen wir n mal nach oben/unten geben: $\begin{eqnarray} \begin{pmatrix} 2n \\ n \end{pmatrix} \end{eqnarray}$ Weiter bin ich leider noch nicht, denke aber ich muss irgendwie zu den Catalan-Zahlen kommen, weil wir diese gerade in der Vorlesung behandelt haben. Danke
13.11.2017, 19:16	sibelius84	Auf diesen Beitrag antworten »
Hallo FelNa1109, wenn man eine erzeugende Funktion aufstellt, macht man das ja meistens aus einer Rekursion. Könntest du, wenn du die Anzahl a_n der Dyck-Pfade von (0,0) nach (2n,0) für ein n kennst (und falls benötigt auch a_(n-1), a_(n-2), ...), daraus die Anzahl a_(n+1) der Dyck-Pfade von (0,0) nach (2n+2,0) ableiten? Alle Pfade nach (2n,0) könnte man ja durch Anfügung von (1,1) und (1,-1) zu Pfaden nach (2n+2,0) erweitern. Darüber hinaus muss man aber auch noch die Anzahl der Pfade kennen, die von (0,0) nach (2n,2) führen. Vielleicht kann man das auf die (theoretisch bekannten) niedriger indizierten Anzahlen zurückführen und so eine Rekursionsgleichung aufstellen. LG sibelius84 edit: es könnte hilfreich sein, mit einer doppelt indizierten Folge a_(n,k) := Anzahl der Pfade von (0,0) nach (2n,2k) (mit den beschriebenen Eigenschaften) zu arbeiten, so dass a_n = a_(n,0). Manchmal muss man die Angel etwas weiter auswerfen, um zum Schluss neben einigen anderen insbesondere auch den gewünschten Fisch im Netz zu haben.
13.11.2017, 19:52	FelNa1109	Auf diesen Beitrag antworten »
Erstmal danke für das Antworten. Die Anzahl der Dyck-Pfade von $\begin{eqnarray} (0,0) \end{eqnarray}$ nach $\begin{eqnarray} (2n,0) \end{eqnarray}$ sind doch die Catalan-Zahlen, oder? ! Also: $\begin{eqnarray} \frac{1}{n+1} \begin{pmatrix} 2n \\ n \end{pmatrix} \end{eqnarray}$
13.11.2017, 20:16	sibelius84	Auf diesen Beitrag antworten »
Ja, schon richtig - nur da musst du ja erstmal irgendwie noch hinkommen
13.11.2017, 20:17	FelNa1109	Auf diesen Beitrag antworten »
Außerdem könnte ich doch einen Dyck-Pfad der Länge 2n aufteilen in: 2n = oben + Weg1 + Weg2 + unten wobei: Weg1 = 2k, Weg2 = 2n-2k-2 Wenn also jetzt $\begin{eqnarray} f(n) \end{eqnarray}$ die Anzahl der Dyck-Pfade von $\begin{eqnarray} (0,0) \end{eqnarray}$ nach $\begin{eqnarray} (2n,0) \end{eqnarray}$ ist, kann man doch auch $\begin{eqnarray} f(n)=\sum\limits_{k=1}^{n} f(k)f(n-k-1) \end{eqnarray}$ finden oder?
13.11.2017, 20:20	sibelius84	Auf diesen Beitrag antworten »
Ich fürchte, das ist ein Schnellschuss, da du damit implizit voraussetzt, dass Weg 1 nach 2k auf der x-Achse endet und Weg 2 dort anfängt. Dass die erste Bewegung immer "hoch" sein muss und die letzte immer "runter", ist richtig.
Anzeige

13.11.2017, 20:34	FelNa1109	Auf diesen Beitrag antworten »
Meinst du damit, dass ich das k einschränken soll? Also z.B. $\begin{eqnarray} 0\leq k\leq n-1 \end{eqnarray}$
13.11.2017, 21:30	FelNa1109	Auf diesen Beitrag antworten »
Also zusammenfassend weiß ich jetzt, dass ich einen Dyck-Pfad der Länge 2n wie folgt aufteilen kann: $\begin{eqnarray} 2n = o + Weg1 + Weg2 + u \end{eqnarray}$ wobei: $\begin{eqnarray} o=oben, u=unten \end{eqnarray}$ $\begin{eqnarray} Weg1=2k, 0\leq k\leq n-1 \end{eqnarray}$ $\begin{eqnarray} Weg2=2n-2k-2 \end{eqnarray}$ Wenn also mein $\begin{eqnarray} f(n) \end{eqnarray}$ die Anzahl aller Dyck-Pfade ist, hab ich: $\begin{eqnarray} f(n)=\sum\limits_{k=1}^{n-1} f(k)f(n-k-1) \end{eqnarray}$ Nur wie ich damit jetzt auf die erzeugende Funktion kommen soll, weiß ich leider nicht
14.11.2017, 11:26	sibelius84	Auf diesen Beitrag antworten »
Wie bereits gesagt - ich fürchte, deine Summe stimmt nicht. Damit würdest du über alle Wege summieren, die bei 2, 4, 6, ..., 2n-2 einen Zwischenstopp auf der x-Achse einlegen. Das heißt, du hättest nicht nur das Problem, dass das eine echte Beschränkung der Allgemeinheit ist (weil du zB "n-mal oben, n-mal unten" nicht dabei hast), sondern auch noch, dass du Wege doppelt zählst (weil du zB "oben-unten-oben-unten-...-oben-unten" direkt n-mal gezählt hast statt nur 1-mal). Versuch' doch, wie ebenfalls weiter oben gesagt, mal zu setzen $\begin{eqnarray} a_{(n,k)} := \text{Anzahl der Pfade von }(0,0)\text{ nach }(2n,2k) \end{eqnarray}$ . Könntest du dann a_(n+1) = a_((n+1),0) - rekursiv - ausdrücken als Summe irgendwelcher a_(j,k), wobei alle j kleinergleich n sein müssen?
14.11.2017, 12:31	FelNa1109	Auf diesen Beitrag antworten »
a (n+1,0) = a (k+1, 1) + a (n-k, -1)...
14.11.2017, 13:12	FelNa1109	Auf diesen Beitrag antworten »
Also a(2n,0)=a (k+1,1)+a (2n-k+1,-1)
14.11.2017, 14:59	sibelius84	Auf diesen Beitrag antworten »
Ich glaube nicht, dass es Sinn macht, negative Werte für k zuzulassen. Meine Überlegung war die folgende: Wie kommt man von (0,0) nach (2n+2,0)? (Also gesucht: $\begin{eqnarray} a_{n+1}=a_{(n+1,0)} \end{eqnarray}$ .) Nun: Entweder, indem man von (0,0) nach (2n,0) geht und dann "oben-unten" macht (also $\begin{eqnarray} a_{(n,0)} \end{eqnarray}$ ); oder, indem man von (0,0) nach (2n,2) geht und dann "unten-unten" macht (also $\begin{eqnarray} a_{(n,1)} \end{eqnarray}$ .) Damit haben wir die Rekursionsgleichung: $\begin{eqnarray} a_{(n+1,0)}=a_{(n,0)}+a_{(n,1)}. \end{eqnarray}$ Nun sollen ja in der Endform der Rekursion die a_(n,k) mit k ungleich Null nicht vorkommen. Also müssen wir in der obigen Zeile weitermachen und a_(n,1) noch durch Ausdrücke a_(m,0) ersetzen, mit m<n. Das wäre so mein Herangehen an die Sache - verstehst du, wie ich das meine? Ich vermute mal, im Ergebnis hätte man da eine ziemlich wilde Summe $\begin{eqnarray} \sum_{j=1}^n \lambda_ja_j \end{eqnarray}$ stehen (mit natürlichen lambdas), aber vielleicht ja dann so, dass man die erzeugende Funktion draus basteln könnte.

Neue Frage »

Antworten »

Dyck-Pfade

Verwandte Themen