Die Mathe-Redaktion - 23.07.2017 14:51 - Registrieren/Login
Auswahl
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 Apr. 2017

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

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Mathematik: Summenzerlegungen 2
Freigegeben von matroid am Fr. 12. Juli 2002 18:13:32
Verfasst von matroid -   8628 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
Mathematik

Ein Ausflug in die Kombinatorik, Teil 2

Im ersten Beitrag war definiert worden, was eine Summenzerlegung einer natürlichen Zahl n ist und u.a. gefragt worden:
Wieviele verschiedene Summenzerlegungen gibt es für eine natürliche Zahl n?
Heute will ich mit der Erforschung des Problems beginnen.



Das Angenehme bei den kombinatorischen Problemen ist, daß man zum Warmwerden den naheliegenden Anfang mit kleinen Zahlen für n oder k oder beide hat. Nach einigem Nachdenken hat man eine kleine Wertetabelle und bereits etwas von der Struktur des Problems begriffen.
Anschließend ist man schon etwas im Zweifel, ob die gesuchte Anzahl mit den gängigen Anzahlformeln berechnet werden kann. Tatsächlich ist für die Summenzerlegungen bzw. numerischen Partitionen keine geschlossene Formel bekannt.

Hier ist eine Wertetabelle bis n = 4096.

Damit eine so umfangreiche Tabelle gefüllt werden kann, muß es eine genügend einfache Berechnungsmethode geben.
Um Berechnungsmethoden soll es heute gehen.

Wir stürzen uns daher in verschiedene

Rekursive Ansätze

Üblicher Ansatz bei der Suche nach rekursiven Beziehungen:
Finde geeignete disjunkte Aufteilungen der zu zählenden Gesamtheit, und versuche die Mächtigkeit der Teilmengen zu bestimmen.
[Zwei Mengen heißen disjunkt, wenn sie keine gemeinsamen Elemente haben.]
Hier bieten sich zwei mögliche Ansätze.

Gruppiere die Summenzerlegungen
I.   nach ihrem größten Summanden
II.  nach der Anzahl der Summanden
Beide werden zum Ziel führen.

I. Summenzerlegungen nach Größe der Summanden



Ich führe die Bezeichnung z(n) für die gesuchte Anzahl ein und bezeichne die Anzahl der Summenzerlegungen von n in denen der größte vorkommende Summand gleich m ist mit b(n,m).

Die Aufteilung der Summenzerlegungen für n nach dem größten vorkommenden Summanden ist disjunkt.

Summenzerlegungen der 7, geordnet nach größten vorkommenden Summanden

Es ist
[1]      z(n) = b(n,1) + b(n,2) + ... + b(n,n).
Weiter muß man nicht gehen, denn b(n,n+1), b(n,n+2) usw. sind 0.
Das führt auf die Frage nach der Berechung der b(n,m).

Wie man sich leicht überzeugt, gelten die Anfangsbedingungen:
b(n,m) = 0, wenn m > n
b(n,0) = 0, für alle n > 0
b(n,1) = 1, für alle n > 0
b(0,0) = 1, aus logischen Erwägungen.
Wenn eine Summenzerlegung einen maximalen Summanden m hat, dann ergibt sich daraus durch Weglassen dieses Summanden eine Summenzerlegung von n-m, in der der größte vorkommende Summand m' höchstens gleich m ist.
Hat man zwei verschiedene solche Summenzerlegungen von n, dann erhält man nach diesem Verfahren verschiedene Summenzerlegungen von n-m (mit maximalem Element <=m). Es ist somit
[2]      b(n,m) <= b(n-m, 1) + ... + b(n-m, m-1) + b(n-m, m)
Umgekehrt: Ausgehend von einer Summenzerlegung von n-m mit maximalem Summanden kleiner oder gleich m bildet man eine Summenzerlegung von n mit maximalem Summanden m, indem man einen Summanden m hinzufügt.
Hat man zwei verschiedene solche Summenzerlegungen von n-m, dann erhält man nach diesem Verfahren verschiedene Summenzerlegungen von n (mit maximalem Element m).
[3]      b(n-m, 1) + ... + b(n-m, m-1) + b(n-m, m) <= b(n,m)
Aus [2] und [3] folgt Gleichheit:
[4]      b(n,m) = b(n-m, 1) + ... + b(n-m, m-1) + b(n-m, m)
Dieses erste Ergebnis ermöglicht schon die Berechnung der b(n,m) mit einem Computer.
Unschön ist hierbei die variable Länge der Rekursion.

Wir betrachten das Problem nun von einer anderen Seite.
Wesentlich ist folgende Überlegung:

Die Summenzerlegungen von n in Summanden <= m kann man disjunkt aufteilen nach der Häufigkeit des Summanden m.
Wenn der Summand m genau einmal vorkommt, dann kann eine Summenzerlegung von n-1 mit größtem Summanden m-1 konstruieren, indem man von dem Summanden m eins wegnimmt.
Wenn der Summand m aber mehrfach vorkommt, dann ergibt das Streichen dieses Summanden eine Summenzerlegung von n-m, in der der größte vorkommende Summand immer noch m ist.

Somit gelangt man zu der Gleichung:
[5]      b(n,m) = b(n-1,m-1) + b(n-m,m)
Gleichung [5] ist das Erkennungsmerkmal vieler Varianten von Summenzerlegungen. Wir werden dieser Identität noch mehrmals begegnen.
Anmerkung: Gleichungen wie [5] werden als Differenzengleichungen bezeichnet. Für bestimmte Typen von Differenzengleichungen sind Verfahren bekannt, eine explizite Form der durch die Differenzengleichung und die Anfangswerte impizit gegebenen Funktion zu bestimmen. Diese Verfahren sind eng verwandt mit den Methoden zur Lösung von Differentialgleichungen.
Was für stetige Funktionen die Differentialgleichungen sind in der Kombinatorik die Differenzengleichungen!
Und genau wie nicht jede Differentialgleichung eine explizit bekannte Lösung hat, ist es auch hier:
Für die Differenzengleichung [5] ist keine explizite Form der Lösung bekannt. Wenn ich zu einem späteren Zeitpunkt näher auf Differenzengleichungen und Lösungsverfahren eingehen werden, dann werde ich dazu andere Beispiele brauchen.

II. Summenzerlegungen nach Anzahl der Summanden

Ich verwende weiter die Bezeichnung z(n) für die Anzahl der Summenzerlegungen, und bezeichne die Anzahl der Summenzerlegungen von n in genau k Summanden mit a(n,k).

Die Aufteilung der Summenzerlegungen für n nach der Anzahl der Summanden ist disjunkt.

Summenzerlegungen der 7, geordnet nach größten vorkommenden Summanden

Es gilt:
[6]      z(n) = a(n,1) + a(n,2) + ... + a(n,n)
Mit der Erfahrung aus dem vorigen Abschnitt wage ich sogleich folgenden Anzatz:

Die Summenzerlegungen von n in genau k Summanden kann man disjunkt aufteilen nach dem kleinsten Summanden.
Der kleinste Summand ist entweder eine 1 oder er ist größer als 1.
Wenn der kleinste Summand größer als 1 ist, dann kann man von jedem Summanden eins wegnehmen und es ergibt sich eine Summenzerlegung von n-k mit genau k Summanden. Wenn der kleinste Summand 1 ist, dann kann man einen Summanden 1 weglassen und es verbleibt eine Summenzerlegung von n-1 in k-1 Summanden.
[7]      a(n,k) = a(n-1,k-1) + a(n-k,k)
Für die Berechnung der a(n,k) nach Beziehung [7] benötigen wir die Anfangswerte:
a(0,0) = 1
a(n,0) = 0, für n > 0
a(n,1) = 1, wenn n > 0
a(n,k) = 0, wenn k > n
Eine Tabelle der a(n,m) ist zugleich eine Tabelle der b(n,m):
     n|0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
-+----------------------------------------------------
k 0|1
(m) 1| 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2| 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
3| 1 1 2 3 4 5 7 8 10 12 14 16 19 21 24 27 30 33
4| 1 1 2 3 5 6 9 11 15 18 23 27 34 39 47 54 64
5| 1 1 2 3 5 7 10 13 18 23 30 37 47 57 70 84
6| 1 1 2 3 5 7 11 14 20 26 35 44 58 71 90
7| 1 1 2 3 5 7 11 15 21 28 38 49 65 82
8| 1 1 2 3 5 7 11 15 22 29 40 52 70
9| 1 1 2 3 5 7 11 15 22 30 41 54
10| 1 1 2 3 5 7 11 15 22 30 42

[Tabelle a(n,k) bzw. b(n,m)]


Es ist stets a(n,k) = b(n,k), denn die Rekursionen sind gleich und die Anfangswerte ebenfalls.

Mit [1] und [5] bzw. [7] lassen sich die z(n) berechnen.

III. Dualität

Die Beziehung a(n,k) = b(n,k) signalisiert eine Dualität der beiden Probleme.
Es gibt einen einfachen und anschaulichen Weg die zueinander dualen Summenzerlegungen gemaß I. oder II. zu bestimmen.

Die Abbildung zeigt eine Summenzerlegung der 7 im sog. Ferrers-Diagramm.
Die Zerlegung 7 = 4 + 2 + 1 wurde in den Zeilen eingetragen. Dreht man das Diagramm um 90° oder liest die Anzahl der gefüllte Kästchen in den Spalten, dann erhält man 7 = 3 + 2 + 1 + 1.

Konjugierte Summenzerlegungen der 7

Die eine Zerlegung hat das maximale Element 4 und die andere hat 4 Summanden.

Zwei Summenzerlegungen, die durch diese Operation auseinander hervorgehen, nennt man konjugiert.
Summenzerlegungen sind selbstkonjugiert, wenn das Konjugierte einer Summenzerlegung mit der Summenzerlegung übereinstimmt.

Mit Hilfe der Dualität läßt sich beispielsweise die Anzahl der "Summenzerlegungen in lauter verschiedene Summanden" finden.

IV. Leere Behälter

Die bisherigen Überlegungen galten Summenzerlegungen mit positiven Summanden.
Nun noch ein Blick auf Zerlegungen in nichtnegative Summanden.
Zur genauen Unterscheidung nenne ich diese Summenzerlegungen°.

Nun macht es keinen Sinn nach der Anzahl der Sumenzerlegungen° einer natürlichen Zahl n zu fragen, denn schließlich kann man durch Hinzufügen von weiteren Nullen beliebig viele andere Summenzerlungen° erzeugen.

Ich will aber die Anzahl der Summenzerlegungen° betrachten, die eine natürliche Zahl n in genau k nichtnegative Summanden zerlegt.
Diese Anzahl nenne ich c(n,k).

Es ist
[8]      c(n,k) = a(n+k,k)
denn aus einer Summenzerlegung° von n mit k nichtnegativen Summanden wird eine Summenzerlegung von n+k mit k positiven Summanden, wenn man zu jedem Summanden 1 addiert und vice versa.

Unmittelbar haben wir damit die Rekursion:
[9]      c(n,k) = c(n,k-1) + c(n-k,k)
Diese Beziehung läßt sich nach dem oben schon vorgeführten Muster auch direkt zeigen:

Eine Summenzerlegung° von n in k Summanden enthält eine 0 oder enthält keine 0.
Die Anzahl der Summenzerlegungen° von n ohne eine 0 ist gleich der Anzahl der Summenzerlegungen° von n-k in k Summanden. Die Anzahl der Summenzerlegungen° mit einer 0 ist gleich der Anzahl der Summenzerlegungen° von n in k-1 Summanden.

Die Anfangswerte für c(n,k) sind:
c(0,k) = 1
c(n,0) = 0 (n>0)
c(1,k) = 1 (k>0)
c(n,1) = 1 (n>0)
Der Anfang einer Tabelle der c(n,k)

n| 0 1 2 3 4 5 6 7 8
-+--------------------------
k 0| 1 1 1 1 1 1 1 1 1
1| 1 1 1 1 1 1 1 1
2| 1 2 2 2 2 3 3 3
3| 1 2 3 3 3 3 3 3
4| 1 3 4 4 4 4 4 4
5| 1 3 5 6 7 7 7 7
6| 1 4 7 9 10 11 11 11
7| 1 4 8 11 13 14 15 15
8| 1 5 10 14 17 19 20 21

[Tabelle c(n,k)]


Aus jeder Summenzerlegung von n in weniger als k Summanden erhält man eine Summenzerlegung° von n in k Summanden, indem man die erforderliche Anzahl Nullen hinzufügt.

Darum gilt:
fed-Code einblenden
Mit [8] wird daraus:
fed-Code einblenden
Interessanter ist nun, daß man auch mit den c(n,k) die z(n) berechnen kann.

Es gilt:
fed-Code einblenden
Beweis: Zur Übung überlassen.

Das bedeutet: die Summe der m-ten Gegendiagonalen in der Tabelle der c(n,k) ist gleich der Anzahl der Summenzerlegungen von m. Die Beziehung [8] zwischen den a(n,k) und den c(n.k) ist aufschlußreich, denn sie zeigt, wie man etwa die Frage nach den Summenzerlegungen² angehen kann.
Mit Summenzerlegung² meine ich Zerlegungen von n in Summanden, die alle mindestens 2 sind.

Fortsetzung folgt

In einigen Tagen werde ich über die Erzeugenden Funktionen für die Summenzerlegungen berichten und erklären, welche zusätzlichen Aufschlüsse man durch Erzeugende Funktionen über die Struktur des Problems erhält.

Wer mag, kann sich in der Zwischenzeit mit folgender Frage beschäfigen:
Frage: Wieviele Möglichkeiten gibt es, einen Betrag von 1 Euro in Münzen zu zahlen?
Damit möchte ich heute enden.

Zur Fortsetzung über Erzeugende Funktionen

Matroid 2002



Ich verweise auf A000041, das ist der Eintrag für die z(n) in Sloane's Datenbank der ganzzahligen Folgen. Dort findet man zahlreiche Referenzen und Links.

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


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 :: Duales Problem :: Rekursion :: Summenzerlegungen :: Sonstige Mathematik :
Summenzerlegungen 2 [von matroid]  
Im ersten Beitrag war definiert worden, was eine Summenzerlegung einer natürlichen Zahl n ist und u.a. gefragt worden: Wieviele verschiedene Summenzerlegungen gibt es für eine natürliche Zahl n? Heute will ich mit der Erforschung des Problems beginnen. Rekursive Ansätze,Summenzerlegungen nach der Größe bzw. Anzahl der Summanden, Dualität
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
Verwandte Links
 
Besucherzähler 8628
 
Aufrufstatistik des Artikels
Insgesamt 936 externe Besuche zwischen 2017.07 und 2017.07 [Anzeigen]
DomainAnzahlProz
http://matheplanet.com30.3%0.3 %
http://www.hardwareluxx.de25827.6%27.6 %
http://google.de63167.4%67.4 %
http://google.nl212.2%2.2 %
http://google.dk40.4%0.4 %
http://suche.gmx.net10.1%0.1 %
http://www.bing.com60.6%0.6 %
http://www.searchmobileonline.com10.1%0.1 %
http://www.ecosia.org10.1%0.1 %
http://r.duckduckgo.com20.2%0.2 %
http://suche.t-online.de10.1%0.1 %
http://search.incredibar.com20.2%0.2 %
http://de.search.yahoo.com10.1%0.1 %
http://search.sweetim.com10.1%0.1 %
http://search.conduit.com10.1%0.1 %
http://search.daum.net10.1%0.1 %
http://de.wow.com10.1%0.1 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 3 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2017.07.06-2017.07.20 (3x)https://www.google.de/

Häufige Aufrufer in früheren Monaten
Insgesamt 910 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2012-2016 (257x)http://www.hardwareluxx.de/community/f24/summenzerlegung-857815.html
2013-2016 (202x)http://google.de/url?sa=t&rct=j&q=
2012-2013 (41x)http://google.de/url?sa=t&rct=j&q=zerlegung einer natürlichen zahl
2014.11 (38x)http://google.de/url?sa=t&rct=j&q=zerlegung von zahlen in summanden
2013.01 (25x)http://google.de/url?sa=t&rct=j&q=zerlegung der summe
2012.11 (24x)http://google.de/url?sa=t&rct=j&q=zerlegen einer zahl in summe
2012.12 (24x)http://google.de/url?sa=t&rct=j&q=zerlegung summen
201308-10 (23x)http://google.de/url?sa=t&rct=j&q=summenzerlegung
2012.10 (22x)http://google.de/url?sa=t&rct=j&q=zerlegung von zahlen summanden trick
2012.01 (21x)http://google.de/url?sa=t&source=web&cd=9&ved=0CF0QFjAI
2012.03 (21x)http://google.de/url?sa=t&rct=j&q=zerlegung von natürlichen zahlen
2015.01 (21x)http://google.nl/url?sa=t&rct=j&q=
2013.11 (20x)http://google.de/url?sa=t&rct=j&q=anzahl der summanden
2013.05 (20x)http://google.de/url?sa=t&rct=j&q=teil summenzerlegung
2012.05 (19x)http://google.de/url?sa=t&rct=j&q=zerlegung in die summe von ausdrücken
2012.04 (18x)http://google.de/url?sa=t&rct=j&q=summenzerlegungen 2 matroid
2012.07 (16x)http://google.de/url?sa=t&rct=j&q=zerlegung in summe
2013.06 (15x)http://google.de/url?sa=t&rct=j&q=wieviele zerlegungen hat eine zahl
2013.02 (12x)http://google.de/url?sa=t&rct=j&q=wieviele möglichkeiten betrag zerlegen
2012.02 (12x)http://google.de/url?sa=t&rct=j&q=zahl in summanden aufteilen
2014.10 (12x)http://google.de/url?sa=t&source=web&cd=1&ved=0CBwQFjAA
2012.08 (10x)http://google.de/url?sa=t&rct=j&q=summenzerlegungen nach größe der summande...
2014.07 (9x)http://google.de/url?sa=t&source=web&cd=3&ved=0CCQQFjAC
2013.07 (9x)http://google.de/url?sa=t&rct=j&q=zerlegung von 16 als summe von vier summand...
2012.06 (9x)http://google.de/url?sa=t&rct=j&q=zerlegung einer natürlichen zahl in eine s...
2013.03 (6x)http://google.de/url?sa=t&rct=j&q=zerlegung summe 14
2016.03 (4x)http://google.dk/url?sa=t&rct=j&q=

[Seitenanfang]

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

Re: Summenzerlegungen 2
von Ende am Sa. 13. Juli 2002 18:50:09


Hallo!



Eine Anmerkung:

Die Gleichung



[5] b(n,m) = b(n-1,m-1) + b(n-m,m)



kann man ganz leicht mit der Gleichung



[4'] b(n,m) = b(n-m, 1) + ... + b(n-m, m-1) + b(n-m, m)



einsehen.



Denn:

Nach [4'] ist b(n, m) = (b(n-m, 1) + ... + b(n-m, m-1)) + b(n-m, m).

Nun addiere in den ( ... )-Ausdruecken eine namhafte Null, und erhalte:

b(n, m) = (b((n-1)-(m-1), 1) + ... + b((n-1)-(m-1), m-1)) + b(n-m, m).

Das ergibt aber wieder mit [4'] angewendet auf die ( ... )-Ausdruecke:

b(n, m) = b(n-1, m-1) + b(n-m, m).



Und genau das wollten wir erhalten.



Gruss, E. wink

 [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]