Die Mathe-Redaktion - 16.01.2018 20:33 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktZur Award-Abstimmung
ListenpunktFormeleditor fedgeo
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 731 Gäste und 30 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Stern Mathematik: Summenzerlegungen 3
Freigegeben von matroid am Sa. 20. Juli 2002 00:41:41
Verfasst von matroid -   10400 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
Mathematik

\(\begingroup\)

Dies ist der dritte Beitrag des Sommerausflugs in die Kombinatorik. Die früheren Teile waren:

1. Teil: Begriffe, Defintionen,
          Unterscheidungen

2. Teil: Rekursive Ansätze

Heutiges Ziel

Sei z(n) die Anzahl der Summenzerlegungen der natürlichen Zahl n
(siehe Teil 1).

Die erzeugende Funktion der z(n) lautet:

fed-Code einblenden

Was ist eine erzeugende Funktion?



Definition (Erzeugende Funktion)
Als erzeugende Funktion einer reellen Zahlenfolge an bezeichnet man die formale Potenzreihe
fed-Code einblenden
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
fed-Code einblenden
fed-Code einblenden
zwei formale Potenzreihen, dann gelten die folgenden Regeln:
fed-Code einblenden

fed-Code einblenden
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.
fed-Code einblenden

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.
fed-Code einblenden
fed-Code einblenden

Ü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.
Behauptung: Es ist

fed-Code einblenden
Plausibilisierung von [16]:

Berechne das Produkt (1 + x + x² + x³ + x4 + x5 + x6 + x7 + x8 + x9 + x10)*(1 + x² + x4 + x6 + x8 + x10).

Ergebnis: 1 + x + 2x² + 2x³ + 3x4 + 3x5 + 4x6 + 4x7 + 5x8 + 5x9 + 6x10 + (höhere Potenzen)

Man liest ab, daß h(7,2) = 4 ist.

Tatsächlich gibt es 4 Summenzerlegungen mit Summanden 1 oder 2:
7 = 2 + 2 + 2 + 1
7 = 2 + 2 + 1 + 1 + 1
7 = 2 + 1 + 1 + 1 + 1 + 1
7 = 1 + 1 + 1 + 1 + 1 + 1 + 1
Beweis [16]:
fed-Code einblenden
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:

fed-Code einblenden

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.

Die erzeugende Funktion von e(n) ist

[18] 1/(1-x)*1/(1-x²)*1/(1-x5)*1/(1-x10)*1/(1-x20)*1/(1-x50)*1/(1-x100)

Gut und schön, was ist nun e(100)? Ist man nicht genauso schlau wie zuvor? Ich sage: "Schlauer!", denn
  1. 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)
  2. 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:
fed-Code einblenden
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


Zur Fortsetzung über Kartenhäuser und Eulers Pentagonalzahlensatz




Matroid 2002

 
Dieser Artikel ist enthalten in unserem Buch
Mathematisch für fortgeschrittene Anfänger
Mathematisch für fortgeschrittene Anfänger

\(\endgroup\)

Link auf diesen Artikel Link auf diesen Artikel  Druckbare Version Druckerfreundliche Version  Einen Freund auf diesen Artikel aufmerksam machen Weitersagen Kommentare zeigen Kommentare  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Kombinatorik :: Mathematik :: Erzeugende Funktion :: Summenzerlegungen :: Sonstige Mathematik :
Summenzerlegungen 3 [von matroid]  
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.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
Verwandte Links
 
Besucherzähler 10400
 
Aufrufstatistik des Artikels
Insgesamt 331 externe Besuche zwischen 2018.01 und 2018.01 [Anzeigen]
DomainAnzahlProz
http://matheplanet.com226.6%6.6 %
http://google.de18555.9%55.9 %
http://forum.mods.de4814.5%14.5 %
http://www.mathelounge.de154.5%4.5 %
http://www.gute-mathe-fragen.de164.8%4.8 %
http://www.c-plusplus.de154.5%4.5 %
http://www.c-plusplus.net92.7%2.7 %
http://r.duckduckgo.com20.6%0.6 %
http://vodafone.de.searchturbo.com10.3%0.3 %
http://search.incredibar.com10.3%0.3 %
http://www.bing.com30.9%0.9 %
http://yandex.ru51.5%1.5 %
http://search.babylon.com10.3%0.3 %
http://newsgroups.derkeiler.com20.6%0.6 %
http://www.startxxl.com10.3%0.3 %
http://google.at10.3%0.3 %
http://search.snapdo.com10.3%0.3 %
http://duckduckgo.com10.3%0.3 %
http://www.ecosia.org10.3%0.3 %
http://de.yhs4.search.yahoo.com10.3%0.3 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 7 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2018.01.15 20:07fav.php?agid=1&keyword=Summenzerlegungen
2018.01.06-2018.01.14 (5x)viewtopic.php?topic=33880&ref=https://www.google.de/&ff=y
2018.01.12 12:16viewtopic.php?topic=181361&ref=https://www.google.de/&ff=y

Häufige Aufrufer in früheren Monaten
Insgesamt 266 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2012-2017 (95x)http://google.de/url?sa=t&rct=j&q=
2012-2017 (46x)http://forum.mods.de/bb/thread.php?TID=99392&page=2
2015-2016 (15x)http://www.mathelounge.de/57638/wie-viele-moglichkeiten-gibt-es-50-euro-in-sc...
2013-2015 (15x)http://www.gute-mathe-fragen.de/57638/wie-viele-moglichkeiten-gibt-es-50-euro...
2014.01 (10x)http://google.de/url?sa=t&rct=j&q=summenzerlegung fibonacci
2013.05 (9x)http://google.de/url?sa=t&rct=j&q=wieviele möglichkeiten gibt es 55 cent dar...
2012.09 (9x)http://google.de/url?sa=t&rct=j&q=wieviele möglichkeiten gibt es 20 cent dar...
2013-2014 (9x)http://www.c-plusplus.de/forum/104093-full
201411-12 (8x)http://www.c-plusplus.net/forum/104093-full
2013.06 (7x)http://google.de/url?sa=t&rct=j&q=geldwechselproblem erzeugende funktion
2012.02 (6x)http://google.de/url?sa=t&rct=j&q=wieviele möglichkeiten gibt es 1 euro darz...
2012-2014 (6x)http://www.c-plusplus.de/forum/104093-10
2012.05 (6x)http://google.de/url?sa=t&rct=j&q=exponential erzeugende funktion beispiel ma...
2014.06 (6x)http://google.de/url?sa=t&rct=j&q=mathematik "wieviele möglichkeiten gibt es...
2012.06 (6x)http://google.de/url?sa=t&rct=j&q=konvergenzradius (nx)^n
2012.08 (5x)http://google.de/url?sa=t&rct=j&q=wie viele wege gibt es eine 1 euro münze m...
2012.07 (4x)http://google.de/url?sa=t&rct=j&q=wie viele möglichkeiten 1 euro durch cent ...
2013.08 (4x)http://google.de/url?sa=t&rct=j&q=formale potenzreihen erzeugende funktion

[Seitenanfang]

" Stern Mathematik: Summenzerlegungen 3" | 12 Kommentare
 
Für den Inhalt der Kommentare sind die Verfasser verantwortlich.

Re: Summenzerlegungen 3
von Ex_Mitglied_40174 am So. 23. März 2003 16:26:49

\(\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\)

 [Bearbeiten]

Re: Summenzerlegungen 3
von matroid am Mo. 24. März 2003 00:36:01

\(\begingroup\)
Hi Anna,



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.



Ein einfaches Beispiel:

<img src="http://fed.matheplanet.com/mprender.php?string=%5Cprodukt%28i%2Ci%3D1%2Cn%29+%3D+1%2A2%2A3%2A...%2A%28n-1%29%2An+%3D+n%21" border=0 alt="" onmouseover='javascript:fedimageinfo(this)' onclick='javascript:fedshowimage2(this)'>



Gruß

Matroid



\(\endgroup\)

 [Bearbeiten]

Re: Summenzerlegungen 3
von Ex_Mitglied_40174 am Mi. 16. April 2003 18:18:22

\(\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\)

 [Bearbeiten]

Re: Summenzerlegungen 3
von matroid am Mi. 16. April 2003 18:33:49

\(\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.

Gruß
Matroid\(\endgroup\)

 [Bearbeiten]

Re: Summenzerlegungen 3
von Ex_Mitglied_40174 am Mi. 16. April 2003 19:12:55

\(\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\)

 [Bearbeiten]

Re: Summenzerlegungen 3
von Ex_Mitglied_40174 am Mi. 16. April 2003 20:33:25

\(\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\)

 [Bearbeiten]

Re: Summenzerlegungen 3
von matroid am Mi. 16. April 2003 20:50:58

\(\begingroup\)
Um die Koeffizienten für x-Potenzen bis 'hoch 100' zu bestimmen, muß man multiplizieren:





fed-Code einblenden



Im Ergebnis gibt der Koeffizient von xk die Anzahl der Summenzerlegungen von k Cent an.



Gruß

Matroid\(\endgroup\)

 [Bearbeiten]

EF
von Ex_Mitglied_40174 am Mo. 28. April 2003 10:42:16

\(\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?

ja, ka ob das jemand findet der mir helfen kann

danke
sebi\(\endgroup\)

 [Bearbeiten]

Re: Summenzerlegungen 3
von Ex_Mitglied_40174 am Mo. 07. April 2008 18:00:03

\(\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\)

 [Bearbeiten]

Re: Summenzerlegungen 3
von matroid am Di. 08. April 2008 15:46:55

\(\begingroup\)
Richtig, in [16] muß es g(n,1) und g(n,2) heißen. Ich habe es oben korrigiert.

Gruß
Matroid\(\endgroup\)

 [Bearbeiten]

Re: Summenzerlegungen 3
von Ex_Mitglied_40174 am Do. 01. Mai 2008 19:30:59

\(\begingroup\)
Was muss ich denn jetzt konkret machen, um auf 4563 zu kommen? Auch euer Programmquellcode hilft mir nicht weiter.\(\endgroup\)

 [Bearbeiten]

Re: Summenzerlegungen 3
von Ex_Mitglied_40174 am Do. 01. Mai 2008 20:55:32

\(\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\)

 [Bearbeiten]

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]