Catalan- zahl: es sei ...

Question

Es sei c_n die Anzahl aller Wörter der Länge 2n mit genau n Buchstaben X und n Buchstaben Y, wobei jedes Anfangsstück des Wortes mindestens genauso viele X wie Y enthalte. ( jedes solche Wort beginnt also mit X und endet mit Y. Zulässige Wörter sind XY, XYXY,XXYY, nicht aber XX, XYYX.) bestimmen sie die folge (c_n)

Comments

Was ist denn genau das Problem? Wenn, wie der Titel andeutet, schon bekannt ist, dass die Folge der Wortanzahlen die Catalan-Zahlen sind, dann ist die Aufgabe "Bestimmen Sie die Folge (c_n)" doch eigentlich schon erledigt, oder? Kannst Du vielleicht die exakte Aufgabenstellung und den Aufgabenkontext nachreichen?

---

Mal ein Anfang

Es sei z_n die Anzahl aller Wörter der Länge 2n mit genau n Buchstaben X und n Buchstaben Y, ...

z_n = (2n tief n) . Binomialkoeffizent: Man wählt n beliebige Stellen für den Buchstaben X und besetzt dann alle andern Stellen mit Y.

Nun zur Fortsetzung:

.....,wobei jedes Anfangsstück des Wortes mindestens genauso viele X wie Y enthalte.

Was scheidet alles aus? Man könnte vielleicht geschickt abzählen:

Sicher darf am Schluss kein X stehen. Das wäre aber in (2n-1 tief n-1) Fällen der Fall.

usw. 

Oder: Man überlegt sich, ob jeweils ein bestimmter Anteil der (2n tief n) Fälle nicht in Frage kommen.

Weiss aber momentan nicht, welcher Ansatz dich schneller zum Ziel bringt. Was ja offenbar https://de.wikipedia.org/wiki/Catalan-Zahl sein soll.

Answer 1

Hi,

Das ist doch garkeine Folge c_n. c_n ist einfach nur das was du oben definiert hast. Oder meinst  du c_1,c_2,...,c_n,...? Na, das hast du doch selber gesagt:

c_n = (a_1 a_2 ... a_2n) mit a_k ∈ {X,Y} und es gibt n von a_1...a_2n die X sind.

Legendär