Rekursionsproblem < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:54 Sa 09.06.2012 | | Autor: | sissenge |
Ich soll nächste Woche ein Referat über das Rekursionsproblem "Changing money" halten, also :"wieviele Möglichkeiten gibt es zB. einen Dollar zu wechseln?"
jetzt habe ich damit angefangen mit Partition angefangen, also In wieviele positive Summanden lässt sich eine positive Zahl zerlegen.
Über verschiedene schritte bin ich dann zu der Formel gekommen :
[mm] \summe_{n=0}^{\infty}h(n,2)x^{n}=\summe_{n=0}^{\infty}g(n,1)x^{n} \summe_{n=0}^{\infty}g(n,2)x^{n}
[/mm]
wobei h(n,m):= Anzahl der Summenzerlegung von n in Summanden kleiner gleich m
und g(n,m):=Anzahl der Summenzerlegung von n in Summanden gleich m
Bis dahin verstehe ich alles einwandfrei, was ich jetzt nicht verstehe ist, wie ich zb. diese Formel darauf anwende: Wieviele Möglichkeiten gibt es die Zahl 7 mit summen aus 1 und 2 auszudrücken??
Dann würde ja folgendes dastehen:
[mm] \summe_{n=0}^{7}h(n,2)x^{n}=(1+x^{1}+x^{2}+x^{3}+x^{4}+x^{5}+x^{6}+x^{7})(1+x^{2}+x^{4}+x^{6})
[/mm]
aber jetzt weiß ich ehrlich gesagt nicht was mir das bringt... woher weiß ich jetzt wieviele Möglichkeiten es gibt????
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:31 So 10.06.2012 | | Autor: | leduart |
Hallo
ich versteh deine Formeln nicht.
was ist das x darin? Was sind deine "verschiedenen schritte da hin? und wie kannst du bis [mm] \infty [/mm] summieren.
bei 7 in 1 und 2 zerlegen
fang mit 7*1 an ,dann 1*2+5*1; 2*2+3*1 3*2+1 also 4 verschiedene Zerlegungen
etwa dein g(n,m):=Anzahl der Summenzerlegung von n in Summanden gleich m : da gibt es doch nur eine a)n teilbar durch m eine Zerlegung, 6 etwa kann man nur in 2+2+2 zerlegen b) nicht tb durch m dann auch nur eine mit einem Rest. 7=2+2+2+1
also erklär bitte deine Formel.
Gruss leduart
Gruss leduart
|
|
|
|
