+1 Daumen
872 Aufrufe

Es sei cn 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 (cn)

Avatar von

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 (cn)" doch eigentlich schon erledigt, oder? Kannst Du vielleicht die exakte Aufgabenstellung und den Aufgabenkontext nachreichen?

Mal ein Anfang

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

zn = (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.

1 Antwort

0 Daumen

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

Avatar von 4,8 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community