Kompositionen von n - Fibos < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:32 Do 17.11.2011 | | Autor: | clemenum |
| Aufgabe | Man drücke durch Fibonacci-Zahlen aus:
Anzahl der Komopositionen von $n$, deren Teile entweder 1 oder 2 sind.
Dabei sind Kompositionen die Zerlegung einer Zahl $n$ in ihre Summanden, wobei die Reihenfolge eine Rolle spielt.
Hinweis: Man stelle die Verbindung zu den Fibonacci-Zahlen mit einer (geeignet gewählten) Bijektion her! |
Man könnte nun versuchen die Zahl $n$ in zwei Familien aufzuteilen:
diejenigen, derer letzter Summand eine 1 ist und dijenigen, wo eben der letzte eine zwei ist.
Dort, wo der letzte eine 1 ist müsste sich nun (intuitiv) eine Bijektion mit Kompositionen von $n-1$ herstellen lassen und letztere mit $n-2$. Jedoch kann ich keine konkrete Abbildung angeben! :-(
Damit folgt schon, dass [mm] $F_n [/mm] = [mm] F_{n-1} [/mm] + [mm] F_{n-2}$ [/mm] ist.
Kann mir jemand die Abbildung angeben, die mir nur intutiv einleuchtet? Sonst laufe ich Gefahr mit Zirkelschlüssen zu arbeiten... (D.h. ich sehe die die folgernde Identität und versuche durch die gegebene Gleichheit eine Bijektion zu basteln, kann jedoch keine solche angeben, womit ja die Gleichheit eigentlich NICHT bewiesen ist...)
|
|
| |
|
Hallo clememum,
> Man drücke durch Fibonacci-Zahlen aus:
> Anzahl der Komopositionen von [mm]n[/mm], deren "Teile" entweder 1 oder 2 sind.
Wir bezeichnen die Anzahl der Kompositionen von [mm] n\in\IN, [/mm] deren Teile entweder 1 oder 2 sind, mit [mm] K_n.
[/mm]
> Dabei sind Kompositionen die Zerlegung einer Zahl [mm]n[/mm] in ihre
> Summanden, wobei die Reihenfolge eine Rolle spielt.
> Hinweis: Man stelle die Verbindung zu den Fibonacci-Zahlen
> mit einer (geeignet gewählten) Bijektion her!
> Man könnte nun versuchen die Zahl [mm]n[/mm] in zwei Familien
> aufzuteilen:
> diejenigen, derer letzter Summand eine 1 ist und dijenigen,
> wo eben der letzte eine zwei ist.
Prima Idee!
Ich verstehe nicht, warum man unbedingt eine Bijektion angeben soll. Es reicht die Gültigkeit der Rekursionsformel und zwei (übereinstimmende) Startwerte nachzuweisen. Letzteres ist leicht getan.
Dann der Induktionsschritt für [mm] n\geq3. [/mm] Hier nimmst du deine beiden Fälle:
a) Kompositionen von n mit 1 am Ende: Das sind [mm] K_{n-1} [/mm] Stück.
b) Kompositionen von n mit 2 am Ende: Das sind [mm] K_{n-2} [/mm] Stück.
Da die Fälle a) und b) disjunkt und vollständig sind folgt
[mm] K_n=K_{n-1}+K_{n-2}.
[/mm]
LG
|
|
|
|
