Bsp33

[Patman]

Also hier einmal ein Ansatz für die Rekusionsgleichung (synonym für Differenzengleichung):

Zeichnet euch am besten einen Baum auf in dem man sieht auf welchen wert welcher folgen kann. Also auf 1 kann 1 und 0 folgen, auf 0 nur 1. So ist gewährleistet, dass es keine zwei benachbarten nullen gibt. Dann ist besser ersichtlich was ich meine.

[]...indizes
x[n]...Anzahl der Einsen für die Tiefe n (des Baumes)
y[n]...Anzahl der Nullen für die Tiefe n (des Baumes)


Anzahl der Einsen:

x[n+1]=y[n]+x[n]

Die Anzahl der Einsen wird einerseits durch die Anzahl der Nullen bestimmt, welche in der vorherigen Stufe vorhanden waren (y[n]). Auf jede 0 muss eine 1 folgen, damit keine zwei nullen nebeneinander stehen.
Andererseits kann auch auf jede 1 eine 1 oder 0 folgen. Da wir uns aber hier nur für die 1en interessieren, steht noch das +x[n] da.


y[n+1]=x[n]

Die Anzahl der 0en wird nur durch die Anzahl der 1en bestimmt, da 0en nur auf 1en folgen können. Und zwar ist die Anzahl der 0en genau die Anzahl an 1en, welche vorher da waren.

Jetzt wird ein bisschen umgeformt:

y[n+1]=x[n] =>
y[n]=x[n-1]


das ganze jetzt in die Rekusionsgleichung für die Einsen eingesetzt:

x[n+1]=x[n-1]+x[n] =>

jetzt kommt die richtige Gleichung für die möglichen kombinationen:

x[n+2]=x[n+1]+x[n]


So, die gleichung steht, der rest ist trivial ;)
Nein, hab jetzt nur keine Zeit mehr dafür, aber ich hoffe ich konnte ein paar leuten weiter helfen!

[Murmel]

Super Ansatz, man sollte vielleicht nur noch dazuschreiben, dass die Anzahl 1en die man setzen kann der Anzahl der möglichen 0/1 Ketten dieser Länge entspricht, weil 1 eh auf alles folgen kann.

Und wie im anderen Thread schon erwähnt handelt es sich um die Fibonacci-Folge, deren Lösung man direkt von S. 30 des Skriptums abschreiben kann, wenn auch vielleicht mit anderer part. Lsg.

lG,
Murmel

[Patman]

Murmel hat natürlich recht, war eigentlich ein Denkfehler....
Das x[n+2] gibt natürlich die Anzahl der Einsen. Zufälligerweise kommt für die Gleichung aber das selbe heraus!! Warum?
Murmel hats eh schon gepostet:
nehmen wir für alle Möglichkeiten mal m[n] an.

Da ja 1 auf alles folgen kann, gilt folgendes:

m[n]=x[n+1]

Soll heißen, dass die Anzahl der Möglichkeiten gleich der Anzahl der Einsen eine Stufe tiefer ist (weil ja 1 auf alles folgen kann)

Wenn man jetzt m in x einsetzt, erhält man:

m[n+1]=m[n]+m[n-1]

was ganau der gleichen Rekursionsgleichung entspricht, wenn man die Indizes um 1 erhöht....

so bitteschön, jetzt sollte es stimmen und sogar noch mit begründbarer herleitung!;)

Hoffe ich habe weniger Verwirrung gestiftet als gesetzt!!


P.S.: ja, ich weiß, dass es rekuRsion heißt;)

[ein_stein2000]

ich finde die Lösung von Studigel etwas intuitiver, aber ich hab mal deine Lösung auch in meine ausarbeitung reingenommen ... auf diese überlegung wär ich jedenfalls nie gekommen, vielen dank für diesen lösungsweg!

ausarbeitung hier: [nix ausarbeitung]
EDIT: man kann net einfach die lösung aus skript nehmen für allgemeine lösung, ich arbeite grad dran ...
(http://einstein2000.oldsch00l.com/uni/mathe2_ubung/Mathe2_Beispiel33.pdf)

[Murmel]

ausarbeitung hier:
http://einstein2000.oldsch00l.com/uni/mathe2_ubung/Mathe2_Beispiel33.pdf
Hmmm also ich weiss nicht ob man 1:1 die Formel aus dem Skriptum für die Fibonnaci-Reihe nehmen darf. x0 und x1 sind in unserem Fall ja andere (und für die gilt die Formel in dem Fall auch gar nicht).

lG,
Murmel

[ein_stein2000]

so jetzt stimmt meine lösung komplett:
http://einstein2000.oldsch00l.com/uni/mathe2_ubung/Mathe2_Beispiel33.pdf (hoff i mal)

EDIT: ich depp hab zwar ah pdf draus gmacht oba net hochgeladen am server ... JETZT [23:19] sollte das aktuelle file am server sein

[Murmel]

so jetzt stimmt meine lösung komplett:
http://einstein2000.oldsch00l.com/uni/mathe2_ubung/Mathe2_Beispiel33.pdf (hoff i mal)

Sollte in der letzten Zeile nicht ein + statt einem - stehen? sonst kommt für x0 nicht 1 raus.

Ich war mir nur nicht sicher ob mans so mit x0 und x1 machen kann, weil die Fibonacci-Reihe ja eigentlich erst ab x2 so funktioniert wie sie soll oder?

lG,
Murmel

[Patman]

einfach: NEIN! ;)

soda, das minus in der letzten zeile steht deswegen da, weil ich zu faul war alle indizes nocheinmal um 1 zu erhoehehn. Dann steht auch wieder ein n+2 da...
mein zyweiter post war auch nur nocheinmal zur verdeutlihchung...
ausserdem sehe ich kein Problem darin die Fibonaccireihe zu verwenden. mit x[0]=1 und x[1]=2
kann man sich leicht ueberlegen: bei laenge 0 gibts eine Moeglichkeit (quasi die leere menge) und bei laenge 1 gibts 2

[ein_stein2000]

Sollte in der letzten Zeile nicht ein + statt einem - stehen? sonst kommt für x0 nicht 1 raus.
du hast recht, hab mich wohl vertippt ... habs ausgebessert

[minority]

ich find das ganze a bissl komisch.
wenn ma sich nur die seite vom baum anschaut wo die folge mit 0 beginnt hat ma die fibonacci folge (0),1,1,2,3,5,...
wenn ma sich die seite anschaut wo nur 1 am anfang is hat ma dann auch a fibonacci folge mit (0),1,2,3,5,8...
und wenn man jetzt die folgen in der jeweiligen ebene zamzählt hat ma wieder a fibonacci folge.
is das die überlegung die dahinter steht oder hab ich da was falsch verstanden?
mfg markus