n-Dyck-Weg < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Ein n-Dyck-Weg ist ein (n, n)-Treppenlauf, der keinen Gitterpunkt (a, b) mit b < a durchläuft (also immer "oberhalt der Diagonale bleibt"). Wieviele n-Dyck-Wege gibt es? |
Ok, ich hab das so gelöst: Bei einem n * n-Gitter ist der Weg von rechts unten nacht links oben 2n - 2 lang. Jetzt berechne ich alle Möglichen Weg von rechts unten nach links oben:
[mm] \vektor{2n - 2 \\ n}
[/mm]
Da nur die Hälfte aller Weg begehbar ist, muss ich das nur noch durch 2 teilen.
Stimmt das so?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hi,
> Ein n-Dyck-Weg ist ein (n, n)-Treppenlauf, der keinen
> Gitterpunkt (a, b) mit b < a durchläuft (also immer
> "oberhalt der Diagonale bleibt"). Wieviele n-Dyck-Wege gibt
> es?
> Ok, ich hab das so gelöst: Bei einem n * n-Gitter ist der
> Weg von rechts unten nacht links oben 2n - 2 lang.
Ich denke, das Gitter beginnt wieder bei (0,0), dann wäre die Weglänge 2n.
> Jetzt berechne ich alle Möglichen Weg von rechts unten nach
> links oben:
>
> [mm]\vektor{2n - 2 \\ n}[/mm]
Die Gesamtanzahl an Möglichkeiten wäre dann unter obiger Voraussetzung [mm] \vektor{2n \\ n}
[/mm]
>
> Da nur die Hälfte aller Weg begehbar ist, muss ich das nur
> noch durch 2 teilen.
Nein. Es stimmt zwar, dass es zu jedem Weg einen 'symmetrischen' Weg gibt, bei dem alle Schritte sozusagen an der Diagonale von (0,0) nach (n,n) gespiegelt sind. Aber bei deutlich mehr Wegen wird diese Diagonale vom Weg gekreuzt. Das darf aber nicht sein, da es dann einen Wegpunkt (a,b) unterhalb der Diagonalen gibt mit a>b.
Bleiben wir bei dem, was teufel im anderen Thread geschrieben hat.
Ein Treppenlauf lässt sich darstellen als Folge der Zeichen O, R wobei O für Schritt nach oben und R für Schritt nach rechts steht. In dieser Aufgabe gibt es jeweils n "O" und "R" und die Zeichenkette hat die Gesamtlänge 2n. Wegen der Zusatzbedingung, darf keine Teilzeichenkette (die nur einen Anfang des kompletten Wegs, dargestellt als Zeichenkette, enthält) mehr "R" als "O" enthalten. Denn dann befinden wir uns unterhalb der Diagonalen.
Für n=3 wäre OORORR ein gültiger Weg. ORROOR jedoch nicht, da die Anfangszeichenkette "ORR" obige Bedingung nicht erfüllt.
Ihr hattet bestimmt für die Berechnung der Anzahl gültiger Zeichenketten eine geeignete Formel.
Gruß
|
|
|
| |
|
Ich hab noch ein bisschen nachgedacht und bin darauf gekommen:
[mm] \vektor{2n \\ n} [/mm] - [mm] \bruch{1}{n!} \vektor{2n \\ n}
[/mm]
Ist das richtig? Ob wir eine Formel dafür bekommen haben, kann ich nicht sagen, auf jeden Fall wurde dies dann nicht explizit erwähnt. Ansonsten bin ich grad mit meinem Latein am Ende.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:11 Mo 28.02.2011 | | Autor: | Teufel |
Hi!
Für n=2 stimmt die Formel schon leider nicht.
Ich denk auch nochmal darüber nach.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:23 Mo 28.02.2011 | | Autor: | Teufel |
Also ich habe eine rekursive Formel gefunden.
Dazu zerlege ich alle Wege von (0,0) bis (n,n) in disjunkte Mengen. Die Gesamtzahl aller Wege kennst du ja, diese war [mm] \vektor{2n \\ n}. [/mm] Nun sein [mm] W_n [/mm] die gesuchte Anzahl an n-Dyck-Wegen. Dann sei [mm] W_0=1 [/mm] (das macht die Formel etwas kompakter, man kann das aber auch gern ohne diese Konvention machen).
Dann gilt:
[mm] \vektor{2n \\ n}=W_n+W_0*\vektor{2n-1 \\ n-1}+W_1*\vektor{2n-3 \\ n-2}+...+W_{n-1}*\vektor{1 \\ 0}
[/mm]
[mm] \gdw [/mm]
[mm] W_n=\vektor{2n \\ n}-\summe_{i=0}^{n-1}W_i*\vektor{2n-2i-1 \\ n-i-1}, W_0=1.
[/mm]
Der Grund:
Nehmen wir z.B. mal ein 3x3-Gitter.
Dann gibt es insgesamt [mm] \vektor{6 \\ 3} [/mm] Wege von unten links nach oben rechts.
Diese Wege kann man in die folgenden Mengen Zerlegen: Die Menge der gesuchten 3-Dyck-Wege (davon gibt es also [mm] W_3 [/mm] Stück).
Dann die Menge der Wege, die schon nach der 1. Richtung kein 3-Dyck-Weg mehr sein können (dafür gibt es nur [mm] 1=W_0 [/mm] Möglichkeit, nämlich R, also wenn man direkt nach rechts läuft). Also wenn man nun ein Feld am Anfang nach rechts läuft, dann hat man noch [mm] \vektor{5 \\ 2} [/mm] Möglichkeiten den schon zum Scheitern verurteilten Weg zu Ende zu bringen. Daher gibt es [mm] W_0* \vektor{5 \\ 2} [/mm] solcher schon nach dem 1. Schritt gescheiterten Wege.
Dann die Menge der Wege, die nach der 3. Richtung kein 3-Dyck-Weg mehr sein können (dafür gibt es nur [mm] 1=W_1 [/mm] Möglichkeit, nämlich ORR). Hier hat man dann noch [mm] \vektor{3 \\ 1} [/mm] Möglichkeiten den Weg zu Ende zu bringen. Daher gibt es [mm] W_1*\vektor{3 \\ 1} [/mm] solcher schon nach dem 3. Schritt gescheiterten Wege.
Dann die Menge der Wege, die nach der 5. Richtung kein 3-Dyck-Weg mehr sein können (dafür gibt es [mm] 2=W_2 [/mm] Möglichkeiten, nämlich ORORR oder OORRR). Hier hat man dann noch [mm] \vektor{1 \\ 0}=1 [/mm] Möglichkeiten den Weg zu Ende zu bringen. Daher gibt es [mm] W_2*\vektor{1 \\ 0} [/mm] solcher schon nach dem 5. Schritt gescheiterten Wege.
Insgesamt gilt also
[mm] \vektor{6 \\ 3}=W_3+W_0*\vektor{5 \\ 2}+W_1*\vektor{3 \\ 1}+W_2*\vektor{1 \\ 0}.
[/mm]
Damit kannst du dann immer nach und nach [mm] W_n [/mm] berechnen. Wie man die Rekursion auslöst (falls verlangt), weiß ich auch gerade nicht.
Dann hast du z.B.
[mm] W_0=W_1=1
[/mm]
[mm] W_2=2
[/mm]
[mm] W_3=5
[/mm]
[mm] W_4=14
[/mm]
[mm] W_5=42
[/mm]
...
|
|
|
|
