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

Ein Ausflug in die Kombinatorik

 
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.

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 = {(v₁,n₁), (v₂,n₂), ..., (v_r,n_r) } mit verschiedenen n_i, für die gilt:

sum(v_i*n_i,i=1,r) = n
  r > 0
  v_i > 0, i=1,...,r
  n_i > 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.

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) }

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.

Frage 1: Wieviele verschiedene Summenzerlegungen gibt es für eine natürliche Zahl n?

Zählen kann doch jeder

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

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?

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?

Frage 4: Wieviele Summenzerlegungen mit genau k Elementen hat eine natürliche Zahl n?

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

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