Partitionsfunktion

aus Wikipedia, der freien Enzyklopädie

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.

Inhaltsverzeichnis

1 Beispielwerte
2 P(k,n)
- 2.1 Beispielwerte
- 2.2 Eigenschaften, Berechnung
3 Berechnung von P(n)
4 Eigenschaften
- 4.1 Kongruenzen
5 Siehe auch
6 Weblinks

[Bearbeiten] Beispielwerte

P(0) = 1 ({})
P(1) = 1 ({1})
P(2) = 2 ({1,1}, {2})
P(3) = 3 ({1,1,1},{1,2},{3})
P(4) = 5 ({1,1,1,1},{1,1,2}, {2,2}, {1,3}, {4})
P(5) = 7
P(6) = 11
P(7) = 15
P(8) = 22
...

Die Werte von P(n) gehen für n gegen ∞ ziemlich schnell gegen unendlich (vgl. obige Abb. in halblogarithmischer Darstellung). P(100) ist schon 190.569.292, p(1000) = 24.061.467.864.032.622.473.692.149.727.991 ≈ 2,4 × $1031$ .

Eine thermodynamische Anwendung der Partitionsfunktion(en) findet sich in der Zustandssumme.

[Bearbeiten] 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)$

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

		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

[Bearbeiten] Eigenschaften, Berechnung

$1+\sum_{k=1}^{[\frac{n}{2}]} p(k,n-k) = p(n).$

wobei [n] die Gaußklammer ist.

Es ist

p(k, n) = 0 wenn k > n

p(k, n) = 1 wenn k = n

[Bearbeiten] Berechnung von P(n)

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

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

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

Eine direkte Berechnung liefert die Formel

$p(n)=\frac{1}{\pi \sqrt{2}} \sum_{k=1}^\infty A_k(n)\; \sqrt{k} \; \frac{d}{dn} \left( \frac {\sinh \left( \frac{\pi}{k} \sqrt{\frac{2}{3}\left(n-\frac{1}{24}\right)}\right) } {\sqrt{n-\frac{1}{24}}}\right)$