Rekursionen aufstellen?

Hey, also ich komme bei solchen Aufgaben nicht weiter. Kann mir jemand erklären wie man hier vorgeht? Würde mich sehr freuen.

Gruß

Answer 1

[ralphdieter]

Für die Rekursion brauchst Du nur eine Vorschrift, wie die Anzahl für n aus der Anzahl für k<n berechnet werden kann. Das ist meist viel einfacher, als eine geschlossene Formel zu finden.

In (i) kannst du ein Wort der Länge n≥2 auf zwei Arten bilden:

1. Wort der Länge n−1 plus b∈B
2. Wort der Länge n−2 plus z∈Z plus b∈B

Mach dir klar, dass dabei alle Wörter gezählt werden und dabei keines doppelt vorkommt. Die rekursive Formel lautet also

• f₀ = 1
• f₁ = |B|
• fₙ₊₂ = fₙ₊₁·|B| + fₙ·|Z|·|B|

Bei (ii) geht es ähnlich, nur eben mit zwei Parametern: ein Wort der Länge n>0 mit k Ziffern entsteht durch

1. ein Wort der Länge n−1 mit k Ziffern plus b∈B
2. ein Wort der Länge n−1 mit k−1 Ziffern plus z∈Z

(1) klappt nur bei n>k, und (2) nur bei k>0. Deshalb müssen die Fälle fₙ,ₙ und fₙ,₀ extra behandelt werden (der ungültige Summand fällt da weg):

• f₀,₀ = 1
• fₙ₊₁,₀ = fₙ,₀·|B|
• fₙ₊₁,ₙ₊₁ = fₙ,ₙ·|Z|
• fₙ₊₁,ₖ₊₁ = fₙ,ₖ₊₁·|B| + fₙ,ₖ·|Z|

Zu (iii): Ich weiß nicht, was ein „Matching“ ist. Aber vermutlich geht es auch hier darum, diese Dinger aus Matchings in Pₙ₋₁ zu konstruieren.