Der Fünfeckszahlensatz

Wähle eine Zahl n. Die Seite listet jede Möglichkeit auf, sie als Summe verschiedener positiver ganzer Zahlen zu schreiben. Du siehst sie als Punktdiagramme, die durch die Franklin-Operation gepaart werden: eines mit einer geraden Anzahl von Summanden neben einem mit einer ungeraden. Höchstens ein Diagramm bleibt ohne Partner, und das auch nur, wenn n eine Fünfeckszahl ist. Unten wird das Produkt (1 − x)(1 − x²)… Klammer für Klammer ausmultipliziert. Seine Koeffizienten erzählen dieselbe Geschichte.

Rechenbeispiel — Der Fünfeckszahlensatz

Gerade Anzahl Summanden	7
Ungerade Anzahl Summanden	8
Gerade minus ungerade	−1
p(12), nach Eulers Rekursion	77
p(100)	190.569.292

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Der Fünfeckszahlensatz

Eulerscher Fünfeckszahlensatz: (1 − x)(1 − x²)(1 − x³)… = 1 − x − x² + x⁵ + x⁷ − x¹² − x¹⁵ + …, eine Summe über jede ganze Zahl k, positiv, negativ oder null, von (−1)ᵏ x^(k(3k − 1)/2). Die Exponenten sind die verallgemeinerten Fünfeckszahlen, und jeder Koeffizient ist 0, +1 oder −1.

Was die einzelnen Symbole bedeuten

p(n): die Anzahl der Partitionen von n: Möglichkeiten, es als Summe positiver ganzer Zahlen zu schreiben, ohne Beachtung der Reihenfolge
D₊(n), D₋(n): die Partitionen von n in verschiedene Summanden mit einer geraden bzw. einer ungeraden Anzahl von Summanden
k(3k ∓ 1)/2: die verallgemeinerten Fünfeckszahlen 1, 2, 5, 7, 12, 15, 22, 26, …

Woher die Formel kommt

Warum jeder Koeffizient gerade minus ungerade ist. Wenn du (1 − x)(1 − x²)(1 − x³)… ausmultiplizierst, wählst du aus jeder Klammer entweder 1 oder −xᵏ. Entscheidest du dich bei einigen Klammern für −xᵏ, ergibt das x hoch die Summe dieser k. Jede solche Wahl steuert ein Minuszeichen bei. Der Koeffizient von xⁿ erhält also +1 für jede Möglichkeit, n als Summe verschiedener positiver ganzer Zahlen mit einer geraden Anzahl an Summanden zu schreiben, und −1 für jede Möglichkeit mit einer ungeraden Anzahl. Der Satz besagt, dass diese Differenz null ist – außer bei den Fünfeckszahlen, wo sie (−1)ᵏ beträgt.
Warum die Franklin-Operation sie paart. Nimm ein Diagramm mit unterschiedlichen Zeilenlängen. Sei s der kleinste Summand und g die Steigung: die Anzahl der Zeilen von oben gezählt, die jeweils um genau eins abnehmen. Wenn s ≤ g ist, nimmst du die unterste Zeile und fügst ans Ende der oberen s Zeilen je einen Punkt an. Ist s > g, nimmst du vom Ende der oberen g Zeilen je einen Punkt weg und bildest daraus eine neue unterste Zeile der Länge g. In beiden Fällen bleiben die Zeilenlängen verschieden, die Gesamtsumme bleibt n, und die Anzahl der Zeilen ändert sich um eins. Dadurch tauschen gerade und ungerade ihre Plätze, und eine erneute Anwendung macht den Schritt rückgängig. Die Operation ist nur blockiert, wenn die unterste Zeile und die Steigung sich einen Punkt teilen und s = g oder s = g + 1 gilt. Diese Diagramme sind k + (k + 1) + … + (2k − 1) und (k + 1) + … + 2k. Ihre Summen betragen k(3k − 1)/2 und k(3k + 1)/2.
Vom Satz zu p(n). Jede Partition von n, auch mit Wiederholungen, wird durch Σ p(n) xⁿ = 1/((1 − x)(1 − x²)(1 − x³)…) gezählt. Multipliziere beide Seiten mit dem Produkt, also mit der Fünfeckszahlenreihe: (1 − x − x² + x⁵ + x⁷ − x¹² − …) × Σ p(n) xⁿ = 1. Für n ≥ 1 ist der Koeffizient von xⁿ auf der rechten Seite 0. Es gilt also p(n) − p(n − 1) − p(n − 2) + p(n − 5) + p(n − 7) − … = 0. Das ist Eulers Rekursionsformel, und die Anzahl ihrer Terme wächst nur wie √n.

Zweihundert Klammern, und nur 23 der ersten 201 Koeffizienten überleben 🖖

Multipliziere (1 − x)(1 − x²) aus, und du erhältst 1 − x − x² + x³. Mach mit dem Schieberegler unter dem Balkendiagramm Klammer für Klammer weiter. Die Koeffizienten wachsen, erreichen zwischendurch 31 und heben sich dann auf. Nach 200 Klammern sind nur 23 der ersten 201 Koeffizienten nicht null. Jeder von ihnen ist +1 oder −1, und sie stehen bei 0, 1, 2, 5, 7, 12, 15, 22, 26, … Das sind die Fünfeckszahlen, k(3k − 1)/2 und k(3k + 1)/2. Euler fand dieses Muster, indem er das Produkt ausmultiplizierte.

Eine Paarung beweist es: Bei 12 bleibt genau eine Partition übrig 🖖

Klick auf n = 9. Die 8 Möglichkeiten, 9 als Summe verschiedener positiver ganzer Zahlen zu schreiben, teilen sich auf in 4 mit einer geraden Anzahl von Summanden und 4 mit einer ungeraden. Die Franklin-Operation paart jede gerade mit einer ungeraden. Klick auf n = 12: 7 gerade stehen 8 ungeraden gegenüber. Eine Partition hat keinen Partner, nämlich 5 + 4 + 3. Ihre Summe, 12, ist eine Fünfeckszahl. Klick sie an, und die Seite zeigt dir, warum die Operation dort blockiert ist. Der Koeffizient von x¹² ist gerade minus ungerade, also −1. Diese Paarung ist der gesamte Beweis. Franklin, ein Student von Sylvester an der Johns Hopkins University, veröffentlichte ihn 1881.

p(1000) erfordert 50 Rückgriffe 🖖

Dreh den Satz um, und er zählt Partitionen p(n), also Summen in beliebiger Reihenfolge mit erlaubten Wiederholungen. Eulers Rekursionsformel verwendet nur frühere Werte in fünfeckigen Abständen: p(12) = p(11) + p(10) − p(7) − p(5) + p(0) = 77. Für p(1000), eine 32 Ziffern lange Zahl, sind das 50 Terme. Die gesamte Tabelle von p(1) bis p(1000) erfordert 33.475 Rückgriffe, im Vergleich zu 500.500 Additionen auf dem herkömmlichen Weg. Klick auf p(200) für 3.972.999.029.388. Dies ist der letzte Eintrag in MacMahons Tabelle für Hardy und Ramanujan. Der erste Term ihrer berühmten Formel ist bei n = 1.000 immer noch 1,42 % zu hoch.

Aufgabe vollständig gelöst

Eulers „außerordentliches Gesetz“: Teilersummen aus denselben Vorzeichen 4 Schritte
Die Vorzeichen, die p(n) bilden, bilden auch die Summe der Teiler von n. Euler nannte dies ein höchst außerordentliches Gesetz. Berechne damit σ(12), die Teilersumme von 12, mit einer kleinen Änderung an der Formel: Wo du σ(0) bräuchtest, verwendest du n selbst.

Öffne diese Aufgabe im Tool
1. Die Rekursionsformel der Seite für p(12) als Vorlage:
  
  $p (12) = p (11) + p (10) - p (7) - p (5) + p (0) = 56 + 42 - 15 - 7 + 1 = 77$
2. Dieselben Abstände und Vorzeichen für σ(12). Der letzte Abstand ist 12 selbst, also wird σ(0) zu 12:
  
  $σ (12) = σ (11) + σ (10) - σ (7) - σ (5) + σ (0) \to 12$
3. Mit σ(11) = 12, σ(10) = 18, σ(7) = 8 und σ(5) = 6:
  
  $σ (12) = 12 + 18 - 8 - 6 + 12 = 28$
4. Überprüfe das Ergebnis, indem du die Teiler direkt addierst:
  
  $1 + 2 + 3 + 4 + 6 + 12 = 28$
Antwort

σ(12) = 28. Euler notierte dies im Jahr 1747, und es gilt für jedes n. Die eigene Arithmetik der Seite prüft dies bis n = 500.

$σ (12) = 28; σ (n) = \sum_{k} (- 1)^{k + 1} σ (n - \frac{k ( 3 k \mp 1 )}{2}), σ (0) \to n$

Lernpfad

Beweismethoden

Quellen (3)

Franklin's involution as stated on this page (compare the smallest part with the slope; move one onto the other; blocked only at the pentagonal diagrams), with Franklin's 1881 paper and his place as Sylvester's student at Johns Hopkins: I. Pak, "Partition bijections, a survey", The Ramanujan Journal 12, 5–75 (2006); preprint, §5.2.
Euler's paper on the sum of divisors, where the pentagonal signs that give p(n) give σ(n) too, the worked problem: L. Euler, "Découverte d'une loi tout extraordinaire des nombres par rapport à la somme de leurs diviseurs", Bibliothèque impartiale 3, 10–31 (written 1747, published 1751); Eneström number E175, The Euler Archive.
The partition numbers, Euler's recurrence over the generalised pentagonal numbers, Hardy and Ramanujan's asymptotic formula, and MacMahon's table of p(n) up to 200: OEIS Foundation, "A000041: a(n) = number of partitions of n" and "A001318: Generalized pentagonal numbers", The On-Line Encyclopedia of Integer Sequences.

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.