Partitionen mit verschiedenen Teilen

Die Partitionsfunktion mit verschiedenen Teilen q(n) beantwortet eine klassische Frage der Zahlentheorie: Auf wie viele Arten können Sie eine nichtnegative ganze Zahl n als Summe positiver ganzer Zahlen schreiben, wenn jeder Summand höchstens einmal vorkommt und die Reihenfolge keine Rolle spielt? Zum Beispiel ist 5 gleich 5, 4+1 und 3+2, also ist q(5) gleich drei; 6 hat vier Partitionen mit verschiedenen Teilen und 10 hat zehn. Diese Zählung unterscheidet sich von der uneingeschränkten Partitionsfunktion p(n), die wiederholte Teile wie 2+2 oder 1+1+1 zulässt. Partitionen mit verschiedenen Teilen treten in erzeugenden Identitäten, in Eulers Satz, der sie mit Partitionen in ungerade Teile gleichsetzt, in Olympiaden und in Übungen zur dynamischen Programmierung auf. Diese Fähigkeit akzeptiert eine nichtnegative ganze Zahl n und liefert das exakte q(n) als Dezimalzeichenkette, berechnet mit 0-1-Dynamikprogrammierung in BigInt, sodass Werte jenseits sicherer Ganzzahlen ziffernweise korrekt bleiben. Ein negatives n wird mit einem klaren Validierungsfehler abgelehnt statt mit einem stillen Nullwert oder einer falschen Antwort.

Wie Partitionen mit verschiedenen Teilen definiert und gezählt werden

Eine Partition einer nichtnegativen ganzen Zahl n in verschiedene Teile ist eine Schreibweise von n als Summe positiver ganzer Zahlen, in der kein Teil wiederholt wird und die Reihenfolge der Summanden unerheblich ist. Konventionsgemäß ist q(0) gleich eins und zählt die leere Partition der Null. Klassische Lehrbuchwerte sind q(1)=1 (nämlich 1), q(2)=1 (nämlich 2), q(3)=2 (3 und 2+1), q(4)=2 (4 und 3+1), q(5)=3 (5, 4+1, 3+2), q(6)=4 und q(10)=10.

Die gewöhnliche erzeugende Funktion der Folge ist das unendliche Produkt über k größer oder gleich eins von eins plus x hoch k; das kodiert, dass jede positive ganze Zahl null- oder genau einmal als Teil vorkommen darf.

Ein praktischer Algorithmus in Software ist das klassische 0-1-Rucksack-Dynamikprogramm: initialisieren Sie ein Array mit einer Weise, die Summe null zu bilden, und gehen Sie für jede Teilgröße von eins bis n das Array der Restsummen von n abwärts bis zu dieser Größe und addieren die Weisen ohne den Teil zu den Weisen mit dem Teil. Die absteigende Richtung stellt sicher, dass jeder Teil höchstens einmal genutzt wird, sodass uneingeschränkte Mehrfachnutzung nie vorkommt.

Verwandte, aber andere Objekte sind uneingeschränkte Partitionen p(n), bei denen Teile wiederholt werden dürfen; Kompositionen, bei denen die Reihenfolge zählt; Mengenpartitionen, gezählt durch Stirling-Zahlen zweiter Art; und Partitionen nur in ungerade Teile, die Euler als gleichmächtig zu Partitionen mit verschiedenen Teilen für jedes n bewies. Diese Implementierung nutzt keine Gleitkomma-Näherung, kein Monte-Carlo-Sampling und keine externen Tabellen: sie füllt ein eindimensionales BigInt-Array, damit jede Ziffer korrekt ist. Der Pfad ist vollständig deterministisch — ohne Zufallsseeds, Uhren, Netz und ohne Modelldrift —, sodass dasselbe n immer dieselbe Zeichenkette liefert.

Wo Partitionen mit verschiedenen Teilen in der Praxis vorkommen

Zahlentheorie-Kurse und Programmierwettbewerbe fragen ständig, wie viele Partitionen von n paarweise verschiedene Summanden nutzen, wie diese Zählung mit uneingeschränktem p(n) verglichen wird oder ob eine Tabelle kleiner Werte mit Eulers Identität zu Partitionen in ungerade Teile übereinstimmt. Algorithmendesigner nutzen Zählungen mit verschiedenen Teilen bei der Analyse von Zustandsräumen im Stil von 0-1-Subset-Sum, beim Zählen von Kombinationen einzigartiger Ressourcengrößen, die ein Budget ergeben, oder beim Dimensionieren von DP-Tabellen, deren Dimensionen Teilgrößen mit höchstens einmaliger Nutzung verfolgen.

Kombinatorik- und erzeugende-Funktionen-Unterricht verknüpft q(n) mit dem Produkt aus eins plus x hoch k und mit eingeschränkten Identitäten vom Rogers–Ramanujan-Typ; Lehrende listen oft die verschiedenen Partitionen eines kleinen n und fragen dann nur nach der Zählung. Interviewvorbereitung und Olympiadentraining brauchen häufig ein einziges zuverlässiges q(n), ohne Tabellen von Hand zu pflegen oder versehentlich Kompositionen oder uneingeschränkte Partitionen zu zählen.

Wenn Sie später uneingeschränktes p(n), Kompositionen mit Ordnungsrelevanz, Mengenpartitionen über Stirling zweiter Art oder eine explizite Liste jeder Partition mit verschiedenen Teilen statt der Zählung brauchen, behandeln Sie diese als getrennte Suchintentionen und überladen Sie diese Landingpage nicht. Halten Sie n innerhalb der dokumentierten Grenze, damit die Latenz der Free-Tier vorhersehbar bleibt, und bevorzugen Sie String-Verbraucher für den Rückgabewert, weil q(n) bei großen Argumenten den sicheren Ganzzahlbereich verlässt.