Wörter der Länge k mit mindestens zwei a

19.02.2011, 22:33	S_A_S	Auf diesen Beitrag antworten »
Wörter der Länge k mit mindestens zwei a Wenn ich über dem Alphabet {a, b, c, d, e} Wörter der Länge k >= 2 mit mindestens zwei a berechen muss. Dann ist das doch einfach $\begin{eqnarray} \sum\limits_{k=2}^k (k-i) 4^{i} \end{eqnarray*}$ Die Summe ist klar, weil "mindestens zwei" also ist alles von zwei bis k möglich. Das k-i weil ich ja bei i jew. i a mal a habe. Damit dürfen meine a's k-i plätze belegen. Also bilde ich ganz normal ne Variation mit Widerholung von einer einelementigen menge (meine a's) in die Menge der Positionen im Wort ab. also (k-i) ^1 = k-i dann habe ich für die restlichen i Plätze ja nur noch vier Buchstaben übrig. Damit habe ich 4^i Möglichkeiten- da sich ja auch hier alles wiederholen kann. Sind meine Überlegungen so weit richtig?
19.02.2011, 22:41	HAL 9000	Auf diesen Beitrag antworten »
Ich verstehe weder deine Formel (statt Index $\begin{eqnarray} k \end{eqnarray}$ muss doch da Index $\begin{eqnarray} i \end{eqnarray}$ hin, oder?) noch deren Begründung. Ich würde einfach über das Komplement gehen: Berechne die Anzahl aller Wörter der Länge $\begin{eqnarray} k \end{eqnarray}$ abzüglich der mit keinem oder genau einem a.
19.02.2011, 22:54	S_A_S	Auf diesen Beitrag antworten »
Sorry, vertippt gehabt. Natürlich läuft die Summe von i=2 bis k. Ich denke die Wörter mit einem oder keinem a dürfte dazu äquivalent sein.
19.02.2011, 23:12	HAL 9000	Auf diesen Beitrag antworten »
Dem $\begin{eqnarray} 4^i \end{eqnarray}$ nach zu urteilen ist bei dir $\begin{eqnarray} i \end{eqnarray}$ die Anzahl der Buchstaben ungleich a im Wort! Für diese Buchstaben gibt es aber $\begin{eqnarray} \binom{k}{i} \end{eqnarray}$ Möglichkeiten erstmal deren Position im Wort festzulegen. Und die Summation verläuft dann nicht von $\begin{eqnarray} i=2 \end{eqnarray}$ bis $\begin{eqnarray} k \end{eqnarray}$ , sondern von $\begin{eqnarray} i=0 \end{eqnarray}$ bis $\begin{eqnarray} k-2 \end{eqnarray}$ . Insgesamt also $\begin{eqnarray} \sum_{i=0}^{k-2} \binom{k}{i} 4^i \end{eqnarray}$ . Ist $\begin{eqnarray} i \end{eqnarray}$ bei dir hingegen die Anzahl der a im Wort, dann lautet die Formel $\begin{eqnarray} \sum_{i=2}^{k} \binom{k}{i} 4^{k-i} \end{eqnarray}$ . Beides ist äquivalent, und gleich dem $\begin{eqnarray} 5^k-4^k-k4^{k-1} \end{eqnarray}$ , das sich gemäß meinem obigen Vorschlag ergibt. Im Klartext: Ich halte deine Formel für durch und durch falsch.
19.02.2011, 23:36	S_A_S	Auf diesen Beitrag antworten »
oh ich sehs grad selbst. Die Verteilung der a's stellt ja insich keine Variation dar. Ich kann a von a ja nicht unterscheiden - daher spielt es auch keine Rolle in welcher Reihenfolge ich die a's am Anfang verteile. Gut jetzt hab ich das denke ich richitg verstanden. Lustigerweise bin ich auf die Komplementdarstellung auf anhieb korrekt gekommen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »