Perfekte Partition

In der Additiven Zahlentheorie, einem der mathematischen Teilgebiete innerhalb der Zahlentheorie, wie auch im Teilgebiet der Kombinatorik untersucht man, ob eine zu einer natürlichen Zahl gegebene Partition so beschaffen ist, dass jede kleinere natürliche Zahl sich ebenfalls als Summe von einzelnen Summanden dieser Partition eindeutig darstellen lässt. Diese Fragestellung und das zugehörige Konzept gehen zurück auf den Mathematiker Percy Alexander MacMahon (1854–1929).

Definition

Es sei eine natürliche Zahl $\,n\in \mathbb {N} \,$ gegeben und weiter eine Partition

$\,(n=n_{1}+n_{2}+\ldots +n_{k})\,$ mit $\,k,n_{1},n_{2},\ldots ,n_{k}\in \mathbb {N} \,$ und $\,n_{1}\geq n_{2}\geq \ldots \geq n_{k}$.

Genügt diese Partition zusätzlich der Bedingung, dass

jede der Zahlen $\,m=1,2,\ldots ,n-1\,$ sich stets aus gewissen der in dieser Partition auftretenden Summanden $\,n_{1},n_{2},\ldots ,n_{k}\,$ auf genau eine Art als Summe darstellen lässt,

so bezeichnet man sie als perfekt oder auch als vollkommen (englisch perfect partition).

Eigenschaften und Beispiele

• In einer perfekten Partition tritt die $\,1\,$ stets als kleinster Summand auf.
• Für jedes $\,n\in \mathbb {N} \,$ ist die aus exakt $\,n\,$ Summanden $\,1\,$ aufgebaute Partition $\,(n=1+1+\ldots +1)\,$ stets perfekt. Weiter ist für jede ungerade Zahl $\,n=2\cdot k+1\,(k\in \mathbb {N} )\,$ die aus einem einzigen Summanden $\,1\,$ und aus exakt $\,k\,$ Summanden $\,2\,$ aufgebaute Partition $\,(n=1+2+2+\ldots +2)\,$ stets perfekt.
• Für die Zahl $\,7\,$ sind die Partitionen $\,(7=4+2+1)\,$ , $\,(7=4+1+1+1)\,$ , $\,(7=2+2+2+1)\,$ und $\,(7=1+1+1+1+1+1+1)\,$ perfekt.
• Für die Zahl $\,4\,$ ist $\,(4=2+1+1)\,$ keine perfekte Partition, denn es gibt etwa für die darunter liegende Zahl $\,2\,$ die beiden Partitionen $\,(2=2)\,$ und $\,(2=1+1)\,$.
• Für die Zahl $\,9\,$ ist $\,(9=4+2+2+1)\,$ keine perfekte Partition, denn es gibt etwa für die darunter liegende Zahl $\,5\,$ die beiden Partitionen $\,(5=4+1)\,$ und $\,(5=2+2+1)\,$.

Satz von MacMahon

Die perfekten Partitionen stehen in unmittelbarer Beziehung zu den sogenannten geordneten Faktorisierungen von natürlichen Zahlen.

Eine solche geordnete Faktorisierung ist für eine natürliche Zahl $\,f\in \mathbb {N} \,$ mit $\,f>1\,$ genau dann gegeben, wenn ein $\,t\in \mathbb {N} \,$ sowie ein aus $\,f\,$-Teilern $\,f_{1}>1,\ldots ,f_{t}>1\,$ bestehendes $\,t\,$-Tupel $\,(f_{1},\ldots ,f_{t})\,$ vorliegen, so dass $\,f\,$ der Produktdarstellung $\,f=f_{1}\cdot \ldots \cdot f_{t}\,$ genügt.

Hier gilt nun ein grundlegender Satz, der dem Mathematiker James Joseph Tattersall zufolge auf MacMahon zurückgeht und sich darstellen lässt wie folgt:

Für jede natürliche Zahl $\,n\in \mathbb {N} \,$ stimmen die Anzahl der perfekten Partitionen von $\,n\,$ einerseits und die Anzahl der geordneten Faktorisierungen der Folgezahl $\,f=n+1\,$ andererseits stets überein.

Korollar

Aus dem MacMahon'schen Satz gewinnt man eine direkte Folgerung:

Ist für eine natürliche Zahl $\,n\in \mathbb {N} \,$ die Folgezahl $\,f=n+1\,$ eine Primzahl, so besitzt $\,n\,$ genau eine perfekte Partition, nämlich die aus den $\,n\,$ Summanden $\,1\,$ aufgebaute triviale Partition $\,(n=1+1+\ldots +1)\,$ .

Anzahlfunktion

Mit den perfekten Partitionen ist die Frage nach den zugehörigen Anzahlen verbunden. Es geht also für jedes $\,n\in \mathbb {N} \,$ um die Anzahl aller Möglichkeiten, $\,n\,$ in Form einer perfekten Partition darzustellen.

Diese Zahlenfolge der $\,\mathrm {Per} (n)\,$ beginnt mit folgenden Werten:

$(\mathrm {Per} \left(n\right))_{n=1,2,3,\ldots }=\left(1,1,2,1,3,1,4,2,3,1,8,\dotsc \right)$ (Folge A002033 in OEIS).

Dabei gelten für diese Anzahlen oft interessante Kongruenzbeziehungen, die denen ähneln, die schon Srinivasa Ramanujan für die gewöhnliche Partitionsfunktion gefunden hat. So ist etwa für je zwei natürliche Zahlen $\,k\geq 2\,,\,n\,$ und jede Primzahl $\,p\,$ stets die Kongruenz

${\mathrm {Per} ({n\cdot p^{k}-1})}\equiv 0{\pmod {2^{k-1}}}$

gegeben.

Verallgemeinerungen

Das Konzept der perfekten Partition ist weiter verallgemeinert worden. So legten etwa A. K. Agarwal und R. Sachdeva in 2018 die sogenannten n-color perfect partitions (deutsch etwa: n-gefärbte perfekte Partitionen) vor.

Literatur

• Martin Aigner: Combinatorial Theory (= Grundlehren der mathematischen Wissenschaften in Einzeldarstellungen. Band 234). Springer-Verlag, Berlin, New York 1979, ISBN 0-387-90376-3 (MR0542445). 
• A. K. Agarwal, M. V. Subbarao: Some properties of perfect partitions. In: Indian Journal of Pure and Applied Mathematics. Band 22, 1991, S. 737–743 (MR1128892). 
• A. K. Agarwal, R. Sachdeva: Combinatorics and n-color perfect partitions. In: Ars Combinatoria. Band 136, 2018, S. 29–43 (MR3752586). 
• Heinz-Richard Halder, Werner Heise: Einführung in die Kombinatorik (= Mathematische Grundlagen für Mathematiker, Physiker und Ingenieure). Hanser Verlag, München, Wien 1976, ISBN 3-446-12140-4 (MR0498160). 
• P. A. MacMahon: Combinatory Analysis. Cambridge University Press, Cambridge 1915. 
• Augustine O. Munagi: Perfect compositions of numbers. Art. 20.5.1. In: Journal of Integer Sequences. Band 23, 2020 (MR4115755). 
• John Riordan: An Introduction to Combinatorial Analysis. Princeton University Press, Princeton 1978, ISBN 0-691-08262-6. 
• James J. Tattersall: Elementary number theory in nine chapters. Cambridge University Press, Cambridge 1999, ISBN 0-521-58531-7 ([1]). 
• Wang, E Fang: Perfect partitions. In: Chinese Annals of Mathematics. Series B. Band 7, 1986, S. 267–272 (MR0867751). 

Weblinks

• Eric W. Weisstein: Perfect Partition. In: MathWorld (englisch).
• Eintrag Perfekte Partition im Lexikon der Mathematik (2017)