\(\begingroup\)\(\newcommand{\IX}{\mathbb{X}}
\newcommand{\IW}{\mathbb{M}}
\newcommand{\politician}[1]{\text{Ich habe die Frage nicht verstanden. #1}}
\newcommand{\ba}{\begin{aligned}}
\newcommand{\ea}{\end{aligned}}
\newcommand{\bpm}{\begin{pmatrix}}
\newcommand{\epm}{\end{pmatrix}}
\newcommand{\bc}{\begin{cases}}
\newcommand{\ec}{\end{cases}}
\newcommand{\on}{\operatorname}
\newcommand{\ds}{\displaystyle}\) Dies ist der dritte Beitrag des Sommerausflugs in die Kombinatorik. Die früheren Teile waren:
Definition (Erzeugende Funktion) Als erzeugende Funktion einer reellen Zahlenfolge an bezeichnet man die formale Potenzreihe sum(a_n\.x^n,n=0,\inf) bzw. die durch diese Reihe in ihrem Konvergenzintervall dargestellte Funktion (falls Konvergenzradius > 0).
Zunächst: eine formale Potenzreihe ist eine Schreibweise, die man ohne Rücksicht auf mögliche Konvergenz verwendet. Beim Umgang mit Potenzreihen ist es zweckmäßig, die algebraischen Rechenregeln von Konvergenzfragen zu trennen.
Sind \ P := sum(a_n x^n,n=0,\inf) und \ Q := sum(b_n x^n,n=0,\inf) zwei formale Potenzreihen, dann gelten die folgenden Regeln:
[14] P+Q := sum((a_n+b_n) x^n,n=0,\inf)
[15] P*Q := sum((c_n) x^n,n=0,\inf), mit c_n = sum(a_i*b_j,i+j=n)
Die derart definierte Addition und Multiplikation stimmt im Falle konvergenter Potenzreihen mit den dort beweisbaren Rechenregeln überein.
Eine formale Potenzreihe ist eine Potenzreihe, bei der keinerlei Konvergenzvoraussetzungen gemacht werden.
Die formalen Potenzreihen sind nicht mehr als eine Wäscheleine, an der die Folgenglieder aufgehängt, befestigt werden.
In der formalen Potenzreihe der Folge z(n) ist der Koeffizient der n-ten Potenz der Unbestimmten x das Folgenglied z(n), d.h. der Platz von z(n) ist bei xn. In formalen Potenzreihen wird niemals ein x eingesetzt.
Die Brücke
Um eine Brücke zum Verständnis der erzeugenden Funktionen zu bauen, betrachte ich für ein festes m die Folge
g(n,m) := Anzahl der Summenzerlegungen von n in Summanden gleich m.
Für m=1 ist g(n,1) = 1 für alle n, denn wenn nur der Summand 1 erlaubt ist, dann gibt es nur eine Möglichkeit die Zahl n als Summe von Einsen darzustellen. Die Potenzreihe P := sum(g(n,1)x^n,n=0,\inf) = sum(x^n,n=0,\inf) ist für abs(x)<1 konvergent und stellt die Funktion 1/(1-x) dar.
\stress~>\ Die erzeugende Funktion von g(n,1) lautet 1/(1-x).
[Hinweis: sum(x^n,n=0,\inf) ist eine geometrische Reihe, deren Konvergenzverhalten und Grenzwert 1/(1-x) bekannt ist.]
Für m=2 ist g(n,2) = 0 für ungerade n und g(n,2) = 1 für gerade n, denn es gibt keine Möglichkeit eine ungerade Zahl als Summe von Zweien darzustellen, und es gibt genau eine Möglichkeit eine gerade Zahl als Summe von Zweien zu schreiben. Die Potenzreihe P := sum(g(n,2) x^n,n=0,\inf) = sum(x^2n,n=0,\inf) = sum((x^2)^n,n=0,\inf) ist für abs(x) < 1 konvergent und stellt die Funktion 1/(1-x^2) dar.
\stress~>\ Die erzeugende Funktion von g(n,2) lautet 1/(1-x^2).
Es ist schon zu sehen, wie die erzeugende Funktion von g(n,3) lautet, nämlich 1/(1-x^3)
Über die Brücke gehen
Wir betrachten nun für festes m die Folge
h(n,m) := Anzahl der Summenzerlegungen von n in Summanden kleiner gleich m.
Beweis [16]: Das Produkt sum(g(n,1) x^n,n=0,\inf) * sum(g(n,2) x^n,n=0,\inf) ist eine formale Potenzreihe sum(c(n) x^n,n=0,\inf). Was ist der Koeffizient von x^n in diesem Produkt? c(n) ist gleich der Anzahl der Möglichkeiten das x^n als Produkt von verschiedenen x\-Potenzen zu erhalten. Genau die Produkte g(i,1)x^i*g(j,2)x^j mit i+j=n ergeben die Potenz x^n. Der Koeffizient von x^n ist gleich der Summe der g(i,1)*g(j,2) mit i+j=n. Folglich ist c(n) = sum(g(i,1)*g(j,2),i+j=n). Die c(n) sind wohldefiniert, denn die rechte Summe hat nur endlich viele Summanden. QED [16]
In der Anschauung der Kombinatorik bedeutet diese Formel: Man erhält alle Summenzerlegungen von n in Summenden aus {1,2}, indem man zu einer vorgegebenen Anzahl Einsen (nämlich i Einsen) die erforderliche Anzahl Zweien auffüllt. Es gibt g(i,1)*g(n-i,2) Summenzerlegungen, mit genau i Einsen. Man beachte, daß g(n-i,2) gleich 0 ist, wenn n-i eine ungerade Zahl ist.
Der Bauplan ist klar
Nach diesem Bauplan ist es nun leicht, die erzeugende Funktion für die Folge
d(n) := Anzahl der Summenzerlegungen in Summanden {2,3}
anzugeben. Sie lautet:
[17] 1/(1-x^2)*1/(1-x^3)
Auch die beim letzten Mal gestellte Frage:
Wieviele Möglichkeiten gibt es, 1 Euro in Münzen zu zahlen?
kann ich nun beantworten.
Die verfügbaren Münzwerte sind (in Cent): 1, 2, 5, 10, 20, 50, 100.
Sei e(n) die Anzahl der Möglichkeiten n Cent in Münzen zu zahlen.
Gut und schön, was ist nun e(100)? Ist man nicht genauso schlau wie zuvor? Ich sage: "Schlauer!", denn
Mit erzeugenden Funktionen können viele Probleme sehr schnell auf die Berechnung der Koeffizienten von Potenzreihen zurückgeführt werden. (Siehe das Problem des Geldwechsels)
Ein einfaches Berechnungsverfahren für die Koeffizienten ist leicht anzugeben und zu programmieren.
Der Koeffizient von x100 in der erzeugenden Funktion von e(n) gibt die Antwort auf die Frage:
Die Summe von 100 Cent kann auf 4563 verschiedene Weisen in Münzen bezahlt werden!
Die Berechnung habe ich mit einem Programm durchgeführt, das Du hier selbst ausprobieren kannst: Programm Münzzerlegungen. Die Folgenglieder werden über die erzeugende Funktion [18] berechnet. Dabei müssen mehrere Polynome bis zu einem maximalen Grad, der durch den zu zerlegenden Betrag bestimmt ist, multipliziert werden.
Zurück zu Summenzerlegungen
Sei z(n) die Anzahl der Summenzerlegungen der natürlichen Zahl n.
Die erzeugende Funktion der z(n) lautet:
[13] produkt(1/(1-x^i),i=0,\inf)
Das sollte nun plausibel sein. Für jede gegebene Zahl n kann das unendliche Produkt auf das Produkt der Faktoren 1/(1-xi) mit i <= n beschränkt werden.
Mit dem Programm für Münzerlegungen kann man die Anzahl der Summenzerlegungen einer natürlichen Zahl n berechnen: setze bei den Münzwerten alle Zahlen kleiner oder gleich n ein, dann sind die vom Programm gelieferten Anzahlen bis einschließlich n genau die Anzahl der Summenzerlegungen für die jeweilige Zahl.
Einige andere, in meinen Augen effektivere Berechnungsmethoden waren schon in Summenzerlegungen 2 genannt worden (z.B. [12]).
Ausblick und Schluß
Mit etwas Geschick holt man aus der erzeugenden Funktion auch noch explizte Formeln für die Koeffizienten heraus. Für die Summenzerlegungen ist aber keine explizite Formel bekannt.
Zur Vorbereitung des nächsten Beitrags in dieser Reihe stelle ich folgende
Frage
Wie lautet die erzeugende Funktion der Fibonacci-Folge?
Die Fibonacci-Folge: f(0)=f(1)=1 f(n) = f(n-1) + f(n-2) für n > 1
Dies ist der dritte Beitrag des Sommerausflugs in die Kombinatorik.
Die früheren Teile waren:
1. Teil: Begriffe, Defintionen,
2. Teil: Rekursive Ansätze
Heutiges Ziel: Ansatz mittels Erzeugender Funktion und Anwendung in einem selbstgeschriebenen Programm.
\(\begingroup\)halli hallo, ich bin gerade dabei, meine facharbeit in mathe über die figurierten zahlen zu schreiben, ich bin schon fast fertig, ich muss nur noch den pentagonalzahlensatz von euler verstehen und ihn mit einbeziehen. ich verstehe ihn nur leider nicht... es wäre furchtbar nett, wenn ihr mir wenigstens in einem problem helfen könntet: was bedeutet dieses zeichen, das so aussieht wie ein pi, aber darüber steht, dass es von n=1 bis unendlich geht, ist das ein zeichen für das produkt??? falls ihr antworten wollt, dann bitte auf elostesso@gmx.de
ciao anna\(\endgroup\)
das ist das Produkt-Zeichen.
Kennst Du das Summenzeichen S?
Dann weißt Du, daß es eine Abkürzung für die Summation von Zahlen ist und die Summation hat einen Index, den man unter und über das Summenzeichen schreibt.
Beim Produkt-Zeichen ist es so ähnlich, nur daß man die Terme nicht addiert, sondern multipliziert.
\(\begingroup\)"Siehe das Problem des Geldwechsels" lese ich im Artikel. Ich habe die Matroidseite leider vergeblich nach näheren Informationen über dieses Thema durchsucht. Weiß da jemand näheres drüber?\(\endgroup\)
\(\begingroup\) Die erzeugende Funktion für ein Geldwechselproblem ist kurz vorher genannt worden. Eine programmierte Lösung unter Verwendung dieser erzeugenden Funktion folgt im nächsten Absatz.
\(\begingroup\)Entschuldigung, ich war etwas verwirrt. Ich hatte den Begriff "Geldwechselproblem" in einem anderen Zusammenhang gesehen und ihn nicht auf das angesprochene Beispiel mit den 100 Cent bezogen.\(\endgroup\)
\(\begingroup\)Mir scheint etwas unklar zu sein. Wenn ich selbst den Fall der 100 Cent per Taschenrechner nachrechne, so erhalte unglaublich kleine Zahlen:
Wenn ich in
1/(1-x)*1/(1-x²)*1/(1-x5)*1/(1-x10)*1/(1-x20)*1/(1-x50)*1/(1-x100)
x=100 (weil 100 Cent) einsetze, kommt ein ganz kleiner Wert raus. Vermutlich habe ich einen elementaren Denkfehler, oder?
Wäre es unter Umständen vielleicht möglich ein Einsetzbeispiel für die Formel zu geben? Ich habe mir auch schon das php-Skript angeschaut, in der Hoffnung dort meinen eventuell vorhandenen Denkfehler zu finden, aber da blicke ich leider nicht so ganz durch. Es wäre nett, wenn ihr mir weiterhelfen könntet, da ich die Formel 13 dringend für eine Facharbeit brauche.
Vielen Dank schon einmal im Vorraus für eure Mühe.\(\endgroup\)
\(\begingroup\)keine ahnung ob das hier noch jemand findet, so wie es aussieht ist der Beitrag über ein Jahr alt...
Mir ist die Sache mit der erzeugenden Funktion einfach nicht klar.
Soll heißen ich verstehe sie einfach nicht.
Es geht mir ja noch ein, dass ich z.B mit f=(1+x)^n die EF zu der Potenzreihe Summe(k=0,n)(n über k)x^k erhalte. Ich muss ja nur in der EF für das n den Wert eintragen, den ich auch in meiner Summe habe.
Aber z.B. die EF von Summe (n=0 bis unendlich) x^n ist ja 1/(1-x) ich sehe/verstehe/schnalle es einfach nicht, wie ich jetzt davon wieder auf das ergebnis x,x^2,x^3,.... kommen soll.
was hat diese Funktion, in der es (mal abgesehen von dem sterilen x, das ja eigentlich eh uninteresant ist), noch mit einer sich entwickelnden reihe zu tun?
\(\begingroup\)Wenn ich das richtig verstehe, vermute ich, dass entweder der Beweis von [16] oder [16] selbst einen Fehler enthält: Das zu Beginn des Beweises angegebene Produkt enthält Summen mit Faktoren g(n,1) und g(n,2). Diese finden sich aber gar nicht in [16], sondern dort stehen g(i,1) und g(i,2).
Könnte aber auch sein, dass ich ein Verständnisproblem beim Beweis habe.\(\endgroup\)
\(\begingroup\)(1+x+x^2+x^3+...+x^100) 1,2,3,4,bis 100
$*(1+x^2+x^4+...+x^100) 2,4,6,8 bis 100
$*(1+x^5+x^10+...+x^100) 5,10,15,20 bis 100
$*(1+x^10+x^20+...+x^100)
$*(1+x^20+x^40+...+x^100)
$*(1+x^50*x^100)*(1+x^100)
woher kommen diese Zahlen und was ist x?
Vielen Dank im Vorraus für's erklären!!!\(\endgroup\)
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
Mathematik: Summenzerlegungen 3
Printer-friendly version
Get link to this article
Comments
Für diesen Artikel gibt es keine pdf-Datei
Dieser Artikel ist im Verzeichnis der 
