Wörter der Länge n ... < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Gegeben sei ein Alphabet [mm] \summe_{}^{} [/mm] ={0,1,#}.
(a) Wie viele verschiedene Wörter der Länge n gibt es?
(b) Wie viele Wörter der Länge n gibt es in denen ein Symbol c [mm] \in \summe_{}^{} [/mm] genau k-mal vorkommen. |
Hallihallo!
Ja im Prinzip ist es ja Grundlagen der Informatik, aber ich dachte mir dass es eigentlich Kombinatorik ist und hab es deshalb hier gepostet.
a habe ich bereits gelöst, wenn ich mich nicht irre kommt da [mm] 3^n [/mm] raus.
Allerdings hänge ich nun bei b, hab eigentlich gar keinen Ansatz der mich zu irgendetwas logischen führt.
Bin auch durch Beispiele auf nichts grünes gekommen und erhoffe mir von euch Hilfe.
Danke schonmal im Voraus!
|
|
| |
|
> Gegeben sei ein Alphabet [mm]\summe_{}^{}[/mm] ={0,1,#}.
> (a) Wie viele verschiedene Wörter der Länge n gibt es?
> (b) Wie viele Wörter der Länge n gibt es in denen ein
> Symbol c [mm]\in \summe_{}^{}[/mm] genau k-mal vorkommen.
> Hallihallo!
> Ja im Prinzip ist es ja Grundlagen der Informatik, aber
> ich dachte mir dass es eigentlich Kombinatorik ist und hab
> es deshalb hier gepostet.
>
> a habe ich bereits gelöst, wenn ich mich nicht irre kommt
> da [mm]3^n[/mm] raus.
![[ok]](/images/smileys/ok.gif "[ok]")
> Allerdings hänge ich nun bei b, hab eigentlich gar keinen
> Ansatz der mich zu irgendetwas logischen führt.
Das fragliche Symbol [mm] $c\in \Sigma$, [/mm] das genau $k$ mal vorkommen soll, kannst Du auf [mm] $\binom{3}{1}=3$ [/mm] Arten auswählen. Nachdem Du es ausgewählt hast, kannst Du die $k$ Positionen innerhalb eines Wortes der Länge $n$, an denen dieses Symbol $c$ vorkommt, auf [mm] $\binom{n}{k}$ [/mm] Arten wählen. Schliesslich kannst Du die restlichen $n-k$ Positionen noch mit den restlichen $2$ Symbolen aus [mm] $\Sigma\backslash\{c\}$ [/mm] auf [mm] $2^{n-k}$ [/mm] Arten belegen. Insgesamt erhält man so ('Produktsatz der Kombinatorik'): [mm] $3\cdot \binom{n}{k}\cdot 2^{n-k}$ [/mm] Möglichkeiten.
|
|
|
|
