Rekursion finden
-
a[n] ... Anzahl der Wörter Länge n
Alphabet = {a,b,c}
Bedingung: Anzahl der a gerade (0 ist gerade)Wie kann ich da eine Rekursion aufstellen?
Die ersten Werte sind:
n=0 : 0
n=1 : 2 (b und c, da 0 ja gerade ist) - 1 Fall fällt weg
n=2 : 5 - 4 Fälle fallen weg
n=3 : 14 - 13 Fälle fallen wegAber ich komme weder auf die Lösug der Rekursion noch in einem nächstne Schritt auf die Rekursion selbst.
MfG SideWinder
-
die folge ist wie folgt:
A_0 = 1 (das leere wort ist auch ein wort)
A_n+1 = 2*A_n + 3^n - A_n = 3^n + A_ndas kommt daher, dass sich die parität der a's nicht ändert, wenn man ein b oder c dran hängt, daher die 2*A_n. die parität ändert sich aber, wenn man ein a dranhängt. Es gibt insgeammt 3^n wörter mit länge n und A_n mit gerader anzahl an a's, also 3^n - A_n mit ungerader anzahl.
mfg
MamboKurt
-
Danke!
MfG SideWinder
-
So heute hatte ich Zeit das Beispiel nochmal näher anzusehen. Du schreibst:
"3^n - A_n mit ungerader anzahl."
sollte das nicht gerade umgekehrt sein? Sollten wir nicht diejenigen mit gerader Anzahl hinzuaddieren?
MfG SideWinder
-
Habs schon. Danke nochmal!
MfG SideWinder