Rekursionsformel bestimmen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei f (n) die Anzahl der Strings der Länge n, in denen nur die Symbole 0,1,2 vorkommen
und in denen keine zwei Nullen hintereinander stehen.
Geben Sie die Rekursionsgleichung an und lösen Sie sie. |
Meine Überlegung war dass f(1) = 3 sein muss (0,1,2)
jetzt kann man an jede Zeichenkette 1 und 2 anhängen also f(n-1)*2
hinzu kommt noch eine 0 für jede Zeichenkette die keine 0 enthält.
Daraus hab ich folgendes hergeleitet:
n=1 1nuller 2nicht nuller
n=2 2nuller 6nicht nuller
n=3 6nuller 16nicht nuller
n=4 16nuller 44 nicht nuller
n=5 44 nuller 120 nicht nuller
n=6 120nuller 328 nicht nuller
mit nuller sind die Zeichenketten die auf eine 0 enden gemeint.
es läßt sich leicht erkennen dass die anzahl der nuller gleich der anzahl der nicht nuller des Vorgängers ist und das die Anzahl der nicht nuller gleich dem 2 fachen der summe aus nicht nuller und nuller ist.
Kann mir irgendjemand nen Tipp geben wie man daraus ne Rekursiongleichung basteln kann?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Moin zusammen,
ein versuch: sei [mm] f_0(n) [/mm] die Zahl aller solcher Strings, die mit 0 enden, und sei [mm] f_{12}(n)=f(n)-f_0(n) [/mm] die zahl aller solcher, die auf 1 oder 2 enden.
Dann ist
[mm] f_{12}(1)=2, f_0(1)=1 [/mm] und
[mm] f(n)=f_{12}(n)+f_0(n)
[/mm]
mit
[mm] f_0(n)=f_{12}(n-1)
[/mm]
und
[mm] f_{12}(n)=3\cdot [/mm] f(n-1) = [mm] 3\cdot f_{12}(n-1)+ 3\cdot f_0(n-1)=3\cdot f_{12}(n-1)+ 3\cdot f_{12}(n-2)
[/mm]
d.h. wir haben jetzt eine Rekursion für [mm] f_{12}(n) [/mm] und bekommen daraus die für f(n).
Gruss,
Mathias
|
|
|
| |
|
k, der erste Teil deiner Antwort leuchtet mir noch ein wobei wenn
$f(n) = [mm] f_{12}(n)+f_{0}(n)$
[/mm]
mit
[mm] $f_{0}(n) [/mm] = [mm] f_{12}(n-1)$
[/mm]
wäre es doch eleganter zu sagen:
$f(n) = f(n) = [mm] f_{12}(n)+f_{12}(n-1)$
[/mm]
oder gibt das irgendwelche Komplikationen?
Der letzte Teil ist für mich unverständlich da eine Multiplikation mit 3 statt mit 2 gemacht wird ich glaube es müsste so lauten:
$ [mm] f_{12}(n)= [/mm] 2 [mm] \cdot f_{12}(n-1)+ f_{12}(n-2)$
[/mm]
vielleicht kann mir noch jemand einen Tipp geben wie man die Rekursion dann am Besten noch in eine geschlossene Form bringt, sofern sie korrekt ist.
|
|
|
| |
|
Hallo nochmal,
ja, da ist mir ein Fehler unterlaufen:
Es muss
[mm] f_{12}(n)= 2\cdot [/mm] f(n-1) = [mm] 2\cdot (f_{12}(n-1)+f_{12}(n-2))
[/mm]
lauten, ganz recht.
Damit bekommt man dann doch sowas wie
[mm] f_{12}(n)= f_{12}(n-k)\cdot \sum_{i=1}^{k-1}2^i
[/mm]
oder so, nicht wahr ?
Gruss,
Mathias
|
|
|
|
