Was eine Zahlpartition ist
Eine Partition einer natürlichen Zahl n ist eine Zerlegung in positive ganze Summanden, bei der die Reihenfolge keine Rolle spielt. Die Zahl 4 hat fünf Partitionen: 4, 3+1, 2+2, 2+1+1 und 1+1+1+1. Die Anzahl wird mit p(n) bezeichnet. Sie wächst zunächst langsam und dann sehr schnell: p(10) = 42, p(100) = 190.569.292, und p(200) hat bereits 13 Stellen.
Eine geschlossene Formel aus elementaren Funktionen gibt es für p(n) nicht. Der Rechner zählt deshalb mit dynamischer Programmierung: Er geht die möglichen Summanden 1, 2, 3 und so weiter der Reihe nach durch und addiert, auf wie viele Arten der Rest gebildet werden kann. Das entspricht der Erzeugendenfunktion von Euler, dem Produkt der Faktoren 1/(1 − xk). Gerechnet wird mit ganzen Zahlen beliebiger Länge, das Ergebnis ist also exakt.
Zusätzlich zeigt der Rechner q(n), die Zahl der Partitionen in lauter verschiedene Summanden. Nach einem Satz von Euler ist sie gleich der Zahl der Partitionen in lauter ungerade Summanden. Für n = 7 sind das je fünf: 7, 6+1, 5+2, 4+3, 4+2+1 einerseits und 7, 5+1+1, 3+3+1, 3+1+1+1+1, 1+1+1+1+1+1+1 andererseits.
Bellzahlen, Catalan-Zahlen und Näherungen
Die Bellzahl B(n) beantwortet eine andere Frage: Auf wie viele Arten lässt sich eine Menge mit n unterscheidbaren Elementen in nicht leere Gruppen aufteilen? Bei drei Personen sind es fünf Möglichkeiten, von allen zusammen bis zu jeder allein. Anders als bei p(n) kommt es hier darauf an, welche Elemente zusammen in einer Gruppe stehen. Der Rechner bildet B(n) über das Bell-Dreieck, in dem jede Zahl die Summe aus ihrem linken Nachbarn und dem Eintrag darüber ist.
Die Catalan-Zahlen C(n) = 1, 1, 2, 5, 14, 42, 132, … treten in der Kombinatorik ungewöhnlich oft auf. Sie zählen korrekte Klammerungen mit n Paaren, binäre Bäume mit n inneren Knoten, Zerlegungen eines (n + 2)-Ecks in Dreiecke durch Diagonalen und Gitterwege, die die Diagonale nicht überschreiten. Der Rechner berechnet sie über die Rekursion C(n + 1) = C(n) · 2(2n + 1)/(n + 2).
Hardy und Ramanujan fanden 1918 eine asymptotische Formel für p(n). Sie überschätzt den wahren Wert, wird relativ aber immer genauer: Bei n = 100 liegt sie etwa 4,6 % zu hoch, bei n = 300 noch rund 2,6 %. Rademacher verfeinerte die Formel später zu einer konvergenten Reihe, mit der sich p(n) exakt berechnen lässt. Die Werte des Rechners lassen sich mit den Folgen A000041, A000110 und A000108 der OEIS abgleichen.
Für sehr große n zeigt der Rechner die Zahlen in wissenschaftlicher Schreibweise mit der Anzahl der Stellen an, weil Bellzahlen und Catalan-Zahlen rasch Hunderte von Stellen erreichen. Die Liste der einzelnen Partitionen ist auf n bis 12 begrenzt, da p(12) schon 77 Einträge hat. Die Partitionen erscheinen in absteigender Ordnung der Summanden, wie es in Tabellen üblich ist.
Tipps und typische Fehler
Zählen mit System.
- Reihenfolge: Egal bei p(n).
- Mengen: Dafür B(n).
- Klammern: Dafür C(n).
- OEIS: Zum Abgleich.
Mehr zum Thema Primzahlen und Teiler
Häufige Fragen
Ist p(0) gleich 1?
Ja. Die leere Summe ist die einzige Partition der Null, deshalb gilt nach Konvention p(0) = 1. Ebenso sind B(0) = 1 und C(0) = 1.
Was ist der Unterschied zwischen p(n) und B(n)?
p(n) zerlegt eine Zahl, die Summanden sind nicht unterscheidbar. B(n) zerlegt eine Menge unterscheidbarer Elemente in Gruppen und ist deshalb viel größer.
Wie genau ist die Formel von Hardy und Ramanujan?
Sie liefert die richtige Größenordnung und wird mit wachsendem n relativ genauer. Für exakte Werte braucht man die Rekursion oder die Reihe von Rademacher.
Was ist ein Young-Diagramm?
Eine Darstellung einer Partition als Zeilen von Kästchen, deren Längen die Summanden sind, von oben nach unten absteigend.
Wie schnell wächst p(n)?
Etwa wie e hoch π·√(2n/3), also schneller als jede Potenz von n, aber langsamer als eine Exponentialfunktion in n.
- Partitionen berechnen
- Zahlpartition p(n)
- Bellzahl berechnen
- Catalan-Zahl berechnen
- Partitionsfunktion
- Zerlegung in Summanden Anzahl
Alle Berechnungen erfolgen direkt in Ihrem Browser, Ihre Eingaben werden nicht übertragen oder gespeichert. Die Ergebnisse sind Orientierungswerte ohne Gewähr und ersetzen keine steuerliche, rechtliche oder finanzielle Beratung. Die Erklärtexte auf dieser Seite wurden mit KI erstellt. Letzte inhaltliche Änderung dieser Seite: . Mehr dazu: So entstehen und prüfen wir die Rechner.