Partitionsfunktions-Rechner

Willkommen beim Partitionsfunktions-Rechner, einem umfassenden Explorer für eines der faszinierendsten Objekte der Kombinatorik. Geben Sie eine beliebige nicht-negative ganze Zahl \(n\) ein und dieses Tool berechnet \(p(n)\) — die Anzahl der Möglichkeiten, \(n\) als Summe positiver ganzer Zahlen zu schreiben, bei denen die Reihenfolge keine Rolle spielt — zusammen mit der Anzahl der Partitionen in ungleiche Teile \(q(n)\), der Anzahl der Partitionen in ungerade Teile \(o(n)\), der asymptotischen Hardy-Ramanujan-Schätzung, allen zutreffenden Ramanujan-Kongruenzen und (für kleine \(n\)) jeder einzelnen Partition, dargestellt als animiertes Young-Diagramm.

Was ist die Partitionsfunktion p(n)?

Die Partitionsfunktion \(p(n)\) zählt die Anzahl der Möglichkeiten, \(n\) als Summe positiver ganzer Zahlen auszudrücken, ohne die Reihenfolge zu berücksichtigen. Zwei Summen, die sich nur in der Reihenfolge ihrer Summanden unterscheiden, werden als dieselbe Partition betrachtet. Zum Beispiel sind die Partitionen von 4:

• 4
• 3 + 1
• 2 + 2
• 2 + 1 + 1
• 1 + 1 + 1 + 1

Das ergibt \(p(4) = 5\). Konventionsgemäß ist \(p(0) = 1\), was die "leere Partition" zählt. Weitere Werte: \(p(1) = 1,\ p(5) = 7,\ p(10) = 42,\ p(50) = 204.226,\ p(100) = 190.569.292.\)

Erzeugende Funktion

Leonhard Euler entdeckte, dass die erzeugende Funktion für \(p(n)\) eine wunderschön kompakte Produktform besitzt:

Jeder Faktor \(1/(1 - x^k) = 1 + x^k + x^{2k} + \ldots\) trägt die Entscheidung bei, wie oft der Teil \(k\) in der Partition erscheint. Das Multiplizieren der Faktoren erzeugt jede Partition genau einmal.

Young- (Ferrers-) Diagramme

Ein Young-Diagramm (auch Ferrers-Diagramm genannt) stellt eine Partition visuell als linksbündige Anordnung von Kästchen dar. Jede Zeile entspricht einem Teil, und die Zeilen sind vom größten zum kleinsten aufgelistet. Zum Beispiel wird die Partition \(4 + 2 + 1\) von 7 zu:

Young-Diagramme ermöglichen es, Partitionsidentitäten zu "sehen". Das Spiegeln eines Diagramms an seiner Hauptdiagonale macht Zeilen zu Spalten, was der konjugierten Partition entspricht. Dieser Rechner rendert ein Young-Diagramm für jede Partition von \(n\), sofern \(n \le 15\) ist.

Eulers Partitionstheorem

Eines der elegantesten Ergebnisse von Euler besagt:

Zum Beispiel sind die Partitionen von 7 in ungleiche Teile \(\{7\}, \{6+1\}, \{5+2\}, \{4+3\}, \{4+2+1\}\) — fünf Stück. Die Partitionen von 7 in ungerade Teile sind \(\{7\}, \{5+1+1\}, \{3+3+1\}, \{3+1+1+1+1\}, \{1+1+1+1+1+1+1\}\) — ebenfalls fünf. Die Übersichtstabelle des Rechners zeigt sowohl \(q(n)\) als auch \(o(n)\) an, damit Sie diese Identität für Ihr gewähltes \(n\) überprüfen können.

Die Hardy-Ramanujan-Asymptotik

Im Jahr 1918 bewiesen G.H. Hardy und Srinivasa Ramanujan die erste Formel, die die wahre Wachstumsrate von \(p(n)\) für große \(n\) erfasste:

Das Ergebnis resultierte aus der Hardy-Ramanujan-Kreismethode, die die erzeugende Funktion um Singularitäten auf dem Einheitskreis integriert. Hans Rademacher verfeinerte sie 1937 zu einer exakten konvergenten Reihe — eine der gefeiertsten Formeln der analytischen Zahlentheorie.

Ramanujans Partition-Kongruenzen

Beim Studium der Tabelle der Partitionswerte bemerkte Ramanujan drei erstaunliche Teilbarkeitsmuster:

Zum Beispiel sind \(p(4)=5,\ p(9)=30,\ p(14)=135,\ p(19)=490,\ p(24)=1575\) alle durch 5 teilbar. Der Rechner markiert automatisch, wenn Ihr gewähltes \(n\) in eine dieser Klassen fällt.

So verwenden Sie diesen Rechner

1. Geben Sie eine nicht-negative ganze Zahl bis 500 in das Eingabefeld ein oder klicken Sie auf eines der bekannten Schnellbeispiele (0, 4, 10, 42, 100, 200).
2. Klicken Sie auf "Partitionen berechnen". Das Tool berechnet \(p(n)\), \(q(n)\), \(o(n)\) und die Hardy-Ramanujan-Schätzung.
3. Überprüfen Sie das Hero-Panel, das \(p(n)\) als große Schlagzeilenzahl anzeigt, und scannen Sie dann die Zusammenfassung nach ungleichen Teilen, ungeraden Teilen, der asymptotischen Schätzung und dem prozentualen Fehler.
4. Inspizieren Sie Young-Diagramme — wenn \(n \le 15\), wird jede einzelne Partition als animiertes Young-Diagramm in einem responsiven Raster gezeichnet.
5. Erforschen Sie das Wachstumsdiagramm — es stellt \(p(k)\), \(q(k)\) und die Hardy-Ramanujan-Kurve für \(k = 0, 1, \ldots, n\) dar. Schalten Sie zwischen linearer und logarithmischer Skala um, um die asymptotische Form zu sehen.
6. Lesen Sie die Wachstumstabelle — eine zeilenweise Ansicht von \(p(k), q(k), o(k)\) für kleine \(k\). Verwenden Sie sie, um das erste Auftreten jeder Ramanujan-Kongruenz zu finden.

Anwendungsbeispiel: Partitionen von 5

Gehen wir das Beispiel \(n = 5\) durch. Alle Partitionen sind:

• \(5\)
• \(4 + 1\)
• \(3 + 2\)
• \(3 + 1 + 1\)
• \(2 + 2 + 1\)
• \(2 + 1 + 1 + 1\)
• \(1 + 1 + 1 + 1 + 1\)

Somit ist \(p(5) = 7\). Partitionen in ungleiche Teile: \(\{5\}, \{4+1\}, \{3+2\}\) — drei Stück, also \(q(5) = 3\). Partitionen in ungerade Teile: \(\{5\}, \{3+1+1\}, \{1+1+1+1+1\}\) — ebenfalls drei, also \(o(5) = 3\). Eulers Theorem ist erfüllt. Schließlich ist \(n = 5 \equiv 0 \pmod 5\) nicht von der Form \(5k+4\), daher gilt die 5er-Kongruenz hier nicht; jedoch erfüllt \(p(4) = 5\) die Bedingung \(p(5k+4) \equiv 0 \pmod 5\).

Klassische Werte von p(n)

Geschichte

• 1750er: Leonhard Euler untersucht Partitionen und entdeckt die Identität der erzeugenden Funktion sowie das "ungleich = ungerade" Theorem.
• 1915: Major Percy MacMahon veröffentlicht eine Tabelle von \(p(n)\) für \(n\) bis 200 — von Hand berechnet.
• 1918: Hardy und Ramanujan beweisen die asymptotische Formel mittels der Kreismethode.
• 1919: Ramanujan veröffentlicht die berühmten Kongruenzen \(p(5k+4),\ p(7k+5),\ p(11k+6)\).
• 1937: Hans Rademacher verfeinert Hardy-Ramanujan zu einer exakten konvergenten Reihe.
• 2011: Ken Ono und Jan Bruinier beweisen, dass \(p(n)\) für jede positive ganze Zahl als endliche algebraische Summe ausgedrückt werden kann.

Anwendungen

• Kombinatorik und Darstellungstheorie — Partitionen indizieren irreduzible Darstellungen der symmetrischen Gruppe \(S_n\).
• Statistische Mechanik — Partitionszahlen treten in der Entropie idealer Quantengase und in Partitionsfunktionen der Stringtheorie auf.
• Modulformen — Die erzeugende Funktion für \(p(n)\) ist eng verwandt mit der Dedekindschen Eta-Funktion.
• Informatik — Benchmarks zur Aufzählung von Teilmengen-Summen und ganzzahliger Programmierung nutzen häufig Partitionszahlen.

Häufig gestellte Fragen

Was ist die Partitionsfunktion p(n)?

\(p(n)\) zählt die Anzahl der Möglichkeiten, \(n\) als Summe positiver ganzer Zahlen auszudrücken, wobei die Reihenfolge keine Rolle spielt. \(p(4) = 5\), da 4 als \(4\), \(3+1\), \(2+2\), \(2+1+1\) oder \(1+1+1+1\) geschrieben werden kann. Konventionsgemäß ist \(p(0) = 1\).

Was ist ein Young- oder Ferrers-Diagramm?

Ein Young-Diagramm ist eine visuelle Darstellung einer Partition: Jeder Teil wird zu einer Reihe von linksbündigen Kästchen, wobei die Teile von oben nach unten vom größten zum kleinsten aufgelistet werden. Für \(4+2+1\) zeichnet man eine Reihe mit 4, eine Reihe mit 2 und eine Reihe mit 1 Kästchen. Dieser Rechner rendert ein Young-Diagramm für jede Partition, wenn \(n \le 15\) ist.

Was besagt das Eulersche Partitionstheorem?

Für jede positive ganze Zahl \(n\) ist die Anzahl der Partitionen von \(n\) in ungleiche Teile gleich der Anzahl der Partitionen von \(n\) in ungerade Teile. Für \(n = 5\): Ungleiche Teile ergeben \(\{5\}, \{4+1\}, \{3+2\}\); ungerade Teile ergeben \(\{5\}, \{3+1+1\}, \{1+1+1+1+1\}\). Beide Zählungen ergeben 3.

Was ist die asymptotische Hardy-Ramanujan-Formel?

Sie besagt, dass \(p(n) \sim \frac{1}{4n\sqrt{3}} \exp\!\left(\pi \sqrt{2n/3}\right)\) für \(n \to \infty\) gilt. Dies war die erste Formel, die die exakte Wachstumsrate von \(p(n)\) beschrieb, entdeckt 1918 von G.H. Hardy und Srinivasa Ramanujan.

Was sind die Ramanujan-Partition-Kongruenzen?

Drei bemerkenswerte Teilbarkeitsmuster: \(p(5k+4) \equiv 0 \pmod 5\), \(p(7k+5) \equiv 0 \pmod 7\) und \(p(11k+6) \equiv 0 \pmod{11}\). Zum Beispiel sind \(p(4)=5, p(9)=30, p(14)=135\) alle durch 5 teilbar.

Wie schnell wächst p(n)?

p(n) wächst subexponentiell, aber schneller als jedes Polynom, grob wie \(\exp(\pi \sqrt{2n/3})\). Zum Vergleich: \(p(10)=42\), \(p(50)=204.226\), \(p(100)=190.569.292\) und \(p(200) \approx 4 \times 10^{12}\). Verwenden Sie die Log-Skala-Umschaltung des Diagramms, um diese Wachstumskurve zu visualisieren.

Zusätzliche Ressourcen

• Ramanujans Kongruenzen - Wikipedia (Englisch)