Ganzzahl-Partitionsrechner

Die ganzzahlige Partitionfunktion p(n) beantwortet eine klassische Zählfrage: auf wie viele Weisen lässt sich eine nichtnegative ganze Zahl n als Summe positiver ganzer Zahlen schreiben, wenn die Reihenfolge der Summanden keine Rolle spielt? Zum Beispiel gilt 4 gleich 4, 3+1, 2+2, 2+1+1 und 1+1+1+1, sodass p(4) fünf beträgt; 5 hat sieben Partitionen und 10 hat zweiundvierzig. Partitionen treten in der Zahlentheorie, bei erzeugenden Funktionen, in der statistischen Mechanik und bei Programmierwettbewerben auf, sobald Multimengen-Summen statt geordneter Kompositionen oder Partitionen markierter Mengen gezählt werden. Diese Fähigkeit nimmt eine nichtnegative ganze Zahl n entgegen und liefert das exakte p(n) als Dezimalzeichenkette, berechnet mit dynamischer Programmierung in BigInt, sodass Werte weit jenseits üblicher sicherer Integer-Grenzen zifferngenau korrekt bleiben. Ein negatives n wird mit einem klaren Validierungsfehler abgewiesen statt mit einem stillen Nullwert oder einer falschen Antwort.

Wie die Partitionfunktion p(n) definiert ist

Eine uneingeschränkte ganzzahlige Partition einer nichtnegativen ganzen Zahl n ist eine Schreibweise von n als Summe positiver ganzer Zahlen, bei der die Reihenfolge der Summanden unerheblich ist. Nach Konvention ist p(0) gleich eins und zählt die leere Partition der Null. Kleine Lehrbuchwerte sind p(1)=1, p(2)=2 (nämlich 2 und 1+1), p(3)=3, p(4)=5, p(5)=7, p(6)=11 und p(10)=42.

Die gewöhnliche erzeugende Funktion der Folge ist das unendliche Produkt über k größer oder gleich eins von eins geteilt durch eins minus x hoch k, das kodiert, dass jede positive ganze Zahl beliebig oft als Teil vorkommen darf. Eine in Software übliche praktische Rekurrenz ist das klassische dynamische Programm im Münzwechsel-Stil: man initialisiert ein Array mit einer Möglichkeit, die Summe null zu bilden, und addiert für jede Teilgröße von eins bis n die Möglichkeiten, den Rest zu bilden.

Diese Rekurrenz füllt p(n) exakt und zählt Ordnungen nie doppelt, weil Teile nur einmal in nichtabnehmender Größenordnung eingeführt werden. Verwandte, aber andere Objekte sind Kompositionen, bei denen die Reihenfolge zählt und es zwei hoch n minus eins Kompositionen von n gibt; Mengenpartitionen, gezählt durch Stirling-Zahlen zweiter Art oder Bell-Zahlen, die markierte Elemente partitionieren statt unmarkierte positive ganze Zahlen zu addieren; sowie eingeschränkte Partitionen, die verschiedene Teile, nur ungerade Teile oder eine feste Anzahl von Teilen verlangen.

Diese Implementierung nutzt niemals Gleitkomma-Näherung, Monte-Carlo-Stichproben oder externe Tabellen: sie füllt ein eindimensionales BigInt-Array, sodass jede Ziffer korrekt ist. Der Pfad ist vollständig deterministisch — ohne Zufallsseeds, ohne Uhren, ohne Netz und ohne Modelldrift —, sodass dasselbe n stets dieselbe Zeichenkette liefert.

Wo ganzzahlige Partitionen in der Praxis vorkommen

Zahlentheorie-Kurse und Programmierwettbewerbe fragen ständig, wie viele uneingeschränkte Partitionen ein gegebenes n hat, wie p(n) wächst oder ob eine Tabelle kleiner Werte mit den Ramanujan-Kongruenzen und anderen klassischen Identitäten übereinstimmt. Algorithmendesigner nutzen Partitionzahlen bei der Analyse von Zustandsräumen im Stil ganzzahliger Rucksäcke, beim Zählen von Multimengen-Zerlegungen eines Ressourcenbudgets oder beim Dimensionieren von DP-Tabellen, deren Dimensionen Teilgrößen verfolgen. Physik- und Kombinatorik-Kontexte verbinden p(n) mit bosonischen Partitionfunktionen und Koeffizienten erzeugender Funktionen; Lehrende zeigen oft eine kurze Liste der Partitionen eines kleinen n und fragen dann nur nach der Anzahl.

Interviewvorbereitung und Olympiade-Training brauchen häufig ein zuverlässiges p(n), ohne große Tabellen von Hand zu pflegen oder um eins versetzte Kompositionszählungen zu riskieren. Wenn Sie später Kompositionen brauchen, bei denen die Reihenfolge zählt, Mengenpartitionen über Stirling-Zahlen zweiter Art, nur Bell-Zahlen, eingeschränkte Partitionen mit verschiedenen oder nur ungeraden Teilen oder eine explizite Auflistung jeder Partition statt der Anzahl, behandeln Sie diese als getrennte Suchabsichten statt diese Seite zu überladen.

Halten Sie n innerhalb der dokumentierten Schranke, damit die Latenz der kostenlosen Stufe vorhersagbar bleibt, und bevorzugen Sie Zeichenketten-Verbraucher für den zurückgegebenen Wert, weil p(n) den sicheren Integer-Bereich lange vor fünftausend verlässt.