Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Kompositionen durch Fibonacci-Zahlen ausdrücken

Kompositionen durch Fibonacci-Zahlen ausdrücken

Universität / Fachhochschule

Erzeugende Funktionen

Rekursives Zählen

Tags: Erzeugende Funktionen, Rekursives Zählen

Clemensum aktiv_icon

22:19 Uhr, 16.11.2011

Drücke die folgenden Zahlen durch Fibonaccizahlen aus:
(a) Anzahl aller Kompositionen von n, deren Teile entweder gleich 1 oder 2 sind,
(b) Anzahl aller Kompositionen von n, deren Teile alle gr¨oßer oder gleich 2 sind,
(c) Anzahl aller Kompositionen von n in ungerade Teile.
Eine Komposition ist einfach die Zerlegung der Zahl n in ihre Summanden, wobei es auf die Reihenfolge ankommt. Bsp. für n = 3: 2+1, 1+2, 1+1+1, 3

Ich bin leider hier sehr überfragt. Ich würde mich über einen (guten) Tipp freuen:

Meine konkrete Frage: Welche Methode emphehlt ihr mir hier? Könnte es mit der Fibonacci-Formel klappen, die explizit ist?

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

hagman aktiv_icon

22:41 Uhr, 16.11.2011

(a)

Die Kompositionen von

n

kann man in zwei Klassen aufteilen: diejenigen, deren letzter Summand eine 1 ist und diejenigen, deren letzter Summand eine 2 ist.
Erstere stehen in Bijektion mit Kompositionen von

n - 1,

letztere mit Kompositionen von

n - 2

.
Somilt gilt die Rekursionsformel

f (n) = f (n - 1) + f (n - 2)

wie bei den Fibos. Man muss nur noch zu Fuß

f (1)

und

f (2)

ausrechnen und vergleichen.

(b)

Diesmal erhält man aus einer zulässigen Komposition

n = a_{1} + ... + a_{k}

entweder eine Komposition

n - 2 = a_{1} + ... + a_{k - 1}

(nämlich wenn

a_{k} = 2)

oder eine Komposition

n - 1 = a_{1} + ... + (a_{k} - 1)

(nämlich, wenn

a_{k} \geq 3)

. Wiederum folgt

f (n) = f (n - 1) + f (n - 2)

. Berechne

f (1)

und

f (2)

zu Fuß.

(c)