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) ZahlpartitionJiří Matoušek, Jaroslav Nešetřil: Diskrete Mathematik. Eine Entdeckungsreise. 2002. 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 ) wird als , manchmal auch als notiert und ist . 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 oder notiert und ist . mini|Partitionsfunktion P(n) in halblogarithmischer Darstellung
Mit einer aus der Partitionsfunktion abgeleiteten zahlentheoretischen Funktion kann die Anzahl der Isomorphietypen für die endlichen abelschen Gruppen angegeben werden.
Partition Eine Partition ist eine (endliche oder unendliche) Folge bestehend aus nicht-negativen ganzen Zahlen
Die Zahl nennt man Gewicht. Die Folgenglieder, welche nicht Null sind , nennt man Teile von und die Anzahl der Teile nennt man Länge der Partition. Partitionen, welche die gleichen Teile haben, werden wir miteinander identifizieren, das heißt
beschreiben dieselbe Partition mit Länge .
Wenn gilt, dann ist eine Partition von .
Eigenschaften von P(n)
Beispielwerte + 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 ):
Rekursive Darstellung + Beispielwerte von P(n,k) P(n,k) k12345678910 n112113111412115122116133211713432118145532119147653211101589753211 Bezeichnet die Anzahl der Möglichkeiten, die positive, ganze Zahl in genau positive, ganze Summanden zu zerlegen, dann gilt
,
wobei sich die Zahlen rekursiv über und sowie
oder direkt durch
ermitteln lassen.
Asymptotisches Verhalten + Relativer Fehler der Approximationsfunktion 5 10 100 250 500 in % 27,7 14,5 4,57 2,86 2,01 Für große Werte von gibt die Formel von Godfrey Harold Hardy und S. RamanujanJohn Edensor Littlewood: A Mathematician’s Miscellany. Eine Entdeckungsreise. Methuen, London 1953.
einen guten Näherungswert für . Insbesondere bedeutet dies, dass die Anzahl der Dezimalstellen von etwa proportional zur Quadratwurzel aus ist: P(100) hat 9 Stellen (), P(1000) hat 32 Stellen ().
hat etwa doppelt so viele Stellen wie .
Deswegen gilt dieser Grenzwert des Quotienten sukzessiver Folgenglieder:
Erzeugende Funktion Eine einfache erzeugende Funktion für die Partitionsfunktion gewinnt man aus der multiplikativ Inversen von Eulers Funktion:
Dabei wird mit dem Funktionskürzel die Ramanujansche Psifunktion zum Ausdruck gebracht. Der runde Klammerausdruck mit dem Unendlichkeitsindex stellt das Pochhammer-Symbol und ϑ10, ϑ00 und ϑ01 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:
d. h., dass die Koeffizienten der Reihendarstellung von den Werten von entsprechen.
Zusammenhang mit den Pentagonalzahlen Die Koeffizienten von Eulers Funktion
lassen sich mit dem Pentagonalzahlensatz von Leonhard Euler einfach explizit berechnen. Die Folge ist und es gilt stets
Aus der Tatsache, dass Eulers Funktion multiplikativ invers zur erzeugenden Funktion der Partitionsfunktion ist, folgt, dass für die diskrete Faltung und gilt
Die Summation muss nur über erstreckt werden, da beide Folgen als Koeffizientenfolgen ihrer jeweiligen Funktion an negativen Stellen gleich Null sind.
Rekursionsformel aus dem Pentagonalzahlensatz Aus der im vorigen Unterabschnitt angegebenen Faltungsbeziehung zu den Koeffizienten folgt für die Rekursionsformel
für die Partitionsfunktion.
Berechnung mit analytischer Zahlentheorie Eine Möglichkeit zur direkten Berechnung liefert die aus der erzeugenden Funktion hergeleitete Formel
mit
und
die Hans Rademacher, aufbauend auf Erkenntnissen von S. Ramanujan und Godfrey Harold Hardy, fand.
Berechnung mit algebraischer Zahlentheorie Eine algebraische, geschlossene Form von , die ohne unendliche Reihenentwicklung auskommt, wurde 2011 von Jan Hendrik Bruinier und Ken Ono veröffentlicht.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; Preprint 2011. Genauer gesagt geben Bruinier und Ono eine Funktion an, so dass sich für jede natürliche Zahl eine endliche Anzahl algebraischer Zahlen mit
finden lassen. Darüber hinaus gilt, dass auch alle Werte algebraisch sind.
Dieses theoretische Ergebnis führt nur in Spezialfällen (z. B. über daraus ableitbare Kongruenzen) zu einer schnelleren Berechnung der Partitionsfunktion.
Kongruenzen 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:
A. O. L. Atkin fand folgende Kongruenz:
Ferrers-Diagramme
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 kann durch folgendes Diagramm, das als Ferrers-Diagramm bezeichnet wird, dargestellt werden. Diese Diagramme wurden zu Ehren von Norman Macleod Ferrers benannt.Ferrers war ein britischer Mathematiker (11. August 1829 bis 31. Januar 1903). Jiří Matoušek, Jaroslav Nešetřil: Diskrete Mathematik. Eine Entdeckungsreise. 2002.
16px|*16px|*16px|*16px|* 16px|*16px|*16px|* 16px|*16px|*16px|* 16px|*16px|* 16px|* 16px|* 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: 16px|* 16px|* 16px|* 16px|* 16px|*16px|* 16px|* 16px|* 16px|*16px|* 16px|*16px|* 16px|*16px|*16px|* 16px|* 16px|*16px|*16px|*16px|* 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1
Konjugierte Partition Wenn wir das Diagramm der Partition an seiner Hauptdiagonale spiegeln, erhalten wir eine andere Partition von 14:
16px|*16px|*16px|*16px|* 16px|*16px|*16px|* 16px|*16px|*16px|* 16px|*16px|* 16px|* 16px|* ↔ 16px|*16px|*16px|*16px|*16px|*16px|* 16px|*16px|*16px|*16px|* 16px|*16px|*16px|* 16px|* 6 + 4 + 3 + 1 = 4 + 3 + 3 + 2 + 1 + 1
Indem wir so Reihen in Spalten verwandeln, erhalten wir die Partition . Sie heißt die zu konjugierte Partition.Ulrik Brandes: Methoden der Netzwerkanalyse – Vorlesungsskript, 1.15 (PDF; 316 kB) Universität Konstanz; abgerufen am 17. Februar 2012. Unter den Partitionen von 4 sind und ; und jeweils konjugiert zueinander. Besonders interessant sind Partitionen wie , die zu sich selbst konjugiert sind, deren Ferrers-Diagramm also achsensymmetrisch zu seiner Hauptdiagonalen ist.
Die Anzahl der zu sich selbst konjugierten Partitionen von ist gleich der Anzahl der Partitionen von 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: 16px|* 16px|* 16px|* 16px|* 16px|* ↔ 16px|*16px|*16px|* 16px|* 16px|*
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: 16px|o16px|*16px|x 16px|o16px|*16px|x 16px|o16px|*16px|x 16px|o16px|* 16px|o16px|* 16px|o16px|* 16px|o16px|* 16px|o 16px|o ↔ 16px|o16px|o16px|o16px|o16px|o 16px|o16px|*16px|*16px|*16px|* 16px|o16px|*16px|x16px|x 16px|o16px|*16px|x 16px|o16px|* 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 mit höchstens Summanden ist gleich der Anzahl der Partitionen von , bei denen kein Summand größer als ist. der Anzahl der Partitionen von mit genau Summanden.
Formalisierung 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: Eine Zahlpartition von („Diagramm der Ordnung “) ist ein -Tupel („Anzahl der Spalten=Columns“) mit der Eigenschaft , heißt ihre Spaltenzahl. (Um hier auch die „leere“ Partition mitzuerfassen, muss man für setzen , es ist dann die leere Summe und ergibt immer 0.) Die Zahl heißt die Zeilenzahl (=„Rows“) von Eine Zahlpartition heißt „gültig“, wenn für stets gilt, für gültige Partitionen mit ist . Eine Zahlpartition heißt „strikt“, wenn für stets gilt. Strikte Partitionen sind immer gültig. Die konjugierte Partition einer gültigen Partition ist definiert durch . Sie ist gültig.
Alternativ und näher an der grafischen Darstellung der Ferrers-Diagramme kann man jede Partition als -Matrix mit Einträgen aus darstellen, wobei bedeutet, dass sich im Ferrers-Diagramm in der Reihe in Spalte ein Kreis befindet, , dass dort kein Kreis ist. Die Konjugierte einer Partition hat dann als Matrix die transponierte Matrix der ursprünglichen Partition.
Varianten Partitionen mit vorgegebenem kleinstem Summanden, p(k,n)
Bei einer Abwandlung der Partitionsfunktion wird verlangt, dass der kleinste Summand in der Zahlpartition größer oder gleich ist. Die Anzahl solcher Partitionen wird als notiert. Die „normale“ Partitionsfunktion ist somit Diese Abwandlung ist .
Beispielwerte für p(k,n) + Beispielwerte von p(k,n) p(k,n) k12345678910 n112213311452115721116114211171542111182273211119308421111110421253211111 Zu den Werten von für kleine Zahlen siehe auch die zweite Tabelle rechts. Einzelwerte sind: