Kombinatorik: Anzahl Wörter

13.08.2013, 12:04

JeremyA

Kombinatorik: Anzahl Wörter

Hallo!

Aufgabe: Wie viele Wörter der Länge 8 gibt es über dem Alphabet {a,b,c,d,e}, die keinen der Buchstaben genau 5-mal enthalten?

Ich weiß nicht so recht weiter... Mein bisheriger Ansatz:

Insgesamt können $\begin{eqnarray*} 5^8 \end{eqnarray*}$ Wörter gebildet werden. Nun muss ich davon die abziehen, bei denen keiner der Buchstaben 5-mal vorkommt. Das weiß ich schonmal nicht so recht wie das kombinatorisch ausschauen kann. Meine Idee dazu (Multinomialkoeffizient): $\begin{eqnarray*} \binom {8}{5,2,1} * 5 \end{eqnarray*}$

Ist das dann: $\begin{eqnarray*} 5^8 - \binom {8}{5,2,1} \end{eqnarray*}$ ?

Jeremy

13.08.2013, 12:12

HAL 9000

Auf diesen Beitrag antworten »

RE: Kombinatorik: Anzahl Wörter

Zitat:

Original von JeremyA
Insgesamt können $\begin{eqnarray*} 5^8 \end{eqnarray*}$ Wörter gebildet werden. Nun muss ich davon die abziehen, bei denen keiner der Buchstaben 5-mal vorkommt.

Kleiner Verschreiber: Du musst die abziehen, die einen Buchstaben genau 5-mal besitzen. Augenzwinkern

Es gibt dann

* $\begin{eqnarray*} 5 \end{eqnarray*}$ Möglichkeiten, diesen einen fünffach vorkommenden Buchstaben aus {a,b,c,d,e} zu wählen
* $\begin{eqnarray*} \binom{8}{5} \end{eqnarray*}$ Möglichkeiten, diesen fünf Vorkommen im Wort zu positionieren
* $\begin{eqnarray*} 4^3 \end{eqnarray*}$ Möglichkeiten, die restlichen drei (inzwischen feststehenden) Positionen mit anderen Buchstaben zu befüllen

Das alles noch miteinander multiplizieren, fertig. Zu beachten ist, dass dies nur wegen $\begin{eqnarray*} 5>\frac{8}{2} \end{eqnarray*}$ so einfach klappt - bei "genau 4-mal" geht das nicht mehr so einfach...

13.08.2013, 12:29

JeremyA

Auf diesen Beitrag antworten »

RE: Kombinatorik: Anzahl Wörter

Zitat:

Original von HAL 9000
Kleiner Verschreiber: Du musst die abziehen, die einen Buchstaben genau 5-mal besitzen. Augenzwinkern

Ups. Stimmt.

Zitat:

Original von HAL 9000
* $\begin{eqnarray*} 5 \end{eqnarray*}$ Möglichkeiten, diesen einen fünffach vorkommenden Buchstaben aus {a,b,c,d,e} zu wählen
* $\begin{eqnarray*} \binom{8}{5} \end{eqnarray*}$ Möglichkeiten, diesen fünf Vorkommen im Wort zu positionieren

Also $\begin{eqnarray*} 5 * \binom {5}{8} \end{eqnarray*}$

Zitat:

Original von HAL 9000
* $\begin{eqnarray*} 4^3 \end{eqnarray*}$ Möglichkeiten, die restlichen drei (inzwischen feststehenden) Positionen mit anderen Buchstaben zu befüllen

Ok. 4 Restbuchstaben mit Wortlänge 3.

Also gesamt: $\begin{eqnarray*} 5^8 - (5* \binom {8}{5} * 4^3) \end{eqnarray*}$

Zitat:

Original von HAL 9000
Zu beachten ist, dass dies nur wegen $\begin{eqnarray*} 5>\frac{8}{2} \end{eqnarray*}$ so einfach klappt - bei "genau 4-mal" geht das nicht mehr so einfach...

Das verstehe ich nicht. Wie wäre denn obige Aufgabe mit Wortlänge 7?

Jeremy

13.08.2013, 12:54

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von JeremyA

Zitat:

Original von HAL 9000
Zu beachten ist, dass dies nur wegen $\begin{eqnarray*} 5>\frac{8}{2} \end{eqnarray*}$ so einfach klappt - bei "genau 4-mal" geht das nicht mehr so einfach...

Das verstehe ich nicht. Wie wäre denn obige Aufgabe mit Wortlänge 7?

Analog die Anzahl $\begin{eqnarray*} 5^8 - 5 \cdot \binom {8}{7} \cdot 4^1 \end{eqnarray*}$ , es ist ja auch $\begin{eqnarray*} 7>\frac{8}{2} \end{eqnarray*}$ .

Das Problem sind Mehrfachvorkommen 4-mal oder weniger, weil diese dann für mehrere Buchstaben zugleich im Wort auftreten können.

13.08.2013, 13:42

JeremyA

Auf diesen Beitrag antworten »

Also ich meinte anstatt der Wortlänge 8 nun Wortlänge 7. Keinen der Buchstaben genau 5-mal enthalten bleibt bestehen.

Aber hier würde ja auch $\begin{eqnarray*} 5 > \frac {8}{2} \end{eqnarray*}$ gelten, also $\begin{eqnarray*} 5^7 - (5 * \binom {7}{5} * 4^2) \end{eqnarray*}$

Jeremy

13.08.2013, 13:59

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von JeremyA
Aber hier würde ja auch $\begin{eqnarray*} 5 > \frac {8}{2} \end{eqnarray*}$ gelten

Du meinst eher $\begin{eqnarray*} 5 > \frac {7}{2} \end{eqnarray*}$ - ja, das ist erfüllt.

13.08.2013, 14:19

JeremyA

Auf diesen Beitrag antworten »

Ja, natürlich.
Danke für Deine Hilfe!

Neue Frage »

Antworten »

Kombinatorik: Anzahl Wörter

Verwandte Themen