Kombinatorik: Alphabet {0,1}

10.01.2010, 19:48	dennis7	Auf diesen Beitrag antworten »
Kombinatorik: Alphabet {0,1} Hallo, ich habe eine Frage zur Kombinatorik: Sei n e N. Wieviele Wörter der Länge n über dem Alphabet {0,1} gibt es, in denen genau dreimal die Zeichenfolge 10 vorkommt? Ich habe hier wirklich keine Ahnung wie ich ansetzten soll. Alle Wörter der Länge n sind 2^n. Wäre nett wenn mir jmd helfen könnte Grüße dennis
11.01.2010, 17:39	dennis7	Auf diesen Beitrag antworten »
kann mir keiner helfen, ich probier da jetzt schon lange rum, bisher hab ich nur rausgefunden wie viele wörter der länge n über 0,1 ohne 10 es gibt: (2+n-1)über5 und dass wohl 4 aus n-6 gewählt werden muss (weil ...10...10...10...). wäre wirklich nett wenn mir da jmd weiterhelfen kann...
11.01.2010, 19:08	wisili	Auf diesen Beitrag antworten »
Das Problem ist nicht so einfach ... Es interessiert mich, ich weiss im Moment aber auch noch nichts Verwertbares.
11.01.2010, 20:49	wisili	Auf diesen Beitrag antworten »
Dein Schema ... 10 ... 10 ... 10 ... hat mir zur Lösung verholfen. Bei den 4 Lücken ... muss man die noch fehlenden n-6 Ziffern einfügen, aber so, dass nie eine 0 direkt nach einer 1 auftritt. Das bedeutet, dass jeder der 4 Blöcke leer sein kann, oder 1 ist, oder 0 ist oder 01 oder 001 oder 0111 oder 00001111 oder 00011111111 oder ... Jeder der 4 Blöcke zerfällt somit in einen Nullerblock und einen Einerblock. Wir haben also 4 x 2 = 8 Plätze, wo wir die n-6 Ziffern unterbringen müssen: Wir wählen n-6 mal einen von 8 Plätzen. Diese kombinatorische Grundaufgabe wird so gelöst (Kombinationen mit Wiederholungen, s. Formelsammlung): $\begin{eqnarray} \begin{pmatrix} 8+(n-6)-1 \\ n-6 \end{pmatrix} = \begin{pmatrix} n+1 \\ 7 \end{pmatrix} \end{eqnarray}$ Für n = 6, 7, 8, 9, 10, 11, 12, ... ergeben sich die Anzahlen 1, 8, 36, 120, 330, 792, 1716, ... Für dich bleibt nun noch die Verallgemeinerung: k mal 10 (statt 3 mal 10).
12.01.2010, 14:11	dennis7	Auf diesen Beitrag antworten »
Hey wisili, vielen dank für deine Antwort, die aufgabe hat mich schon ganz verrückt gemacht. Verallgemeinerung müsste sein: statt 8 nimmt man (k+1)2 und statt n-6 n-(2k)
12.01.2010, 14:16	Mystic	Auf diesen Beitrag antworten »
Ja, das ist tatsächlich eine ganz interessante Frage und eine der eher seltenen Gelegenheiten, wo man hier mehr als nur einige Zehntelsekunden braucht, um sofort die Lösung zu sehen... Ich persönlich bin das so angegangen, dass ich mir zuerst überlegt habe, wieviele monotone Binärfolgen der Länge n es gibt...Die Anwort ist natürlich n+1 und die erzeugende Funktion f(x) dafür daher $\begin{eqnarray} f(x)=\sum_{n=0}^{\infty} (n+1)x^n =\frac 1 {(1-x)^2} \ \end{eqnarray}$ Im gegebenen Fall muss ich nun einfach 4 monotone Binärfolgen (die u.U. natürlich auch leer sein können!) durch 3 Binärblöcke 10 voneinander getrennt hinschreiben.... De facto muss ich also 4 monotone Binärfolgen auswählen, sodass sie zusammen eine Binärfolge der Länge n-6 ergeben... Damit ist die erzeugende Funktion g(x) für mein eigentliches Problem gegeben durch $\begin{eqnarray} g(x)= \frac {x^6} {(1-x)^8} \end{eqnarray}$ In Derive könte man z.B. die Koeffizienten $\begin{eqnarray} a_n \end{eqnarray}$ der Taylorreihe von g(x) folgendermaßen berechnen: a(n) := LIM(dif((1 - x)^(-8), x, n - 6), x, 0)/(n - 6)! und erhält so z.B. VECTOR(a(n), n, 6, 15) = [1, 8, 36, 120, 330, 792, 1716, 3432, 6435, 11440] Ich war jetzt zu faul, um die explizite Formel von wisili daraus herzuleiten, aber im Prinzip sollte das kein Problem sein...
Anzeige

12.01.2010, 14:39	wisili	Auf diesen Beitrag antworten »
@dennis7 Deine Verallgemeinerung ist perfekt. Interessant wäre noch, k von 0 bis n/2 laufen zu lassen und alle Resultate zu addieren: Das müsste ja dann alle 2^n Binärfolgen geben. @Mystic Deine Lösung interessiert mich sehr. Aber die Sache mit den erzeugenden Funktionen ist mir nicht geläufig. Aber ich habe jetzt Gelegenheit, mich da mal zu vertiefen ... Danke.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »