Beweis Catalanische Zahlen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Auf einer Kreislinie sind 2n Punkte ausgezeichnet. Auf wie viele Arten kann man diese so zu zweien mit Strecken verbinden, dass keine Überschneidungen auftreten?
Hinweis: Stellen Sie für die Anzahl [mm] f_{n} [/mm] der verschiedenen Möglichkeiten eine Rekursionsformel auf und finden Sie [mm] f_{n} [/mm] durch Betrachtung von [mm] \summe_{n=0}^{\infty}f_{n}x^{n} [/mm] |
Hallo zusammen,
durch Probieren und das Internet konnte ich bereits herausfinden, dass obiges Problem ein Standartbeispiel für die Catalan-Zahlen darstellt.
Deren Rekursionsgleichung [mm] f_{n}=\summe_{k=0}^{n-1}f_{k}f_{n-1-k} [/mm] für [mm] n\ge1 [/mm] und [mm] f_{0}=1 [/mm] konnte ich finden, ebenso die direkte Darstellung [mm] f_{n}=\bruch{1}{n+1}\vektor{2n\\n}.
[/mm]
Nun allerdings mein Problem; mir ist die Beweistechnik nicht klar. Zwar haben wir in der Übung ähnliches zur Fibonacci-Folge gemacht, indem wir die Gleichheit zweier Rekursionen nachgewiesen haben, aber inwiefern mir diese unendliche Reihe aus dem Hinweis helfen soll, bzw. wie ich x geschickt wählen müsste, ist mir völlig unklar.
Bin für jeden Tipp dankbar.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Mi 13.04.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
