Die Mathe-Redaktion - 16.01.2018 20:35 - 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 754 Gäste und 31 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Mathematik: Summenzerlegungen
Freigegeben von matroid am So. 07. Juli 2002 00:05:12
Verfasst von matroid -   12743 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
Mathematik

\(\begingroup\)

Ein Ausflug in die Kombinatorik

Bild  
Wir starten mit der Frage:
Auf wieviele Arten kann man eine Zahl als Summe von Zahlen schreiben?
Diese Frage ist nicht eindeutig zu verstehen. Die Präzision in der Fragestellung muß verbessert werden.
Auf wieviele Arten kann man eine natürliche Zahl als Summe natürlicher Zahlen schreiben?
 
Auch das läßt Raum für Interpretationen. Nächster Versuch:
Auf wieviele Arten kann man eine natürliche Zahl als Summe beliebig vieler positiver natürlicher Zahlen darstellen, wobei zwei Darstellungen nur dann als verschieden gelten, wenn sie sich hinsichtlich der vorkommenden verschiedenen Summanden oder der Vielfachheit der verschiedenen Summanden unterscheiden?

Eine Darstellung in diesem Sinne heißt Summenzerlegung oder auch numerische Partition.


Das bedeutet, daß die Darstellungen von 17 als 5+5+3+4 oder 4+3+5+5 nicht verschieden sind, denn die beiden Darstellungen verwenden die gleichen Summanden (die 3, die 4 und die 5), die 5 kommt in beiden Darstellungen 2 mal vor, und die 3 und die 4 kommen jeweils 1 mal vor.
Dagegen sind die Darstellungen 17 = 10+3+4 und 17 = 3+5+5+4 verschieden, denn ein Summand (etwa die 10) kommt nicht in beiden Darstellungen vor.
Auch die Darstellungen 17 = 5+4+4+2+2 und 17 = 5+4+2+2+2+2 sind verschieden, zwar sind die verschiedenen Summanden in beiden Fällen die 2, 4 und 5, aber die Vielfachheiten der Summanden stimmen nicht überein - einmal kommt die 4 zweimal, das andere mal nur einmal vor.

Zwei Summenzerlegungen sind also gleich, wenn die eine Darstellung zur anderen umsortiert werden kann.

Es ist gewollt, daß die Darstellung von 17 = 17 eine Summenzerlegung ist. Die Ausdrucksweise 'beliebig viele' bedeute eine positive natürliche Zahl. Die 1 ist mit Absicht eingeschlossen. Das muß man nicht so machen, aber es ist meine Entscheidung und ich begründe dies damit, daß es dadurch leichter wird, die Summenzerlegungen zu zählen.

Nun denkt man sich bei einer Summe aber doch eher mindestens zwei Summanden. Ich muß die Aufgabenstellung noch genauer formulieren und kann nun nicht mehr umhin, die sprachliche Fassung des Problems durch eine formelle zu ersetzen:
Definition (Multimenge)
Eine Multimenge auf einer Menge A ist eine Menge geordneter Paare (v,a), wobei a aus A und v eine natürliche Zahl oder Unendlich ist.

Eine Multimenge soll man sich als Menge mit Vielfachheiten vorstellen.
Folgendes ist ein Beispiel für eine Multimenge:

{ (4,Glas Wein), (3,Cola), (8,halbe Bier), (2,Wasser) }
[Ja, Kellner müssen mit Multimengen umgehen können!]

Definition (Summenzerlegung)
Eine Summenzerlegung einer natürlichen Zahl n ist eine Multimenge M = {(v1,n1), (v2,n2), ..., (vr,nr) } mit verschiedenen ni, für die gilt:
fed-Code einblenden
  r > 0
  vi > 0, i=1,...,r
  ni > 0, i=1,...,r
Die Menge aller Summenzerlegungen einer natürlichen Zahl n ist eine Menge, deren Elemente Multimengen sind.
Gefragt ist nach der Anzahl der Elemente der Menge der Summenzerlegungen von n.
Nun ist die Aufgabe nicht mehr mißzuverstehen, oder?
[Freiwillige Zusatzaufgabe: Diskutiere die Behauptung: "Indem die Mathematik unmißverständlich sein will, wird sie unverständlich!"]

Beispiel für eine Summenzerlegung der Zahl 9:

{ (1,5), (1,2), (2,1) }

Zu lesen:

" 1 mal 5, 1 mal 2, 2 mal 1 "

Dies ist eine Summenzerlegung der natürlichen Zahl 9,
weil 1*5 + 1*2 + 2*1 = 9 ist.

Eine andere Summenzerlegung der 9 ist

{ (1,5), (2,2) }
Wenn man weiß, was man meint, dann kann man auch gerne wieder mit weniger formalem Aufwand schreiben.
Die verschiedenen Summenzerlegungen der 9 sind:
9 = 9
9 = 8 + 1
9 = 7 + 2
9 = 7 + 1 + 1
9 = 6 + 3
9 = 6 + 2 + 1
9 = 6 + 1 + 1 + 1
9 = 5 + 4
9 = 5 + 3 + 1
usw.
Die Frage lautet also:
Frage 1: Wieviele verschiedene Summenzerlegungen gibt es für eine natürliche Zahl n?

Zählen kann doch jeder

Sagt man!
Bei der ersten Bekanntschaft mit der Kombinatorik lernt man über Permutationen, Kombinationen und Variationen. Dafür werden Formeln gelehrt, die Potenzen, Fakultäten und Binomialkoeffizienten enthalten.

Das ist die elementare Kombinatorik. Das hier gestellte Problem kann man damit nicht lösen.

Was ist das Ziel der Kombinatorik?
Nun, Formeln für Anzahlen geben, ist die falsche Antwort.
Richtig ist: Ziel der Kombinatorik ist die Lösung von Abzählproblemen. Allerdings ist eine Lösung nicht notwendig eine Formel, sondern allgemeiner, eine Lösung ist eine Methode mit der Abzählungen vorgenommen werden können. Das ist allgemein ein Algorithmus, denn auch eine Formel mit Fakultäten ist nichts anderes als die komprimierte Fassung eines Algorithmus'.
Die Kombinatorik ist die Wissenschaft von diesen Methoden, von den Denkweisen und Wegen auf denen man zu einer Lösung gelangt.

Manche glauben, daß Kombinatorik kein wesentliches Feld der Mathematik sei. Meiner Meinung nach ist Kombinatorik eine Methode des mathematischen Denkens, die sich als unsagbar produktiv erwiesen hat und dabei häufig höchst intuitive und vom ästhetischen Standpunkt (des Mathematikers) schöne Ergebnisse hervorbringt - Ergebnisse, die außerdem für die Berechnung mit Computern unmittelbar einsetzbar sind.

Jede Beschäftigung mit einem Abzählproblem beginnt damit, die Aufgabenstellung zu verstehen, nötigenfalls zu präzisieren und präzise auszudrücken (siehe oben). Es macht schließlich einen wesentlichen Unterschied, ob man die Reihenfolge der Summanden in einer Summenzerlegung unterscheidet oder nicht.

Zur Demonstration habe ich obige Aufgabe ausgewählt.
Damit aber die weiteren Erklärungen auf fruchtbaren (vorbereiteten) Boden fallen, mache ich an dieser Stelle eine Pause von einigen Tagen, damit die Interessierten Zeit haben, sich mit der gestellten Frage zu beschäftigen.

Äquivalente und verwandte Fragen

Ob als Hilfe oder zur Verwirrung, ich formuliere nun noch eine Frage, die zur oben gestellten äquivalent ist, d.h. wenn man das eine zählen kann, dann kann man auch das andere zählen:
Frage 2: Auf wieviele verschiedene Weisen lassen sich n nicht unterscheidbare Kugeln in nicht unterscheidbare Behältern verteilen, so daß kein Behälter leer bleibt?
Dieses Problem ist wiederum nahe verwandt mit folgendem:
Frage 3: Auf wieviele verschiedene Weisen lassen sich n nicht unterscheidbare Kugeln in k nicht unterscheidbaren Behältern verteilen, so daß kein Behälter leer bleibt?
Äquivalent zu Frage 3 ist:
Frage 4: Wieviele Summenzerlegungen mit genau k Elementen hat eine natürliche Zahl n?
Und eine naheliegende Variation von Frage 3 ist diese:
Frage 5: Auf wieviele verschiedene Weisen lassen sich n nicht unterscheidbare Kugeln in k nicht unterscheidbaren Behältern verteilen?
[Behälter dürfen also leer bleiben.]
[Zur Fortsetzung]


 
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 :: natürliche Zahlen :: Partition :: Summenzerlegungen :: Rekursion :
Summenzerlegungen [von matroid]  
Ein Ausflug in die Kombinatorik, der die Frage behandelt, wieviele Summenzerlegungen einer natürlichen Zahl n in natürliche Summanden - auch Partitionen genannt - es gibt.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
Verwandte Links
 
Besucherzähler 12743
 
Aufrufstatistik des Artikels
Insgesamt 364 externe Besuche zwischen 2018.01 und 2018.01 [Anzeigen]
DomainAnzahlProz
http://matheplanet.com164.4%4.4 %
http://matheplanet.de10.3%0.3 %
http://google.de30583.8%83.8 %
http://google.dk164.4%4.4 %
http://www.bing.com92.5%2.5 %
http://google.lt61.6%1.6 %
http://r.duckduckgo.com30.8%0.8 %
http://www.benefind.de20.5%0.5 %
http://google.ru20.5%0.5 %
http://google.at10.3%0.3 %
http://google.ch10.3%0.3 %
http://search.sweetim.com20.5%0.5 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 14 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2018.01.03-2018.01.15 (6x)https://www.google.de/
2018.01.15 14:43http://matheplanet.com/default3.html?call=viewtopic.php?topic=84955&ref=https...
2018.01.06-2018.01.13 (2x)https://www.google.at/
2018.01.13 17:15viewtopic.php?topic=2534&ref=https://www.google.de/&ff=y
2018.01.10-2018.01.12 (2x)viewtopic.php?topic=84955&ref=https://www.google.de/&ff=y
2018.01.11-2018.01.12 (2x)viewtopic.php?topic=84955&ref=https://www.google.ch/&ff=y

Häufige Aufrufer in früheren Monaten
Insgesamt 325 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2013-2017 (120x)http://google.de/url?sa=t&rct=j&q=
2012-2015 (23x)http://google.de/url?sa=t&rct=j&q=summenzerlegung
2014.11 (20x)http://google.de/url?sa=t&rct=j&q=partitionen summenzerlegungen nach anzahl ...
2013.02 (20x)http://google.de/url?sa=t&rct=j&q=variation multimenge
2013.05 (20x)http://google.de/url?sa=t&rct=j&q=summenzerlegung induktion
2012.12 (13x)http://google.de/url?sa=t&rct=j&q=wieviele verschiedene summenzerlegungen gib...
2012.07 (12x)http://google.de/url?sa=t&rct=j&q=was bedeutet multimenge
2013.04 (9x)http://google.de/url?sa=t&rct=j&q=summenzerlegung beweis
2014.07 (8x)http://google.de/url?sa=t&source=web&cd=2&ved=0CCUQFjAB
2012.05 (8x)http://google.de/url?sa=t&rct=j&q=zerlegung einer summe in unterschiedlichen ...
2013.01 (8x)http://google.dk/imgres?sa=X&tbo=d&biw=1280&bih=657&tbm=isch&tbnid=myZo5tc1ot...
2014-2016 (8x)http://www.bing.com/search?q=summenzerlegung&qs=n&form=QBRE&pq=summenzerlegun...
2012.02 (8x)http://google.de/url?sa=t&rct=j&q=summenzerlegung ganzer zahlen + anzahl
2014.05 (8x)http://google.de/url?sa=t&rct=j&q=beweis zahlenpartition
2012.04 (8x)http://google.de/url?sa=t&source=web&cd=5&ved=0CEIQFjAE
2012.03 (7x)http://google.de/url?sa=t&rct=j&q=kombinatorik summenzerlegung
2012.09 (6x)http://google.de/url?sa=t&rct=j&q=auf wieviele arten lässt sich die zahl n a...
2012.01 (6x)http://google.lt/imgres?q=kombinatorik
2012.10 (5x)http://google.dk/imgres?q=Kombinatorik
2013.03 (4x)http://google.de/url?sa=t&rct=j&q=summenzerlegung online
201701-12 (4x)http://google.de/

[Seitenanfang]

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

Re: Summenzerlegungen
von Friedel am So. 07. Juli 2002 12:58:05

\(\begingroup\)
Am einfachsten fällit mir Frage 5. Die kann man spontan ohne Nachdenken beantworten und die Antwort beweisen.



Diese Aufgabe hat keine endliche Lösung. Angenommen es gäbe eine, dann könnte man bei der Lösung mit den meisten Behältern immer noch einen leeren Behälter dazu stellen und hätte eine neue Lösung. Es gibt also unendlich viele Weisen.



Ubrigens: Schönes Bild.\(\endgroup\)

 [Bearbeiten]

Re: Summenzerlegungen
von Ende am Mo. 08. Juli 2002 13:10:06

\(\begingroup\)
Klasse, Klasse, Klasse! *g*



Mir gefaellt der Artikel und das, worauf er Aussicht bietet. MP als passives UND aktives Matheforum. Ich bin schon sehr gespannt, wohin diese Entwicklung fuehrt.



Zum Inhalt des Artikels.

Ich wuerde wie immer beim Zaehlen, dem Zaehlgut zunaechst mal einen Namen geben. Fuer eine natuerliche Zahl n sei vielleicht mit Z(n) die Anzahl der Summenzerlegungen im Sinne des Artikels bezeichnet.

Nun kann man sich ja noch vorgeben, dass man immer nur solche Summen zaehlt, die von links nach rechts absteigend nach der Groesse der Summanden geordnet sind.

Wir zaehlen also 10 = 5 + 3 + 1 + 1, aber nicht 10 = 3 + 5 + 1 + 1. Auf diese Weise ist aus der Klasse der aequivalenten Summenzerlegungen immer ein eindeutiger Repraesentant waehlbar.

Offenbar ist Z(1) = 1.

Und nun wuerde ich ueberlegen, ob man nicht Z(n) irgendwie umschreiben kann.

Vielleicht Z(n) = 1 + Z(1) + Z(2) + Z(3) + ... + Z(n div 2). Oder so. War ein Schnellschuss. Ich muss jetzt zur Vorlesung. *g*

(n div 2 bezeichne das Ergebnis beim ganzzahligen Teilen von n durch 2.)



Gruss, E.



P.S.: Man entschuldige die gedankliche Unordnung. Ich war so begeistert vom Artikel, dass ich unbedingt was beisteuern musste. *g*\(\endgroup\)

 [Bearbeiten]

Re: Summenzerlegungen
von Friedel am Mo. 08. Juli 2002 19:01:57

\(\begingroup\)
Zählen kann doch jeder
steht oben im Artikel. Ich offensichtlich nicht. Dieser Punkt ist also schon mal
widerlegt.\(\endgroup\)

 [Bearbeiten]

Re: Summenzerlegungen
von Fivel am Mo. 08. Juli 2002 20:52:09

\(\begingroup\)
Ich bin zwar kein Mathematiker, was aber nicht heißt, dass ich mich nicht an diesen Aufgaben versuchen kann :)



Frage 2: Wenn n Behälter und n Kugeln zur Verfügung stehen, und in jeden Behälter eine Kugel hineinpasst, würde ich sagen: Auf n! Weisen.

Aber da ja Behälter und Kugeln nicht unterscheidbar sind, gibt es nur eine Art. (?)



Irgendwie verstehe ich aber die Aufgabenstellung nicht:

Es müssen ja mehr Kugeln als Behälter sein(kein Behälter darf leer bleiben), also gibt es (n über k) [k=Kübel,Behälter] Arten, wie man die Behälter füllen kann. Aber nachdem man die Behälter gefüllt hat, erkennt man ja nicht mehr welche Kugeln man genommen hat, da alle nicht unterscheidbar sind. Also bleibt wieder nur eine Antwort übrig?

Das "nicht unterscheidbar" verstehe ich also nicht.







Frage 3: Auf n über k Arten.



Frage 5: Wenn n > k, dann ist die selbe Antwort wie bei Frage 3.

Wenn k > n, dann kommt es auf die leeren Behälter an:

Wenn 1 Behälter von 9 leer bleibt, dann gibt es neun Arten (8 Kugeln)

Wenn 2 Behälter von 9 leer bleiben, dann gibt es 36 Arten (7 Kugeln)

Mein Lösungsvorschlag lautet daher:

(k über (k-n)) Weisen.



k=Kübel

k-n=Leere Kübel



Aber je mehr ich über diese Aufgaben nachdenke, desto ähnlicher werden sie, und umso mehr kenn ich mich noch weniger aus, als ich mich zuvor schon nicht ausgekannt hatte. ;)



Fivel\(\endgroup\)

 [Bearbeiten]

Re: Summenzerlegungen
von Ex_Mitglied_40174 am So. 14. Juli 2002 09:54:34

\(\begingroup\)
ich dachte, der Begriff natürliche Zahlen bedeute 1,2,3,.., also ganze positive ohne die Null

(

Friedrich Laher, aber mein Login wird nicht mehr akzeptiert

)\(\endgroup\)

 [Bearbeiten]

Re: Summenzerlegungen
von Ex_Mitglied_40174 am Do. 01. September 2005 19:59:00

\(\begingroup\)
Hat nicht der alte Euler sich in Briefen schon zu diesem Thema geäußert (Produkt von geometrischen Reihen...). Und sogar Ramanujan (und Hardy) hat sich der Frage der Summenzerlegung angenommen.
vgl.
www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eismumgerman.cgi\(\endgroup\)

 [Bearbeiten]

Re: Summenzerlegungen
von predator am Fr. 02. September 2005 14:01:54

\(\begingroup\)
Es würde mich wundern, wenn sie das nicht getan hätten.
Der Link funktioniert aber nicht.\(\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]