Partitionsfunktion

Partitionsfunktion P(n) in halblogarithmischer Darstellung

Die Partitionsfunktionen geben die Anzahl der Möglichkeiten an, natürliche Zahlen in Summanden zu zerlegen. Üblicherweise betrachtet man die Zerlegungen ohne Berücksichtigung der Reihenfolge. Jede solche Zerlegung wird in der Kombinatorik als (ungeordnete) Zahlpartition oder manchmal kurz Partition bezeichnet. Die Bestimmung aller Zahlpartitionen für eine bestimmte (große) natürliche Zahl ist ein wichtiges Problem sowohl in der theoretischen als auch der praktischen Informatik. Siehe dazu den Artikel Partitionierungsproblem.

Die Partitionsfunktion ohne Nebenbedingungen (Anzahl der ungeordneten Zahlpartitionen von $n$) wird als $P(n)$, manchmal auch als $p(n)$ notiert und ist Folge A000041 in OEIS. Es gibt eine Reihe von Funktionen, bei denen an die Summanden zusätzliche Bedingungen gestellt werden, zum Beispiel dass jeder Summand nur einmal vorkommen darf (strikte Zahlpartitionen), diese Variante wird ebenfalls Partitionsfunktion, manchmal auch strikte Partitionsfunktion genannt, als $Q(n)$ oder $q(n)$ notiert und ist Folge A000009 in OEIS.

Mit einer aus der Partitionsfunktion $P(n)$ abgeleiteten zeahlentheoretischen Funktion kann die Anzahl der Isomorphietypen von endlichen abelschen Gruppen angegeben werden.

Beispielwerte

Beispielwerte von P(n) und zugehörige Zahlpartitionen

n	P(n)	Zahlpartitionen
0	1	(leere Summe)
1	1	(1)
2	2	(1+1), (2)
3	3	(1+1+1), (1+2), (3)
4	5	(1+1+1+1), (1+1+2), (2+2), (1+3), (4)
5	7	(1+1+1+1+1), (1+1+1+2), (1+2+2), (1+1+3), (2+3), (1+4), (5)
6	11	(1+1+1+1+1+1), (1+1+1+1+2), (1+1+2+2), (2+2+2), (1+1+1+3), (1+2+3), (3+3), (1+1+4), (2+4), (1+5), (6)

Die Werte steigen danach schnell an (siehe Folge A000041 in OEIS):

• P(7) = 15
• P(8) = 22
• P(9) = 30
• P(10) = 42
• P(100) = 190.569.292
• P(200) = 3.972.999.029.388
• P(1000) = 24.061.467.864.032.622.473.692.149.727.991 ≈ 2,4 × 10³¹

Asymptotisches Verhalten

Für große Werte von $n$ gibt die Formel

$P(n)\sim {\frac {\exp \left(\pi {\sqrt {2n/3}}\right)}{4n{\sqrt {3}}}}$

einen guten Näherungswert für $P(n)$. Insbesondere bedeutet dies, dass die Anzahl der Dezimalstellen von $P(n)$ etwa proportional zur Quadratwurzel aus $n$ ist: P(100) hat 9 Stellen (${\sqrt {100}}=10$), P(1000) hat 32 Stellen (${\sqrt {1000}}\approx 31{,}6$).

$P(4n)$ hat etwa doppelt so viele Stellen wie $P(n)$.

Partitionen mit vorgegebenem kleinsten Summanden

Bei einer Abwandlung der Partitionsfunktion wird verlangt, dass der kleinste Summand in der Zahlpartition größer oder gleich $k$ ist. Die Anzahl solcher Partitionen wird als $p(k,n)$ notiert. Die „normale“ Partitionsfunktion ist somit $P(n)=p(1,n)$

Beispielwerte

Beispielwerte von p(k,n)

p(k,n)		k
		1	2	3	4	5	6	7	8	9	10
n	1	1
	2	2	1
	3	3	1	1
	4	5	2	1	1
	5	7	2	1	1	1
	6	11	4	2	1	1	1
	7	15	4	2	1	1	1	1
	8	22	7	3	2	1	1	1	1
	9	30	8	4	2	1	1	1	1	1
	10	42	12	5	3	2	1	1	1	1	1

Einzelwerte

p(1, 4) = 5

p(2, 8) = 7

p(3, 12) = 9

p(4, 16) = 11

p(5, 20) = 13

p(6, 24) = 16

Rekursionsformel

Es gilt

$p(k,n)=1+\sum _{j=k}^{\lfloor {\frac {n}{2}}\rfloor }p(j,n-j);\;p(n,n)=1$

wobei $\lfloor n\rfloor$ die Gaußklammer ist.

Mit dieser Rekursionsformel lassen sich alle Werte von $p(k,n)$ und damit auch für $P(n)=p(1,n)$ berechnen. Man beachte aber, dass bei der Rekursionsformel für die Berechnung von $p(1,N)$ alle Werte von $p(k,n)$ für $1\leq k<n<N$ bekannt sein oder mit berechnet werden müssen.

Eigenschaften

$n$	$P(n)$	Kongruenzen
1	1
2	2
3	3
4	5	mod 5
5	7	mod 7
6	11	mod 11
7	15
8	22
9	30	mod 5
10	42
11	56
12	77	mod 7
13	101
14	135	mod 5
15	176
16	231
17	297	mod 11
18	385
19	490	mod 5 und 7
20	627

Es gilt

• $p(k,n)=0$, wenn $k>n$
• $p(k,n)=1$, wenn $k=n$
• $p(k,n)=p(k+1,n)+p(k,n-k)$ sonst

Kongruenzen

Ramanujan entdeckte bei seinen Studien eine Gesetzmäßigkeit. Beginnt man mit der 4 und springt um 5, so erhält man immer Vielfache der Sprungzahl 5 als Zerlegungszahlen. Beginnt man bei der 6 und springt um 11, so erhält man Vielfache von 11. Ramanujan entdeckte weitere derartige Beziehungen, auch Kongruenzen genannt, als er die Potenzen der Primzahlen 5, 7 und 11 sowie deren Produkte als Sprungzahlen untersuchte. Der amerikanische Zahlentheoretiker Ken Ono konnte zeigen, dass es für alle Primzahlen größer 3 Kongruenzen gibt. Ob dies für die beiden kleinsten Primzahlen, die 2 und 3, und deren Vielfache ebenso gilt, konnte Ono nicht nachweisen. Folgende Kongruenzen gehen auf Ramanujan zurück:

${\begin{aligned}P(5k+4)&\equiv 0\mod 5\\P(7k+5)&\equiv 0\mod 7\\P(11k+6)&\equiv 0\mod {11}\end{aligned}}$

A. O. L. Atkin fand folgende Kongruenz:

$P(17303k+237)\equiv 0\mod {13}$

Effiziente Berechnung von P(n)

Erzeugende Funktion

Eine einfache erzeugende Funktion für die Partitionsfunktion gewinnt man aus der Umkehrung von Eulers Funktion

$\sum _{n=0}^{\infty }P(n)x^{n}=\prod _{k=1}^{\infty }{\frac {1}{1-x^{k}}}$

man erhält

$f(x)={\frac {1}{\prod _{k=1}^{\infty }(1-x^{k})}}=1+1x+2x^{2}+3x^{3}+5x^{4}+...$

D.h. dass die Koeffizienten der Reihendarstellung von $f(x)$ den Werten von $P(n)$ entsprechen.

Formel für P(n)

Eine Möglichkeit zur direkten Berechnung liefert die aus der erzeugenden Funktion hergeleitete Formel

$P(n)={\frac {1}{\pi {\sqrt {2}}}}\sum _{k=1}^{\infty }A_{k}(n)\;{\sqrt {k}}\;{\frac {\mathrm {d} }{\mathrm {d} n}}\left({\frac {\sinh \left({\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}\right)}{\sqrt {n-{\frac {1}{24}}}}}\right)$

mit

$A_{k}(n)=\!\!\!\!\sum _{0\leq m<k \atop \operatorname {ggT} (m,k)=1}\!\!\!\!\exp \left\{{\frac {\pi i}{k}}\left[s(m,k)-2nm\right]\right\}.$

und

$s(m,k)=\sum _{j=1}^{k-1}j\left({\frac {mj}{k}}-\left\lfloor {\frac {mj}{k}}\right\rfloor -{\frac {1}{2}}\right)$

die Hans Rademacher, aufbauend auf Erkenntnissen von Ramanujan und Godfrey Harold Hardy, fand.

Eine algebraische, geschlossene Form von $P(n)$, die ohne unendliche Reihenentwicklung auskommt, wurde 2011 von Jan Hendrik Bruinier und Ken Ono veröffentlicht. Genauer gesagt geben Bruinier und Ono eine Funktion $Q$ an, so dass sich für jede natürliche Zahl $n$ eine endliche Anzahl algebraischer Zahlen $\alpha _{1},\alpha _{2},\ldots ,\alpha _{m}$ mit

$P(n)={\frac {1}{24n-1}}\left(Q(\alpha _{1})+Q(\alpha _{2})+\ldots +Q(\alpha _{m})\right)$

finden lassen. Darüber hinaus gilt, dass auch alle Werte $Q(\alpha _{i})$ algebraisch sind.

Dieses theoretische Ergebnis führt nur in Spezialfällen (z. B. über daraus ableitbare Kongruenzen) zu einer schnelleren Berechnung der Partitionsfunktion.

Mathematische Anwendungen

→ Hauptartikel: Partitionierungsproblem

zu Anwendungen in Technik und Informatik.

Konjugationsklassen der symmetrischen Gruppe

Die Anzahl der Konjugationsklassen in der symmetrischen Gruppe $S_{n}$ ist gleich dem Wert $P(n)$ der Partitionsfunktion, denn jede Konjugationsklasse ist eine Klasse von Permutationen mit einer bestimmten Struktur der Darstellung in disjunkter Zyklenschreibweise.

Beispiele;

• Die Permutation $(1,2,3)(5,7,8,9)$ gehört als Element der $S_{9}$ zu der Zahlpartition $1+1+3+4$ der Zahl 9, als Element der $S_{12}$ zur Zahlpartition $1+1+1+1+1+3+4$ von 12. Man beachte, dass Fixelemente der Permutation, die in der Zyklenschreibweise (als „Einerzyklen“) fast immer fortgelassen werden, in der Zahlpartition als Summanden 1 auftauchen. Jedes Element der $S_{12}$, das in der disjunkten Zyklenschreibweise aus einem Dreier- und einem Viererzyklus besteht, ist in $S_{12}$ zu dem oben genannten Element konjugiert, es gibt in diesem Fall ${\binom {12}{4}}\cdot {\binom {8}{3}}\cdot 3!\cdot 2!=332\,640$ solche Permutationen.
• Die Permutation $(1,2,3)(5,7,6)(10,11)$ gehört als Element der $S_{12}$ zur Zahlpartition $1+1+1+1+2+3+3$ von 12. Sie gehört in $S_{12}$ zu einer Konjugationsklasse, die ${\binom {12}{3}}\cdot {\binom {9}{3}}\cdot {\binom {6}{2}}\cdot {\frac {2!\cdot 2!}{2!}}=554\,400$ Permutationen enthält.

Zahlpartition und endliche Mengenpartition

Jede Äquivalenzrelation auf einer endlichen Menge $M$ mit $n$ Elementen bestimmt eine Mengenpartition von $M$. In der Kombinatorik wird ohne Einschränkung der Allgemeinheit $M=\{1,2,\ldots n\}$ angenommen. Zu jeder Zahlpartition von $n$ gehört eine nicht leere Menge von isomorphen Äquivalenzklasseneinteilungen der Menge $M$. Die Anzahl der Zahlpartitionen von $n$ ist daher kleiner gleich der Anzahl der Mengenpartitionen von $M$, für $n\geq 3$ echt kleiner:

Beispiele

$n$	0	1	2	3	4	5	6	7	8	9	10	11
Anzahl der Zahlpartitionen $P(n)$	1	1	2	3	5	7	11	15	22	30	42	56
Anzahl der Mengenpartitionen $B_{n}$	1	1	2	5	15	52	203	877	4140	21147	115975	678570

• Zu der Zahlpartion $3=2+1$ von 3 gehören die 3 Mengenpartitionen $\{\{1,2\},\{3\}\};\{\{1,3\},\{2\}\};\{\{2,3\},\{1\}\}$.
• Zu den Zahlpartition $5=3+2$ und $5=3+1+1$ von 5 gehören je ${\binom {5}{3}}=10$ Mengenpartitionen, zu den Zahlpartitionen $5=5$ und $5=1+1+1+1+1$ je genau eine Mengenpartion.

Endliche abelsche p-Gruppen und abelsche Gruppen

Ist $p$ eine positive Primzahl, dann ist für $n\in \mathbb {N}$ jede Gruppe mit der Gruppenordnung $p^{n}$ eine p-Gruppe. Die Anzahl der (Isomorphieklassen von) abelschen Gruppen mit $p^{n}$ Gruppenelementen ist – unabhängig von der Primzahl $p$ – gleich dem Wert $P(n)$ der Partitionsfunktion, denn jede solche Gruppe $G$ ist nach dem Hauptsatz über endlich erzeugte abelsche Gruppen isomorph zu einem direkten Produkt $G\cong \mathbb {Z} /p^{k_{1}}\mathbb {Z} \times \mathbb {Z} /p^{k_{2}}\mathbb {Z} \times \cdots \times \mathbb {Z} /p^{k_{r}}\mathbb {Z}$ mit $p^{n}=p^{k_{1}}\cdot p^{k_{2}}\cdot \cdots \cdot p^{k_{r}}$ und also $n=k_{1}+k_{2}+\cdots +k_{r}$. Da die Isomorphieklasse nicht von der Reihenfolge der Faktoren im direkten Produkt abhängt, entspricht jede Isomorphieklasse von abelschen Gruppen mit $p^{n}$ Elementen umkehrbar eindeutig einer Zahlpartition von $n$.

Zum Beispiel gibt es bis auf Isomorphie jeweils genau $P(5)=7$ abelsche Gruppen mit $32=2^{5},243=3^{5},3125=5^{5}$ Elementen.

Anwendungsbeispiele

1. Wie viele Isomorphietypen von abelschen Gruppen mit genau 70000 Elementen gibt es? Jede solche Gruppe ist, wieder nach dem Hauptsatz ein direktes Produkt ihrer abelschen p-Sylowgruppen zu den Primzahlen 2, 5 und 7. Es ist $70000=2^{4}\cdot 5^{4}\cdot 7^{1}$, also existieren $P(4)\cdot P(4)\cdot P(1)=5\cdot 5\cdot 1=25\,$ „wesentlich verschiedene“ abelsche Gruppen mit 70000 Elementen.
2. Wie viele Isomorphietypen von abelschen Gruppen mit 7200 Elementen gibt es, die ein Element der Ordnung 180 enthalten? Es ist $180=2^{2}\cdot 3^{2}\cdot 5^{1};7200=2^{5}\cdot 3^{2}\cdot 5^{2}$. Von den abelschen 2-Gruppen und 3-Gruppen kommen nur solche in Betracht, die zu einer Partition von 5 bzw. 2 gehören, die einen Summanden größer oder gleich 2 enthält, damit fällt jeweils eine Zahlpartition (Summe von Einsen) weg. Es gibt also $(P(5)-1)\cdot (P(2)-1)\cdot P(2)=6\cdot 1\cdot 2=12$ solche Gruppen.
3. Ist nun zusätzlich zu den Informationen des vorigen Beispiels bekannt, dass kein Element eine größere Ordnung als 180 hat, so kommen nur noch 2 Arten von 2-Sylowgruppen $(5=2+2+1;5=2+1+1+1)$ und eine Art 5-Sylowgruppe $(2=1+1)$ in Betracht und es gibt genau 2 Isomorphietypen von Gruppen mit diesen Eigenschaften.

Anzahlfunktion von Isomorphietypen endlicher abelscher Gruppen

Der Hauptsatz über die endlich erzeugten abelschen Gruppen erlaubt es, die Anzahl $a(n)$ der Isomorphietypen endlicher abelscher Gruppen mit $n$ Elementen durch die Partitionsfunktion $P$ auszudrücken:

• Zu jeder natürlichen Zahl $n\in \mathbb {N}$ mit der Primfaktorzerlegung $n={p_{1}}^{r_{1}}\cdot {p_{2}}^{r_{2}}\cdots {p_{k}}^{r_{k}}$ existieren genau $a(n)=P(r_{1})\cdot P(r_{2})\cdots P(r_{k})$ Isomorphietypen von abelschen Gruppen mit $n$ Elementen.
• Die Folge $a(n)$ ist Folge A000688 in OEIS, sie ist eine multiplikative zahlentheoretische Funktion von $n$ und als solche durch ihre Werte für Primzahlpotenzen vollständig bestimmt.
• Die der Anzahlfunktion $a(n)$ zugeordnete (formale) Dirichletreihe $A(s)$ ist

$A(s)=\sum _{n=1}^{\infty }{\frac {a(n)}{n^{s}}},\,$ mit $s=\sigma +it\in \mathbb {C} ,\,$ ihr Eulerprodukt lautet $A(s)=\prod _{p\ {\mathrm {prim} }}\sum _{r=0}^{\infty }{\frac {P(r)}{p^{rs}}}.$

• Die Anzahlfunktion $a(n)$ gibt zugleich die Anzahl der durch die Teilbarkeitsrelation geordneten Ketten $t_{j}\in \mathbb {N} \setminus \{0,1\}:\;t_{1}|t_{2}|\cdots |t_{r}$ an, deren Produkt gleich $n$ ist $(t_{1}\cdot t_{2}\cdot \cdots t_{r}=n).$

Siehe auch

• Kombinatorik
• Pentagonalzahlensatz

Literatur

• Jacobus Hendricus van Lint, R. M. Wilson: A Course in Combinatorics. 2. Auflage. Cambridge University Press, Cambridge 2001, ISBN 0-521-80340-3. 
• John Edensor Littlewood: A Mathematician's Miscellany. Eine Entdeckungsreise. Methuen, London 1953, ISBN 3-540-42386-9, 10.7 Zahlpartitionen (Volltext (Englisch) in verschiedenen Dateiformaten [abgerufen am 15. Februar 2012] Littlewood erzählt in diesem Buch unter anderem über seine Zusammenarbeit mit Ramanujan und wie sie das Problem Approximation der Partitionsfunktion 1918 gelöst haben.). 
• Jiří Matoušek, Jaroslav Nešetřil: Diskrete Mathematik. Eine Entdeckungsreise. Springer, Berlin/Heidelberg/New York/... 2002, ISBN 3-540-42386-9, 10.7 Zahlpartitionen (Inhaltsverzeichnis [abgerufen am 8. Februar 2012] englisch: Invitation to Discrete Mathematics. Übersetzt von Hans Mielke, Lehrbuch, das wenig Vorkenntnisse – gehobene Schulmathematik bis 2. Semester Mathematikstudium – voraussetzt). 

Zu den Anwendungen in der Gruppentheorie

• Thomas W. Hungerford: Algebra. In: Graduate texts in mathematics. 8. korrigierte Auflage. Nr. 73. Springer, New York/Berlin/Singapore/Tokyo/Heidelberg/Barcelona/Budapest/Hong Kong/London/Milan/Paris/Santa Clara 1996, ISBN 3-540-90518-9, I. Groups, II. The Structure of Groups, S. 35–82 (Inhaltsverzeichnis [abgerufen am 15. Februar 2012]).  Download as PDF (8MB)

Weblinks

• Eric W. Weisstein: Partition Function P. In: MathWorld (englisch). Partitionsfunktion $P(n)$.
• Eric W. Weisstein: Partition Function Q. In: MathWorld (englisch). Partitionsfunktion $Q(n)$.
• Das Computeralgebraprogramm Maple enthält im Paket combinat die Funktion partition(n), die alle Zahlpartitionen der endlichen Mengen $\{1,2,\ldots n\}$ erzeugt und die Funktion numbpart(n), die den Wert $P(n)$ der Partitionsfunktion berechnet.

Einzelnachweise