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. Es gibt eine Reihe von Funktionen, bei denen an die Summanden zusätzliche Bedingungen gestellt werden, so z. B. dass jeder Summand nur einmal vorkommen darf.

Die Partitionsfunktion P(n), manchmal auch p(n) (Folge A000041 in OEIS) ist die einfachstmögliche Zerlegungsfunktion.

Beispielwerte

Beispielwerte von p(n) und zugehörige Partitionen

n	p(n)	Partitionen
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).

p(k,n)

Dies ist eine Abwandlung der Partitionsfunktion, in der verlangt wird, dass der kleinste Summand größergleich k ist. Die "normale" Partitionsfunktion ist somit p(n) = p(1,n)

Beispielwerte

p(1, 4) = 5

p(2, 8) = 7

p(3, 12) = 9

p(4, 16) = 11

p(5, 20) = 13

p(6, 24) = 16

z. B.

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

Berechnung von p(n)

Eine erzeugende Funktion für p(n) ist:

$\begin{align} f(x) &=\sum_{n=0}^\infty p(n)\, x^n = 1 + 1 x + 2 x^2 + 3 x^3 + 5 x^4 + \cdots\\ &=\frac{1}{\prod_{k=1}^{\infty} (1-x^k)}. \end{align}$

Eine direkte Berechnung liefert die 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\le m < k \atop \operatorname{ggT} (m,k)=1}\!\!\!\!\exp \left\{ \frac{\pi i}{k} \left[ s(m,k) - 2 nm \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.^[1][2] Genauer gesagt geben Bruinier und Ono eine Funktion P(n) 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( P(\alpha_1) + P(\alpha_2) + \ldots + P(\alpha_m) \right)$

finden lassen. Darüber hinaus gilt, dass auch alle Werte P(α_i) algebraisch sind.

Eigenschaften

$1+\sum_{k=1}^{\lfloor\frac{n}{2}\rfloor} p(k,n-k) = p(n)$

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

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

Folgende Kongruenzen gehen auf Ramanujan zurück:

$\begin{align} p(5k+4)&\equiv0 \mod 5\\ p(7k+5)&\equiv0 \mod 7\\ p(11k+6)&\equiv0 \mod {11} \end{align}$

A. O. L. Atkin fand folgende Kongruenz:

$p(17303k+237)\equiv0 \mod {13}$

Siehe auch

• Partition (Mengenlehre)
• Kombinatorik
• Pentagonalzahlensatz
• Der englische Begriff partition function wird in der Physik mit Zustandssumme übersetzt.

Weblinks

• http://mathworld.wolfram.com/PartitionFunctionP.html
• http://mathworld.wolfram.com/PartitionFunctionQ.html

Einzelnachweise

1. ↑ J. H. Bruinier, K. Ono: An algebraic formula for the partition function, 2011.
2. ↑ sueddeutsche.de: Eulers Erbe -- Mathematiker feiern Entdeckung in der Zahlentheorie , bezogen am 29. Januar 2011.