Rekurrenzrelation... < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:12 Di 24.05.2005 | | Autor: | squeezer |
Hallo
Ich habe folgende Aufgabe zu bearbeiten:
Sei [mm] a_j [/mm] die Anzahl der j-Wörter über dem Alphabet {1,...,n}, die eine ungerade Anzahl von Einsen enthalten. Leiten sie eine Rekurrenzrelation für die Folge [mm] {(a_j)^{ \infty}}_{j=0} [/mm] her.
Ich habe mir nun die Ersten [mm] a_j [/mm] überlegt, komme aber nicht auf die Rekurenzrelation:
[mm] $a_1 [/mm] = 1$
[mm] $a_2 [/mm] = 2(n-1)$
[mm] $a_3 [/mm] = [mm] 3(n-1)^2 [/mm] +1$
[mm] $a_4 [/mm] = [mm] 4(n-1)^3 [/mm] +4(n-1)$
[mm] $a_5 [/mm] = [mm] 5(n-1)^4 +10(n-1)^2 [/mm] +1$
[mm] $a_6 [/mm] = [mm] 6(n-1)^5 +20(n-1)^3 [/mm] +6(n-1)$
[mm] $a_7 [/mm] = [mm] 7(n-1)^6 +35(n-1)^4 +21(n-1)^2 [/mm] +1$
Bei diesen Werten bin ich mir ziemlich sicher, wäre nur froh wenn jemand mir mit der Rekurenzrelation helfen könnte.
vielen dank
mfg
Marc
|
|
| |
|
Hallo!
Man muss sich überlegen, wie $j+1$ lange Wörter mit ungerade vielen 1 entstehen: Man nimmt ein $j$ langes Wort mit ungerade vielen 1 und hängt eine nicht-1 dran. Oder man nimmt ein $j$ langes Wort mit gerade vielen 1 und hängt eine 1 dran. Also:
[mm] $a_{j+1}=(n-1)*a_j+n^j-a_j$, [/mm] wobei [mm] $a_1=1$.
[/mm]
Dabei kommt [mm] $n^j-a_j$ [/mm] von der Berechnung des "Gegenereignisses": Es gibt [mm] $n^j$ [/mm] Wörter, davon zieht man die [mm] $a_j$ [/mm] Wörter ab, die ungerade viele 1 haben.
Gruß, banachella
|
|
|
|
