Partitionsfunktion

Die Partitionsfunktionen geben die Anzahl der Möglichkeiten an, positive, ganze Zahlen in positive, ganze Summanden zu zerlegen. Üblicherweise betrachtet man die Zerlegungen ohne Berücksichtigung der Reihenfolge. Jede solche Zerlegung wird in der Kombinatorik als (ungeordnete) Zahlpartition^[2] oder manchmal kurz Partition^[2] 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 {\displaystyle n} ) wird als P ( n ) {\displaystyle P(n)} , manchmal auch als p ( n ) {\displaystyle 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 ) {\displaystyle Q(n)} oder q ( n ) {\displaystyle q(n)} notiert und ist Folge A000009 in OEIS.^[3]

Mit einer aus der Partitionsfunktion P ( n ) {\displaystyle P(n)} abgeleiteten zahlentheoretischen Funktion kann die Anzahl der Isomorphietypen für die endlichen abelschen Gruppen angegeben werden.

Eine Partition ist eine (endliche oder unendliche) Folge κ = ( k 1 , k 2 , … , k p , … ) {\displaystyle \kappa =(k_{1},k_{2},\dots ,k_{p},\dots )} bestehend aus nicht-negativen ganzen Zahlen

k 1 ≥ k 2 ≥ ⋯ ≥ k p ≥ ⋯ ≥ 0. {\displaystyle k_{1}\geq k_{2}\geq \cdots \geq k_{p}\geq \cdots \geq 0.}

Die Zahl | κ | = k 1 + k 2 + ⋯ + k p + ⋯ {\displaystyle |\kappa |=k_{1}+k_{2}+\cdots +k_{p}+\cdots } nennt man Gewicht. Die Folgenglieder, welche nicht Null sind k i ≠ 0 {\displaystyle k_{i}\neq 0} , nennt man Teile von κ {\displaystyle \kappa } und die Anzahl der Teile l ( κ ) {\displaystyle l(\kappa )} nennt man Länge der Partition. Partitionen, welche die gleichen Teile haben, werden wir miteinander identifizieren, das heißt

κ 1 = ( 2 , 1 , 0 , 0 , … ) , κ 2 = ( 2 , 1 , 0 ) , κ 3 = ( 2 , 1 ) , {\displaystyle \kappa _{1}=(2,1,0,0,\dots ),\quad \kappa _{2}=(2,1,0),\quad \kappa _{3}=(2,1),\quad }

beschreiben dieselbe Partition mit Länge l ( κ 1 ) = l ( κ 2 ) = l ( κ 3 ) = 2 {\displaystyle l(\kappa _{1})=l(\kappa _{2})=l(\kappa _{3})=2} .

Wenn n = | κ | {\displaystyle n=|\kappa |} gilt, dann ist κ {\displaystyle \kappa } eine Partition von n {\displaystyle n} .^[4]

Beispielwerte von P(n) und zugehörige Zahlpartitionen

n	P(n)	Zahlpartitionen
0	1	() leere Partition/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 ( 45 ) = 89 134 P ( 8 ) = 22 P ( 100 ) = 190 569 292 P ( 9 ) = 30 P ( 200 ) ≈ 3,973 ⋅ 10 12 P ( 10 ) = 42 P ( 1000 ) ≈ 2,406 ⋅ 10 31 {\displaystyle {\begin{array}{lcr|lcr|lcr}P(7)&=&15&P(45)&=&89\,134\\P(8)&=&22&P(100)&=&190\,569\,292&\\P(9)&=&30&P(200)&\approx &3{,}973\cdot 10^{12}\\P(10)&=&42&P(1000)&\approx &2{,}406\cdot 10^{31}\end{array}}}

Beispielwerte von P(n,k)

P(n,k)		k
		1	2	3	4	5	6	7	8	9	10
n	1	1
	2	1	1
	3	1	1	1
	4	1	2	1	1
	5	1	2	2	1	1
	6	1	3	3	2	1	1
	7	1	3	4	3	2	1	1
	8	1	4	5	5	3	2	1	1
	9	1	4	7	6	5	3	2	1	1
	10	1	5	8	9	7	5	3	2	1	1

Bezeichnet P ( n , k ) {\displaystyle P(n,k)} die Anzahl der Möglichkeiten, die positive, ganze Zahl n {\displaystyle n} in genau k {\displaystyle k} positive, ganze Summanden zu zerlegen, dann gilt

P ( n ) = ∑ i = 1 n P ( n , i ) {\displaystyle P(n)=\sum _{i=1}^{n}P(n,i)} ,

wobei sich die Zahlen P ( n , k ) {\displaystyle P(n,k)} rekursiv über P ( n , 1 ) = 1 {\displaystyle P(n,1)=1} und P ( n , n ) = 1 {\displaystyle P(n,n)=1} sowie

P ( n + k , k ) = ∑ j = 1 k P ( n , j ) {\displaystyle P(n+k,k)=\sum _{j=1}^{k}P(n,j)}

oder direkt durch

P ( n , k ) = P ( n − k , k ) + P ( n − 1 , k − 1 ) {\displaystyle P(n,k)=P(n-k,k)+P(n-1,k-1)}

ermitteln lassen.^[5][6]

Relativer Fehler der Approximationsfunktion

n {\displaystyle n}	5	10	100	250	500
E ( n ) − P ( n ) P ( n ) {\displaystyle {\frac {E(n)-P(n)}{P(n)}}} in %	27,7	14,5	4,57	2,86	2,01

Für große Werte von n {\displaystyle n} gibt die Formel von Godfrey Harold Hardy und S. Ramanujan^[2][7]

P ( n ) ∼ E ( n ) = exp ⁡ ( π 2 n / 3 ) 4 n 3 {\displaystyle P(n)\sim E(n)={\frac {\exp \left(\pi {\sqrt {2n/3}}\right)}{4n{\sqrt {3}}}}}

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

P ( 4 n ) {\displaystyle P(4n)} hat etwa doppelt so viele Stellen wie P ( n ) {\displaystyle P(n)} .

Deswegen gilt dieser Grenzwert des Quotienten sukzessiver Folgenglieder:

lim n → ∞ P ( n + 1 ) P ( n ) = 1 {\displaystyle \lim _{n\rightarrow \infty }{\frac {P(n+1)}{P(n)}}=1}

Eine einfache erzeugende Funktion für die Partitionsfunktion gewinnt man aus der multiplikativ Inversen von Eulers Funktion:

∑ n = 0 ∞ P ( n ) x n = ∏ k = 1 ∞ [ ∑ n = 0 ∞ x k n ] = ∏ k = 1 ∞ 1 1 − x k = ( x ; x ) ∞ − 1 = [ ψ R ( x 2 ) ϑ 00 ( x ) ϑ 01 ( x ) 4 ] − 1 / 6 = {\displaystyle \sum _{n=0}^{\infty }P(n)x^{n}=\prod _{k=1}^{\infty }{\biggl [}\sum _{n=0}^{\infty }x^{kn}{\biggr ]}=\prod _{k=1}^{\infty }{\frac {1}{1-x^{k}}}=(x;x)_{\infty }^{-1}={\bigl [}\psi _{R}(x^{2})\vartheta _{00}(x)\vartheta _{01}(x)^{4}{\bigr ]}^{-1/6}=}

= 2 6 x 1 / 24 ϑ 10 ( x ) − 1 / 6 ϑ 00 ( x ) − 1 / 6 ϑ 01 ( x ) − 2 / 3 = 3 x 1 / 24 ϑ 10 ( 1 6 π ; x 1 / 6 ) − 1 {\displaystyle ={\sqrt[{6}]{2}}\,x^{1/24}\vartheta _{10}(x)^{-1/6}\vartheta _{00}(x)^{-1/6}\vartheta _{01}(x)^{-2/3}={\sqrt {3}}\,x^{1/24}\vartheta _{10}({\tfrac {1}{6}}\pi ;x^{1/6})^{-1}}

Dabei wird mit dem Funktionskürzel ψ R {\displaystyle \psi _{R}} die Ramanujansche Psifunktion zum Ausdruck gebracht. Der runde Klammerausdruck mit dem Unendlichkeitsindex stellt das Pochhammer-Symbol und ϑ₁₀, ϑ₀₀ und ϑ₀₁ stellen die drei Thetafunktionen dar. Für das Intervall −1 ≤ x < 1 gelten alle Stellen in der ersten Zeile der gezeigten Gleichungskette. Mit dem Übergang von der zweiten Stelle zur dritten Stelle wird die Identität der geometrischen Reihe dargestellt. Die restlichen gezeigten Elemente der Gleichungskette gehen unter anderem aus dem Werk Evolutio producti infiniti in seriem simplicem von Leonhard Euler, aus dem Werk Modular Equations and Approximations to π von Srinivasa Ramanujan und aus den Werken von Richard Dedekind hervor.

Man erhält diese Reihe:

f ( x ) = ( x ; x ) ∞ − 1 = 1 ∏ k = 1 ∞ ( 1 − x k ) = 1 + 1 x + 2 x 2 + 3 x 3 + 5 x 4 + . . . {\displaystyle f(x)=(x;x)_{\infty }^{-1}={\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 ) {\displaystyle f(x)} den Werten von P ( n ) {\displaystyle P(n)} entsprechen.

Die Koeffizienten c ( n ) {\displaystyle c(n)} von Eulers Funktion

∏ k = 1 ∞ ( 1 − x k ) = ∑ m = − ∞ ∞ ( − 1 ) m ⋅ x m ( 3 m − 1 ) 2 = ∑ n = 0 ∞ c ( n ) ⋅ x n {\displaystyle \prod _{k=1}^{\infty }(1-x^{k})\;=\sum _{m=-\infty }^{\infty }(-1)^{m}\cdot x^{\frac {m(3m-1)}{2}}=\sum _{n=0}^{\infty }c(n)\cdot x^{n}}

lassen sich mit dem Pentagonalzahlensatz von Leonhard Euler einfach explizit berechnen. Die Folge c ( n ) {\displaystyle c(n)} ist Folge A010815 in OEIS und es gilt stets c ( n ) ∈ { − 1 , 0 , 1 } . {\displaystyle c(n)\in \{-1,0,1\}.}

Aus der Tatsache, dass Eulers Funktion multiplikativ invers zur erzeugenden Funktion der Partitionsfunktion ist, folgt, dass für die diskrete Faltung c ∗ P {\displaystyle c\ast P} und n ∈ N 0 {\displaystyle n\in \mathbb {N} _{0}} gilt

( c ∗ P ) ( n ) = ∑ r ∈ Z c ( r ) ⋅ P ( n − r ) = ∑ r = 0 n P ( r ) ⋅ c ( n − r ) = { 1 ( n = 0 ) 0 ( n ≠ 0 ) . {\displaystyle (c\ast P)(n)=\sum _{r\in \mathbb {Z} }c(r)\cdot P(n-r)=\sum _{r=0}^{n}P(r)\cdot c(n-r)={\begin{cases}1\;(n=0)\\0\;(n\neq 0).\end{cases}}}

Die Summation muss nur über r ∈ { 0 , 1 , … n } {\displaystyle r\in \{0,1,\ldots n\}} erstreckt werden, da beide Folgen als Koeffizientenfolgen ihrer jeweiligen Funktion an negativen Stellen gleich Null sind.

Aus der im vorigen Unterabschnitt angegebenen Faltungsbeziehung zu den Koeffizienten c ( n ) {\displaystyle c(n)} folgt für n ∈ N ∖ { 0 } {\displaystyle n\in \mathbb {N} \setminus \{0\}} die Rekursionsformel

P ( n ) = − ∑ r = 1 n c ( r ) ⋅ P ( n − r ) = P ( n − 1 ) + P ( n − 2 ) − P ( n − 5 ) − P ( n − 7 ) + ⋯ {\displaystyle P(n)=-\sum _{r=1}^{n}c(r)\cdot P(n-r)=P(n-1)+P(n-2)-P(n-5)-P(n-7)+\cdots }

für die Partitionsfunktion.

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

P ( n ) = 1 π 2 ∑ k = 1 ∞ A k ( n ) k d d n { sinh ⁡ [ π k 2 3 ( n − 1 24 ) ] n − 1 24 } {\displaystyle 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 {\bigl [}{\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}{\bigl (}n-{\frac {1}{24}}{\bigr )}}}{\bigr ]}}{\sqrt {n-{\frac {1}{24}}}}}\right\}}

mit

A k ( n ) = ∑ 0 ≤ m < k ggT ⁡ ( m , k ) = 1 exp ⁡ { π i k [ s ( m , k ) − 2 n m ] } . {\displaystyle 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 ) = ∑ j = 1 k − 1 j ( m j k − ⌊ m j k ⌋ − 1 2 ) {\displaystyle 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 S. Ramanujan und Godfrey Harold Hardy, fand.

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

P ( n ) = 1 24 n − 1 ( Q ( α 1 ) + Q ( α 2 ) + … + Q ( α m ) ) {\displaystyle 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 ( α i ) {\displaystyle 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.

n {\displaystyle n}	P ( n ) {\displaystyle 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

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:

P ( 5 k + 4 ) ≡ 0 mod 5 P ( 7 k + 5 ) ≡ 0 mod 7 P ( 11 k + 6 ) ≡ 0 mod 11 {\displaystyle {\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 ( 17303 k + 237 ) ≡ 0 mod 13 {\displaystyle P(17303k+237)\equiv 0\mod {13}}

Im Artikel Young-Tableau wird ein ähnlicher Diagrammtyp ausführlich beschrieben, der wie die hier beschriebenen Ferrers-Diagramme eine Partition eindeutig bestimmt und vor allem in der Darstellungstheorie verwendet wird.

Die Zahlpartition 6 + 4 + 3 + 1 = 14 {\displaystyle 6+4+3+1=14} kann durch folgendes Diagramm, das als Ferrers-Diagramm bezeichnet wird, dargestellt werden. Diese Diagramme wurden zu Ehren von Norman Macleod Ferrers benannt.^[10]

6 + 4 + 3 + 1

Die 14 Kreise werden in 4 Spalten für die 4 Summanden der Partition aufgereiht, wobei die Spalten von links nach rechts nie höher werden. Es wird auch häufig die umgekehrte Konvention verwendet, bei der die Säulen von Kreisen auf der Grundlinie stehen und von links nach rechts nie niedriger werden. Die 5 Partitionen von 4 sind nachfolgend als Ferrers-Diagramme dargestellt:

4	=	3 + 1	=	2 + 2	=	2 + 1 + 1	=	1 + 1 + 1 + 1

Wenn wir das Diagramm der Partition 6 + 4 + 3 + 1 = 14 {\displaystyle 6+4+3+1=14} an seiner Hauptdiagonale spiegeln, erhalten wir eine andere Partition von 14:

	↔
6 + 4 + 3 + 1	=	4 + 3 + 3 + 2 + 1 + 1

Indem wir so Reihen in Spalten verwandeln, erhalten wir die Partition 4 + 3 + 3 + 2 + 1 + 1 = 14 {\displaystyle 4+3+3+2+1+1=14} . Sie heißt die zu 6 + 4 + 3 + 1 = 14 {\displaystyle 6+4+3+1=14} konjugierte Partition.^[11] Unter den Partitionen von 4 sind 1 + 1 + 1 + 1 = 4 {\displaystyle 1+1+1+1=4} und 4 = 4 {\displaystyle 4=4} ; 3 + 1 {\displaystyle 3+1} und 2 + 1 + 1 {\displaystyle 2+1+1} jeweils konjugiert zueinander. Besonders interessant sind Partitionen wie 3 + 2 + 1 = 6 {\displaystyle 3+2+1=6} , die zu sich selbst konjugiert sind, deren Ferrers-Diagramm also achsensymmetrisch zu seiner Hauptdiagonalen ist.

• Die Anzahl der zu sich selbst konjugierten Partitionen von n {\displaystyle n} ist gleich der Anzahl der Partitionen von n {\displaystyle n} in verschiedene, ungerade Summanden.

Beweisidee: Die entscheidende Beobachtung ist, dass jede Spalte im Ferrers-Diagramm, die eine ungerade Anzahl von Kreisen enthält, in der Mitte „gefaltet“ werden kann und so einen Teil eines symmetrischen Diagramms ergibt:

↔

Daraus gewinnt man, wie im folgenden Beispiel gezeigt, eine bijektive Abbildung der Partitionen mit verschiedenen, ungeraden Summanden auf die Partitionen, die zu sich selbst konjugiert sind:

	↔
9 + 7 + 3	=	5 + 5 + 4 + 3 + 2

Mit ähnlichen Methoden können zum Beispiel die folgenden Aussagen bewiesen werden: Die Anzahl der Partitionen von n {\displaystyle n} mit höchstens k {\displaystyle k} Summanden ist gleich

1. der Anzahl der Partitionen von n {\displaystyle n} , bei denen kein Summand größer als k {\displaystyle k} ist.
2. der Anzahl der Partitionen von n + k {\displaystyle n+k} mit genau k {\displaystyle k} Summanden.

Die Ferrers-Diagramme sind ein intuitives Hilfsmittel, mit denen sich Zusammenhänge zwischen ungeordneten Partitionen anschaulich erkennen und nachvollziehen lassen. Für die Erzeugung mit Computern und kompakte Speicherung sind sie ungeeignet, daher spielen auch „formalisierte“ Repräsentationen für diese Diagramme eine wichtige Rolle:

1. Eine Zahlpartition von n ∈ N {\displaystyle n\in \mathbb {N} } („Diagramm der Ordnung n {\displaystyle n} “) ist ein C {\displaystyle C} -Tupel („Anzahl der Spalten=Columns“) π = ( i k ) k = 1 C ∈ ( N ∖ { 0 } ) C {\displaystyle \pi =\operatorname {(i_{k})} _{k=1}^{C}\in \left(\mathbb {N} \setminus \{0\}\right)^{C}} mit der Eigenschaft ∑ k = 1 C i k = n {\displaystyle \sum \nolimits _{k=1}^{C}i_{k}=n} , C {\displaystyle C} heißt ihre Spaltenzahl. (Um hier auch die „leere“ Partition ( ) = ( ) k = 1 0 {\displaystyle ()=\operatorname {()} _{k=1}^{0}} mitzuerfassen, muss man für C = 0 {\displaystyle C=0} setzen ( N ∖ { 0 } ) 0 := { ( ) } {\displaystyle \left(\mathbb {N} \setminus \{0\}\right)^{0}:=\{()\}} , es ist dann die leere Summe und ergibt immer 0.)
2. Die Zahl R = R ( π ) = max ( 0 , max { i k : 1 ≤ k ≤ C } ) {\displaystyle R=R(\pi )=\max(0,\max\{i_{k}:1\leq k\leq C\})} heißt die Zeilenzahl (=„Rows“) von π = ( i k ) k = 1 C . {\displaystyle \pi =\operatorname {(i_{k})} _{k=1}^{C}.}
3. Eine Zahlpartition π = ( i k ) k = 1 C {\displaystyle \pi =\operatorname {(i_{k})} _{k=1}^{C}} heißt „gültig“, wenn für 1 ≤ k < C {\displaystyle 1\leq k<C} stets i k ≥ i k + 1 {\displaystyle i_{k}\geq i_{k+1}} gilt, für gültige Partitionen mit C > 0 {\displaystyle C>0} ist R ( π ) = i 1 {\displaystyle R(\pi )=i_{1}} .
4. Eine Zahlpartition π = ( i k ) k = 1 C {\displaystyle \pi =\operatorname {(i_{k})} _{k=1}^{C}} heißt „strikt“, wenn für 1 ≤ k < C {\displaystyle 1\leq k<C} stets i k > i k + 1 {\displaystyle i_{k}>i_{k+1}} gilt. Strikte Partitionen sind immer gültig.
5. Die konjugierte Partition einer gültigen Partition π = ( i k ) k = 1 C {\displaystyle \pi =\operatorname {(i_{k})} _{k=1}^{C}} ist definiert durch π ¯ = ( max { k : i k + 1 - r > 0 ∧ 1 ≤ k ≤ C } ) r = 1 R ( π ) {\displaystyle {\overline {\pi }}=\operatorname {\left(\max\{k:\,{i_{k}}+1-r>0\land 1\leq k\leq C\}\right)} _{r=1}^{R(\pi )}} . Sie ist gültig.

Alternativ und näher an der grafischen Darstellung der Ferrers-Diagramme kann man jede Partition als R × C {\displaystyle R\times C} -Matrix ( a j k ) {\displaystyle (a_{jk})} mit Einträgen aus { 0 , 1 } {\displaystyle \{0,1\}} darstellen, wobei a j k = 1 {\displaystyle a_{jk}=1} bedeutet, dass sich im Ferrers-Diagramm in der Reihe j {\displaystyle j} in Spalte k {\displaystyle k} ein Kreis befindet, a j k = 0 {\displaystyle a_{jk}=0} , dass dort kein Kreis ist. Die Konjugierte einer Partition hat dann als Matrix die transponierte Matrix der ursprünglichen Partition.

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

Beispielwerte für p(k,n)

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

Zu den Werten von p ( k , n ) {\displaystyle p(k,n)} für kleine Zahlen siehe auch die zweite Tabelle rechts. Einzelwerte sind:

p ( 1 , 4 ) = 5 , p ( 2 , 8 ) = 7 , p ( 3 , 12 ) = 9 , p ( 4 , 16 ) = 11 , p ( 5 , 20 ) = 13 , p ( 6 , 24 ) = 16. {\displaystyle {\begin{alignedat}{4}p(1,4)&=5,&p(2,8)&=7,&p(3,12)&=9,\\p(4,16)&=11,\quad &p(5,20)&=13,\quad &p(6,24)&=16.\end{alignedat}}}

Es gilt

p ( n , n ) = 1 {\displaystyle p(n,n)=1}

und

p ( k , n ) = 1 + ∑ j = k ⌊ n 2 ⌋ p ( j , n − j ) {\displaystyle p(k,n)=1+\sum _{j=k}^{\left\lfloor {\frac {n}{2}}\right\rfloor }p(j,n-j)}

für k < n {\displaystyle k<n} , wobei ⌊ n ⌋ {\displaystyle \lfloor n\rfloor } die Gaußklammer ist. Mit dieser Rekursionsformel lassen sich alle Werte von p ( k , n ) {\displaystyle p(k,n)} und damit auch für P ( n ) = p ( 1 , n ) {\displaystyle P(n)=p(1,n)} berechnen. Man beachte aber, dass bei der Rekursionsformel für die Berechnung von p ( 1 , N ) {\displaystyle p(1,N)} alle Werte von p ( k , n ) {\displaystyle p(k,n)} für 1 < n < N {\displaystyle 1<n<N} und 1 ≤ k < ⌊ N 2 ⌋ {\displaystyle 1\leq k<\left\lfloor {\frac {N}{2}}\right\rfloor } bekannt sein oder mitberechnet werden müssen.

Betrachtet man die Summanden in einer Zahlpartition als geordnete Menge, berücksichtigt also die Reihenfolge in der Summe, dann spricht man von einer geordneten Zahlpartition. Hier werden die folgenden Anzahlfunktionen betrachtet, für die kein Formelzeichen allgemein verbreitet ist.

• g ( k , n ) {\displaystyle g(k,n)} ist die Anzahl der Darstellungen von n {\displaystyle n} als Summe von genau k {\displaystyle k} positiven ganzen Zahlen mit Berücksichtigung der Reihenfolge der Summanden, also die Anzahl der Lösungen ( i 1 , i 2 , … , i k ) ∈ ( N ∖ { 0 } ) k {\displaystyle (i_{1},i_{2},\ldots ,i_{k})\in \left(\mathbb {N} \setminus \{0\}\right)^{k}} der Gleichung i 1 + i 2 + ⋯ + i k = n . {\displaystyle i_{1}+i_{2}+\cdots +i_{k}=n.}
  • Es gilt g ( k , n ) = ( n − 1 k − 1 ) {\displaystyle g(k,n)={\binom {n-1}{k-1}}} .^[2]
  • Die Anzahl lässt sich geometrisch deuten als Zahl der Punkte mit positiven, ganzzahligen Koordinaten auf der Hyperebene mit der Gleichung x 1 + x 2 + ⋯ + x k = n {\displaystyle x_{1}+x_{2}+\cdots +x_{k}=n} im k {\displaystyle k} -dimensionalen reellen affinen Punktraum.
  • Die Folge g ( 1 , 1 ) , g ( 1 , 2 ) , g ( 2 , 2 ) , g ( 1 , 3 ) , g ( 2 , 3 ) , g ( 3 , 3 ) , g ( 1 , 4 ) , … {\displaystyle g(1,1),g(1,2),g(2,2),g(1,3),g(2,3),g(3,3),g(1,4),\ldots } ist die Folge der Zahlen im pascalschen Dreieck, den Reihen nach gelesen, Folge A007318 in OEIS.
• G ( n ) {\displaystyle G(n)} ist die Anzahl der Darstellungen von n {\displaystyle n} als Summe von höchstens n {\displaystyle n} positiven ganzen Zahlen mit Berücksichtigung der Reihenfolge der Summanden. Sie ist Folge A000079 in OEIS und es gilt^[2]
  • G ( n ) = ∑ j = 1 n g ( j , n ) {\displaystyle G(n)=\sum _{j=1}^{n}g(j,n)} ,
  • die Rekursionsformel G ( n ) = 1 + ∑ i 1 = 1 n − 1 G ( n − i 1 ) , n ≥ 1 {\displaystyle G(n)=1+\sum _{i_{1}=1}^{n-1}G(n-i_{1}),\,n\geq 1} und
  • G ( n ) = 2 n − 1 , n ≥ 1 {\displaystyle G(n)=2^{n-1},n\geq 1} , was sich leicht mit vollständiger Induktion aus der Rekursionsformel beweisen lässt.

Offenbar liefert die leicht zu berechnende Funktion G ( n ) {\displaystyle G(n)} eine (sehr grobe) obere Schranke für die Partitionsfunktion:^[2]

P ( n ) < G ( n ) = 2 n − 1 ,   n ≥ 3. {\displaystyle P(n)<G(n)=2^{n-1},\ n\geq 3.}

Die Zahlpartitionen von n {\displaystyle n} , die aus lauter ungeraden Summanden bestehen, lassen sich bijektiv abbilden auf die strikten Zahlpartitionen, das sind die Zahlpartitionen mit lauter unterschiedlichen Summanden. Diese Tatsache wurde bereits 1748 von Euler nachgewiesen.^[12] Sie ist ein Spezialfall des Satzes von Glaisher der nach James Whitbread Lee Glaisher benannt ist:^[13]

Damit verwandt ist die folgende Aussage, die nach Leonard James Rogers als Satz von Rogers benannt ist:^[13]

Die Aussage ist Teil der Rogers-Ramanujan-Identitäten.

zu Anwendungen in Technik und Informatik.

Die Anzahl der Konjugationsklassen in der symmetrischen Gruppe S n {\displaystyle S_{n}} ist gleich dem Wert P ( n ) {\displaystyle P(n)} der Partitionsfunktion, denn jede Konjugationsklasse entspricht genau einem Zykeltyp von Permutationen mit einer bestimmten Struktur der Darstellung in disjunkter Zyklenschreibweise.

Beispiele

• Die Permutation ( 1 , 2 , 3 ) ( 5 , 7 , 8 , 9 ) {\displaystyle (1,2,3)(5,7,8,9)} gehört als Element der S 9 {\displaystyle S_{9}} zu der Zahlpartition 1 + 1 + 3 + 4 {\displaystyle 1+1+3+4} der Zahl 9, als Element der S 12 {\displaystyle S_{12}} zur Zahlpartition 1 + 1 + 1 + 1 + 1 + 3 + 4 {\displaystyle 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 {\displaystyle S_{12}} , das in der disjunkten Zyklenschreibweise aus einem Dreier- und einem Viererzyklus besteht, ist in S 12 {\displaystyle S_{12}} zu dem oben genannten Element konjugiert, es gibt in diesem Fall ( 12 4 ) ⋅ ( 8 3 ) ⋅ 3 ! ⋅ 2 ! = 332 640 {\displaystyle {\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 ) {\displaystyle (1,2,3)(5,7,6)(10,11)} gehört als Element der S 12 {\displaystyle S_{12}} zur Zahlpartition 1 + 1 + 1 + 1 + 2 + 3 + 3 {\displaystyle 1+1+1+1+2+3+3} von 12. Sie gehört in S 12 {\displaystyle S_{12}} zu einer Konjugationsklasse, die ( 12 3 ) ⋅ ( 9 3 ) ⋅ ( 6 2 ) ⋅ 2 ! ⋅ 2 ! 2 ! = 554 400 {\displaystyle {\binom {12}{3}}\cdot {\binom {9}{3}}\cdot {\binom {6}{2}}\cdot {\frac {2!\cdot 2!}{2!}}=554\,400} Permutationen enthält.

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

Beispiele

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

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

Hierbei wird mit Bₙ die n-te Bellsche Zahl zum Ausdruck gebracht.

Ist p {\displaystyle p} eine positive Primzahl, dann ist für n ∈ N {\displaystyle n\in \mathbb {N} } jede Gruppe mit der Gruppenordnung p n {\displaystyle p^{n}} eine p-Gruppe. Die Anzahl der (Isomorphieklassen von) abelschen Gruppen mit p n {\displaystyle p^{n}} Gruppenelementen ist – unabhängig von der Primzahl p {\displaystyle p} – gleich dem Wert P ( n ) {\displaystyle P(n)} der Partitionsfunktion, denn jede solche Gruppe G {\displaystyle G} ist nach dem Hauptsatz über endlich erzeugte abelsche Gruppen isomorph zu einem direkten Produkt G ≅ Z / p k 1 Z × Z / p k 2 Z × ⋯ × Z / p k r Z {\displaystyle 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 ⋅ p k 2 ⋅ ⋯ ⋅ p k r {\displaystyle p^{n}=p^{k_{1}}\cdot p^{k_{2}}\cdot \cdots \cdot p^{k_{r}}} und also n = k 1 + k 2 + ⋯ + k r {\displaystyle 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 {\displaystyle p^{n}} Elementen umkehrbar eindeutig einer Zahlpartition von n {\displaystyle n} .

Zum Beispiel gibt es bis auf Isomorphie jeweils genau P ( 5 ) = 7 {\displaystyle P(5)=7} abelsche Gruppen mit 32 = 2 5 , 243 = 3 5 , 3125 = 5 5 {\displaystyle 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 ⋅ 5 4 ⋅ 7 1 {\displaystyle 70000=2^{4}\cdot 5^{4}\cdot 7^{1}} , also existieren P ( 4 ) ⋅ P ( 4 ) ⋅ P ( 1 ) = 5 ⋅ 5 ⋅ 1 = 25 {\displaystyle 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 ⋅ 3 2 ⋅ 5 1 ; 7200 = 2 5 ⋅ 3 2 ⋅ 5 2 {\displaystyle 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 ) ⋅ ( P ( 2 ) − 1 ) ⋅ P ( 2 ) = 6 ⋅ 1 ⋅ 2 = 12 {\displaystyle (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 ) {\displaystyle (5=2+2+1;5=2+1+1+1)} und eine Art 5-Sylowgruppe ( 2 = 1 + 1 ) {\displaystyle (2=1+1)} in Betracht und es gibt genau 2 Isomorphietypen von Gruppen mit diesen Eigenschaften.

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

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

A ( s ) = ∑ n = 1 ∞ a ( n ) n s , {\displaystyle A(s)=\sum _{n=1}^{\infty }{\frac {a(n)}{n^{s}}},\,} mit s = σ + i t ∈ C , {\displaystyle s=\sigma +it\in \mathbb {C} ,\,} ihr Eulerprodukt lautet A ( s ) = ∏ p   p r i m ∑ r = 0 ∞ P ( r ) p r s . {\displaystyle A(s)=\prod _{p\ {\mathrm {prim} }}\sum _{r=0}^{\infty }{\frac {P(r)}{p^{rs}}}.}

• Die Anzahlfunktion a ( n ) {\displaystyle a(n)} gibt für n ≥ 2 {\displaystyle n\geq 2} zugleich die Anzahl der durch die Teilbarkeitsrelation geordneten Ketten ( t 1 , t 2 , … , t r ) ∈ { ( N ∖ { 0 , 1 } ) r : t 1 | t 2 | ⋯ | t r } {\displaystyle (t_{1},t_{2},\ldots ,t_{r})\in \left\lbrace \left(\mathbb {N} \setminus \{0,1\}\right)^{r}:\;t_{1}|t_{2}|\cdots |t_{r}\right\rbrace } an, deren Produkt gleich n {\displaystyle n} ist ( t 1 ⋅ t 2 ⋅ ⋯ t r = n ) . {\displaystyle (t_{1}\cdot t_{2}\cdot \cdots t_{r}=n).}

Wenn jeder Summand nur einmal^[14] in der Partitionssumme vorkommen darf und somit kein Summand wiederholt in der Partitionssumme auftaucht, dann liegen die sogenannten strikten Partitionen vor. Die strikte Partitionsfolge Q(n) erfüllt somit für alle n ∈ ℕ₀ das Kriterium Q(n) ≤ P(n). Die gleiche Folge^[15] ergibt sich, wenn in der Partitionssumme nur ungerade Summanden^[16] auftauchen dürfen, aber diese auch mehrfach vorkommen dürfen.

Darstellungen der Partitionen:

Beispielwerte von Q(n) und zugehörige Zahlpartitionen

n	Q(n)	Zahlpartitionen ohne wiederholte Summanden	Zahlpartitionen mit nur ungeraden Summanden
0	1	() leere Partition/leere Summe	() leere Partition/leere Summe
1	1	(1)	(1)
2	1	(2)	(1+1)
3	2	(1+2), (3)	(1+1+1), (3)
4	2	(1+3), (4)	(1+1+1+1), (1+3)
5	3	(2+3), (1+4), (5)	(1+1+1+1+1), (1+1+3), (5)
6	4	(1+2+3), (2+4), (1+5), (6)	(1+1+1+1+1+1), (1+1+1+3), (3+3), (1+5)
7	5	(1+2+4), (3+4), (2+5), (1+6), (7)	(1+1+1+1+1+1+1), (1+1+1+1+3), (1+3+3), (1+1+5), (7)
8	6	(1+3+4), (1+2+5), (3+5), (2+6), (1+7), (8)	(1+1+1+1+1+1+1+1), (1+1+1+1+1+3), (1+1+3+3), (1+1+1+5), (3+5), (1+7)
9	8	(2+3+4), (1+3+5), (4+5), (1+2+6), (3+6), (2+7), (1+8), (9)	......
10	10	(1+2+3+4), (2+3+5), (1+4+5), (1+3+6), (4+6), (1+2+7), (3+7), (2+8), (1+9), (10)	......

Die zugehörige erzeugende Funktion basierend auf der Maclaurinschen Reihe mit den Zahlen Q(n) als Koeffizienten vor xⁿ lautet so:

∑ n = 0 ∞ Q ( n ) x n = ∏ m = 1 ∞ ( 1 + x m ) = 1 2 ( − 1 ; x ) ∞ = ( x ; x 2 ) ∞ − 1 = ψ R ( x 2 ) ϑ 00 ( x ) ϑ 01 ( x ) − 2 6 {\displaystyle \sum _{n=0}^{\infty }Q(n)x^{n}=\prod _{m=1}^{\infty }(1+x^{m})={\tfrac {1}{2}}(-1;x)_{\infty }=(x;x^{2})_{\infty }^{-1}={\sqrt[{6}]{\psi _{R}(x^{2})\vartheta _{00}(x)\vartheta _{01}(x)^{-2}}}}

Man erhält folgende erste Summanden:

( x ; x 2 ) ∞ − 1 = 1 ∏ k = 1 ∞ ( 1 − x 2 k − 1 ) = 1 + 1 x + 1 x 2 + 2 x 3 + 2 x 4 + 3 x 5 + 4 x 6 + 5 x 7 + 6 x 8 + 8 x 9 + 10 x 10 . . . {\displaystyle (x;x^{2})_{\infty }^{-1}={\frac {1}{\prod _{k=1}^{\infty }(1-x^{2k-1})}}=1+1x+1x^{2}+2x^{3}+2x^{4}+3x^{5}+4x^{6}+5x^{7}+6x^{8}+8x^{9}+10x^{10}...}

Wichtige Rechenhinweise über die Thetafunktionen und die Ramanujansche Psifunktion:

( x ; x ) ∞ ( x ; x 2 ) ∞ = ϑ 01 ( x ) {\displaystyle (x;x)_{\infty }(x;x^{2})_{\infty }=\vartheta _{01}(x)}

( x ; x ) ∞ 2 = ( x ; x 2 ) ∞ 4 ψ R ( x 2 ) ϑ 00 ( x ) {\displaystyle (x;x)_{\infty }^{2}=(x;x^{2})_{\infty }^{4}\psi _{R}(x^{2})\vartheta _{00}(x)}

16 x ψ R ( x 2 ) 4 = ϑ 00 ( x ) 4 − ϑ 01 ( x ) 4 {\displaystyle 16\,x\,\psi _{R}(x^{2})^{4}=\vartheta _{00}(x)^{4}-\vartheta _{01}(x)^{4}}

Alle drei hier abgebildeten Formeln gelten für den Definitionsbereich −1 < x < 1.

Über die Pochhammer-Produkte gilt weiter folgende Identität:

( x ; x ) ∞ − 1 = ( x 2 ; x 2 ) ∞ − 1 ( x ; x 2 ) ∞ − 1 {\displaystyle (x;x)_{\infty }^{-1}=(x^{2};x^{2})_{\infty }^{-1}(x;x^{2})_{\infty }^{-1}}

Daraus folgt diese Formel:

[ ∑ n = 0 ∞ P ( n ) x n ] = [ ∑ n = 0 ∞ P ( n ) x 2 n ] [ ∑ n = 0 ∞ Q ( n ) x n ] {\displaystyle {\biggl [}\sum _{n=0}^{\infty }P(n)x^{n}{\biggr ]}={\biggl [}\sum _{n=0}^{\infty }P(n)x^{2n}{\biggr ]}{\biggl [}\sum _{n=0}^{\infty }Q(n)x^{n}{\biggr ]}}

Und deswegen gelten auch jene zwei Formeln für die Synthese der Zahlenfolge P(n):

P ( 2 n ) = ∑ k = 0 n P ( n − k ) Q ( 2 k ) {\displaystyle P(2n)=\sum _{k=0}^{n}P(n-k)Q(2k)}

P ( 2 n + 1 ) = ∑ k = 0 n P ( n − k ) Q ( 2 k + 1 ) {\displaystyle P(2n+1)=\sum _{k=0}^{n}P(n-k)Q(2k+1)}

Im nun Folgenden werden zwei Beispiele akkurat ausgeführt:

P ( 8 ) = ∑ k = 0 4 P ( 4 − k ) Q ( 2 k ) = {\displaystyle P(8)=\sum _{k=0}^{4}P(4-k)Q(2k)=}

= P ( 4 ) Q ( 0 ) + P ( 3 ) Q ( 2 ) + P ( 2 ) Q ( 4 ) + P ( 1 ) Q ( 6 ) + P ( 0 ) Q ( 8 ) = {\displaystyle =P(4)Q(0)+P(3)Q(2)+P(2)Q(4)+P(1)Q(6)+P(0)Q(8)=}

= 5 × 1 + 3 × 1 + 2 × 2 + 1 × 4 + 1 × 6 = 22 {\displaystyle =5\times 1+3\times 1+2\times 2+1\times 4+1\times 6=22}

P ( 9 ) = ∑ k = 0 4 P ( 4 − k ) Q ( 2 k + 1 ) = {\displaystyle P(9)=\sum _{k=0}^{4}P(4-k)Q(2k+1)=}

= P ( 4 ) Q ( 1 ) + P ( 3 ) Q ( 3 ) + P ( 2 ) Q ( 5 ) + P ( 1 ) Q ( 7 ) + P ( 0 ) Q ( 9 ) = {\displaystyle =P(4)Q(1)+P(3)Q(3)+P(2)Q(5)+P(1)Q(7)+P(0)Q(9)=}

= 5 × 1 + 3 × 2 + 2 × 3 + 1 × 5 + 1 × 8 = 30 {\displaystyle =5\times 1+3\times 2+2\times 3+1\times 5+1\times 8=30}

Wenn zu einer gegebenen Zahl k alle Partitionen so aufgestellt werden, dass die Summandengröße niemals steigt, und bei jeder so beschaffenen Partition all diejenigen Summanden markiert werden dürfen, welche keinen gleich großen Summanden links von sich haben, dann wird die sich dadurch ergebende Anzahl der unterschiedlich markierten Partitionen in Abhängigkeit von k durch die Oberpartitionsfunktion P ¯ ( k ) {\displaystyle {\overline {P}}(k)} beschrieben. Diese Funktion kann auch Überpartitionsfunktion genannt werden und wird im englischen Sprachraum overpartition function genannt.

Im nun Folgenden werden die ersten Oberpartitionsfunktionswerte mit ihrer beschreibenden Darstellung tabellarisch aufgelistet:

n	P ¯ ( n ) {\displaystyle {\overline {P}}(n)}	Markierte Zahlpartitionen mit Markierungen nicht wiederholter Summanden
0	1	() leere Partition
1	2	(1), (1)
2	4	(2), (2), (1+1), (1+1)
3	8	(3), (3), (2+1), (2+1), (2+1), (2+1), (1+1+1), (1+1+1)
4	14	(4), (4), (3+1), (3+1), (3+1), (3+1), (2+2), (2+2), (2+1+1), (2+1+1), (2+1+1), (2+1+1), (1+1+1+1), (1+1+1+1)
5	24	(5), (5), (4+1), (4+1), (4+1), (4+1), (3+2), (3+2), (3+2), (3+2), (3+1+1), (3+1+1), (3+1+1), (3+1+1), (2+2+1), (2+2+1), (2+2+1), (2+2+1), (2+1+1+1), (2+1+1+1), (2+1+1+1), (2+1+1+1), (1+1+1+1+1), (1+1+1+1+1)

Die erzeugende Funktion der Oberpartitionszahlen P ¯ ( n ) {\displaystyle {\overline {P}}(n)} als Koeffizienten vor x n {\displaystyle x^{n}} ist der Kehrwert der Thetafunktion ϑ₀₁(x):

∑ n = 0 ∞ P ¯ ( n ) x n = ∏ k = 1 ∞ 1 + x k 1 − x k = ∏ k = 1 ∞ 1 − x 2 k ( 1 − x k ) 2 = ( x 2 ; x 2 ) ∞ ( x ; x ) ∞ 2 = 1 ( x ; x ) ∞ ( x ; x 2 ) ∞ = 1 ϑ 01 ( x ) {\displaystyle \sum _{n=0}^{\infty }{\overline {P}}(n)x^{n}=\prod _{k=1}^{\infty }{\frac {1+x^{k}}{1-x^{k}}}=\prod _{k=1}^{\infty }{\frac {1-x^{2k}}{(1-x^{k})^{2}}}={\frac {(x^{2};x^{2})_{\infty }}{(x;x)_{\infty }^{2}}}={\frac {1}{(x;x)_{\infty }(x;x^{2})_{\infty }}}={\frac {1}{\vartheta _{01}(x)}}}

Man erhält folgende erste Summanden:

1 ϑ 01 ( x ) = 1 + 2 x + 4 x 2 + 8 x 3 + 14 x 4 + 24 x 5 + . . . {\displaystyle {\frac {1}{\vartheta _{01}(x)}}=1+2x+4x^{2}+8x^{3}+14x^{4}+24x^{5}+...}

Im Vergleich hierzu gilt für die Thetafunktion ϑ₀₁(x) selbst diese Formel:

ϑ 01 ( x ) = 1 − { ∑ k = 1 ∞ 2 [ x ( 2 k − 1 ) 2 − x ( 2 k ) 2 ] } {\displaystyle \vartheta _{01}(x)=1-{\biggl \{}\sum _{k=1}^{\infty }2{\bigl [}x^{(2k-1)^{2}}-x^{(2k)^{2}}{\bigr ]}{\biggr \}}}

ϑ 01 ( x ) = 1 − 2 x + 2 x 4 − 2 x 9 + 2 x 16 − 2 x 25 ± . . . {\displaystyle \vartheta _{01}(x)=1-2x+2x^{4}-2x^{9}+2x^{16}-2x^{25}\pm ...}

Über die Thetafunktion ϑ₀₁(x) gilt diese Identität:

ϑ 01 ( x ) − 1 = ( x ; x ) ∞ − 1 ( x ; x 2 ) ∞ − 1 {\displaystyle \vartheta _{01}(x)^{-1}=(x;x)_{\infty }^{-1}(x;x^{2})_{\infty }^{-1}}

Daraus folgt diese Formel:

[ ∑ n = 0 ∞ P ¯ ( n ) x n ] = [ ∑ n = 0 ∞ P ( n ) x n ] [ ∑ n = 0 ∞ Q ( n ) x n ] {\displaystyle {\biggl [}\sum _{n=0}^{\infty }{\overline {P}}(n)x^{n}{\biggr ]}={\biggl [}\sum _{n=0}^{\infty }P(n)x^{n}{\biggr ]}{\biggl [}\sum _{n=0}^{\infty }Q(n)x^{n}{\biggr ]}}

Und deswegen ist auch jene Formel für die Synthese der Zahlenfolge P ¯ ( n ) {\displaystyle {\overline {P}}(n)} gültig:

P ¯ ( n ) = ∑ k = 0 n P ( n − k ) Q ( k ) {\displaystyle {\overline {P}}(n)=\sum _{k=0}^{n}P(n-k)Q(k)}

Im nun Folgenden werden auch hierfür zwei Beispiele akkurat ausgeführt:

P ¯ ( 6 ) = ∑ k = 0 6 P ( 6 − k ) Q ( k ) = {\displaystyle {\overline {P}}(6)=\sum _{k=0}^{6}P(6-k)Q(k)=}

= P ( 6 ) Q ( 0 ) + P ( 5 ) Q ( 1 ) + P ( 4 ) Q ( 2 ) + P ( 3 ) Q ( 3 ) + P ( 2 ) Q ( 4 ) + P ( 1 ) Q ( 5 ) + P ( 0 ) Q ( 6 ) = {\displaystyle =P(6)Q(0)+P(5)Q(1)+P(4)Q(2)+P(3)Q(3)+P(2)Q(4)+P(1)Q(5)+P(0)Q(6)=}

= 11 × 1 + 7 × 1 + 5 × 1 + 3 × 2 + 2 × 2 + 1 × 3 + 1 × 4 = 40 {\displaystyle =11\times 1+7\times 1+5\times 1+3\times 2+2\times 2+1\times 3+1\times 4=40}

P ¯ ( 7 ) = ∑ k = 0 7 P ( 7 − k ) Q ( k ) = {\displaystyle {\overline {P}}(7)=\sum _{k=0}^{7}P(7-k)Q(k)=}

= P ( 7 ) Q ( 0 ) + P ( 6 ) Q ( 1 ) + P ( 5 ) Q ( 2 ) + P ( 4 ) Q ( 3 ) + P ( 3 ) Q ( 4 ) + P ( 2 ) Q ( 5 ) + P ( 1 ) Q ( 6 ) + P ( 0 ) Q ( 7 ) = {\displaystyle =P(7)Q(0)+P(6)Q(1)+P(5)Q(2)+P(4)Q(3)+P(3)Q(4)+P(2)Q(5)+P(1)Q(6)+P(0)Q(7)=}

= 15 × 1 + 11 × 1 + 7 × 1 + 5 × 2 + 3 × 2 + 2 × 3 + 1 × 4 + 1 × 5 = 64 {\displaystyle =15\times 1+11\times 1+7\times 1+5\times 2+3\times 2+2\times 3+1\times 4+1\times 5=64}

Die hier gezeigte Tabelle stellt die genannten drei Zahlenfolgen zusammen:

n	P(n)	Q(n)	P ¯ ( n ) {\displaystyle {\overline {P}}(n)}
0	1	1	1
1	1	1	2
2	2	1	4
3	3	2	8
4	5	2	14
5	7	3	24
6	11	4	40
7	15	5	64

• Jacobus Hendricus van Lint, R. M. Wilson: A Course in Combinatorics. 2. Auflage. Cambridge University Press, Cambridge 2001, ISBN 0-521-80340-3. 
• Derrick Henry Lehmer: Two nonexistence theorems on partitions. In: Bulletin of the American Mathematical Society. Volume 52, Nr. 6, 1946, S. 538–544, doi:10.1090/S0002-9904-1946-08605-X (projecteuclid.org [abgerufen am 18. Februar 2012]). 
• John Edensor Littlewood: A Mathematician’s Miscellany. Eine Entdeckungsreise. Methuen, London 1953, ISBN 3-540-42386-9, S. 84–90 (englisch, Volltext in verschiedenen Dateiformaten [abgerufen am 15. Februar 2012] Littlewood erzählt in diesem Buch unter anderem über Hardys 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 usw. 2002, ISBN 3-540-42386-9, 10.7 Zahlpartitionen (Inhaltsverzeichnis d-nb.info [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). 
• Sylvie Corteel, Jeremy Lovejoy: Overpartitions. Versailles / Talence 2004, S. 1–13 (lovejoy.perso.math.cnrs.fr [PDF; abgerufen am 10. März 2022]). 

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 filediva.com [abgerufen am 15. Februar 2012]). 

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

1. ↑ Florian Scheck: Theoretische Physik 5: Statistische Theorie der Wärme. Springer, 2008, ISBN 978-3-540-79823-1, S. 98 (eingeschränkte Vorschau in der Google-Buchsuche). 
2. ↑ ^{a b c d e f} Jiří Matoušek, Jaroslav Nešetřil: Diskrete Mathematik. Eine Entdeckungsreise. 2002.
3. ↑ Eric W. Weisstein: Partition Function Q. In: MathWorld (englisch).
4. ↑ Ian Macdonald: Symmetric functions and Hall polynomials. Hrsg.: Oxford University Press. 2. Auflage. New York, ISBN 978-0-19-873912-8, S. 1. 
5. ↑ Angelika Steger: Diskrete Strukturen 1: Kombinatorik, Graphentheorie, Algebra. Springer, 2001, ISBN 3-540-67597-3, S. 36. 
6. ↑ Karl-Heinz Zimmermann: Diskrete Mathematik. Books on Demand, 2006, ISBN 3-8334-5529-2, S. 115. 
7. ↑ John Edensor Littlewood: A Mathematician’s Miscellany. Eine Entdeckungsreise. Methuen, London 1953.
8. ↑ J. H. Bruinier, K. Ono: Algebraic formulas for the coefficients of half-integral weight harmonic weak Maass forms. In: Advances in Mathematics, Band 246, S. 198–219, 2013; arxiv:1104.1182 Preprint 2011.
9. ↑ Eulers Erbe – Mathematiker feiern Entdeckung in der Zahlentheorie. In: sueddeutsche.de. 27. Januar 2011, ehemals im Original (nicht mehr online verfügbar); abgerufen am 8. März 2024.@1@2Vorlage:Toter Link/www.sueddeutsche.de (Seite nicht mehr abrufbar. Suche im Internet Archive (T)) 
10. ↑ Ferrers war ein britischer Mathematiker (11. August 1829 bis 31. Januar 1903). Jiří Matoušek, Jaroslav Nešetřil: Diskrete Mathematik. Eine Entdeckungsreise. 2002.
11. ↑ Ulrik Brandes: Methoden der Netzwerkanalyse – Vorlesungsskript, 1.15 (PDF; 316 kB) Universität Konstanz; abgerufen am 17. Februar 2012.
12. ↑ Leonhard Euler: Introductio analysin infinitorum. Band 1. Lausanne 1748, S. 253–275
13. ↑ ^{a b} Derrick Henry Lehmer: Two nonexistence theorems on partitions. In: Bulletin of the American Mathematical Society. Volume 52, Nr. 6, 1946.
14. ↑ code golf - Strict partitions of a positive integer. Abgerufen am 9. März 2022. 
15. ↑ A000009. In: OEIS. Abgerufen am 9. März 2022. 
16. ↑ Eric W. Weisstein: Partition Function Q. In: mathworld.wolfram.com. Abgerufen am 9. März 2022 (englisch).