Anzahl von Palindromen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:59 Mo 24.04.2006 | | Autor: | dobberph |
| Aufgabe | | Wie viele Palindrome der Länge k über einem Alphabet der Länge n gibt es? Beweisen Sie Ihre Behauptung. (gemeint sind hier Wortpalindrome, was aber eigentlich egal ist.) |
Hi ihr,
ich habe noch ein Problem und hoffe ihr könnt mir helfen.
Ich habe nur einen Hinweis bezüglich der Zahlenpalindrome:
Dieser gibt es:
bei 1 Stelle 9 Palindrome,
bei 2 Stellen 9 Palindrome,
bei 3 Stellen 90 Palindrome,
bei 5 Stellen 90 Palindrome, usw.
Allerdings sehe ich hier keine Regel und diese dann noch auf n zu beziehen und nicht nur auf n=9 krieg ich nicht hin.
Vielen Dank,
DerTobi
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:14 Mo 24.04.2006 | | Autor: | felixf |
Hallo Tobi!
> Wie viele Palindrome der Länge k über einem Alphabet der
> Länge n gibt es? Beweisen Sie Ihre Behauptung. (gemeint
> sind hier Wortpalindrome, was aber eigentlich egal ist.)
> Hi ihr,
>
> ich habe noch ein Problem und hoffe ihr könnt mir helfen.
>
> Ich habe nur einen Hinweis bezüglich der Zahlenpalindrome:
> Dieser gibt es:
> bei 1 Stelle 9 Palindrome,
> bei 2 Stellen 9 Palindrome,
> bei 3 Stellen 90 Palindrome,
> bei 5 Stellen 90 Palindrome, usw.
>
> Allerdings sehe ich hier keine Regel und diese dann noch
> auf n zu beziehen und nicht nur auf n=9 krieg ich nicht
> hin.
Mach erstmal ne Fallunterscheidung zwischen $k$ gerade und $k$ ungerade.
Ist $k$ gerade, so kannst du die ersten $k/2$ Buchstaben beliebig waehlen (also [mm] $n^{k/2}$ [/mm] Moeglichkeiten), und die letzten $k/2$ Buchstaben werden dann eindeutig durch die ersten $k/2$ Buchstaben bestimmt. Es gibt also genau [mm] $n^{k/2}$ [/mm] Palindrome der Laenge $k$, wenn $k$ gerade ist.
Bekommst du den Fall $k$ ungerade selber hin?
Wenn du beide Faelle hast, dann versuch mal eine Formel fuer beide Faelle gleichzeitig aufzuschreiben. Dafuer benutze am besten [mm] $\left\lceil \frac{k}{2} \right\rceil [/mm] = [mm] \begin{cases} \frac{k}{2}, & k \text{ gerade,} \\ \frac{k+1}{2}, & k \text{ ungerade} \end{cases}$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:50 Mo 24.04.2006 | | Autor: | dobberph |
Ach ja,
dann sind es für k ungerade $ [mm] n^{k-1/2} [/mm] $ + n ?
Und wie faß ich die dann zusammen?
Mfg,
DerTobi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:18 Mo 24.04.2006 | | Autor: | felixf |
> dann sind es für k ungerade [mm]n^{k-1/2}[/mm] + n ?
Nein, es sind [mm] $n^{(k-1)/2} \cdot [/mm] n = [mm] n^{(k+1)/2}$.
[/mm]
> Und wie faß ich die dann zusammen?
Siehst du es jetzt?
LG Felix
|
|
|
|
