Aufgabe: "Bestimmen sie eine Rekursionsgleichung, die die Anzahl x_n der Wörter der Länge n über dem Alphabet {0,1,2} angibt, die eine gerade Anzahl Nullen enthalten."
Habe schon eine Gleichung gefunden, allerdings scheint sich irgendwo ein Fehler eingeschlichen zu haben, bei dem mir bisher niemand helfen konnte.
Folgende Idee:
Spoiler
Die Anzahl aller Möglichen Wörter erhalten wir ja durch 3^n, dh die Gleichung sähe wie folgt aus: x_n=3(x_n-1) mit x_0=1.
Wir wollen alle möglichen Fälle "durchzählen". Fügen wir eine 1oder2 zum Wort hinzu, dann rufen wir 2(x_n-1) auf, fügen wir eine null hinzu, dann gehen wir davon aus das immer eine zusätzliche null hinzugefügt werden muss, damit die Anzahl gerade bleibt. Diese null kann ja eine beliebige Position unter den restlichen Ziffern annehmen, es gibt davon n-1 Positionen.
Somit rechnen wir im Falle der null (n-1)(x_n-2), denn dem Wort werden ja dann zwei Ziffern gleichzeitig hinzugefügt.
Den Fall 1oder2 und null addieren wir dann und bekommen:
x_n = 2(x_n-1) + (n-1)(x_n-2); mit x_0=1 und x_1=2 (denn wenn wir in x_3 eine null hinzufügen, dürfen wir das bei x_1 nichtmehr, weil die Anzahl sonst ungerade wird. Darf ich x_0 und x_1 so festlegen?).
So, irgendwo liegt hier aber glaube ich ein Fehler. Ich habe das ganze für x_3 und x_4 durchgerechnet. Bei x_3 stimmt alles, aber bei x_4 komme ich auf versch. Ergebnisse durch die Rekursionsgleichung und das manuelle durchgehen aller Fälle!
Wäre super wenn ihr mir helfen könnt!
