Partitionen in ungerade oder verschiedene Teile

Dieser Rechner liefert die exakte Anzahl der Möglichkeiten, eine nicht negative ganze Zahl n als Summe positiver ungerader Zahlen zu schreiben, wobei die Reihenfolge keine Rolle spielt. Eulers Partitionssatz besagt, dass dieselbe Zahl auch die Partitionen zählt, deren Teile sämtlich verschieden sind. Geben Sie eine ganze Zahl ein, um ein exaktes Dezimalergebnis statt einer Gleitkommanäherung zu erhalten. Die Berechnung ist deterministisch, benötigt kein Netzwerk und wertet die leere Partition von null als eine gültige Partition.

Was der Rechner zählt

Eine Partition stellt eine ganze Zahl als Summe positiver ganzer Zahlen dar, ohne die Reihenfolge der Summanden zu beachten. Eine Umkehrung derselben Summanden erzeugt daher keine neue Partition. Dieser Rechner beschränkt die erste Sichtweise auf ungerade Teile: Jeder Summand muss ungerade sein, ein ungerader Wert darf jedoch mehrfach vorkommen.

Gleichzeitig beantwortet er die Frage nach Partitionen in verschiedene Teile, bei denen keine positive ganze Zahl zweimal vorkommt. Beide Familien sind für jedes nicht negative n gleich groß, auch wenn ihre einzelnen Elemente meist anders aussehen. Das Ergebnis eignet sich deshalb für Aufgaben mit ungeraden oder mit nicht wiederholten Summanden.

Für n gleich null lautet es eins, entsprechend der üblichen leeren Summe. Negative Werte werden abgelehnt, weil gewöhnliche Partitionen hier nur für nicht negative Zielwerte definiert sind.

Warum ungerade und verschiedene Teile übereinstimmen

Eulers Satz lässt sich mit erzeugenden Funktionen oder einer direkten Umformung verstehen. Beliebig viele Exemplare jedes ungeraden Teils ergeben ein Produkt mit einem geometrischen Faktor für jede ungerade Zahl. Verschiedene Teile ergeben ein Produkt, in dem jede positive ganze Zahl genau einmal gewählt oder ausgelassen wird.

Beide Produkte besitzen dieselben Koeffizienten; der zu n gehörende Koeffizient liefert somit dieselbe Anzahl. Eine Bijektion trennt außerdem wiederholt Zweierpotenzen aus gleichen ungeraden Teilen und verbindet gleiche Kopien zu verschiedenen Teilen, ohne die Summe zu ändern. Dieser Vorgang ist umkehrbar.

Die Implementierung zählt die Seite der verschiedenen Teile mittels dynamischer Programmierung. Sie besucht jeden möglichen Teil einmal und aktualisiert Zielsummen absteigend. Dadurch kann ein Teil während seines eigenen Durchlaufs nicht erneut verwendet werden.

Exakte BigInt-Arithmetik bewahrt jede Ziffer, anschließend wird die ganze Zahl für eine zuverlässige Übertragung als Dezimalzeichenfolge serialisiert.

Ergebnis verwenden und auslegen

Geben Sie n als nicht negative ganze Zahl zwischen null und der veröffentlichten Grenze an. Die Antwort wiederholt n und liefert in count die exakte Anzahl der passenden Partitionen. Sie müssen keinen Modus für ungerade oder verschiedene Teile wählen, da Eulers Identität die Gleichheit beider Anzahlen garantiert.

Damit können Sie kombinatorische Aufgaben prüfen, Koeffiziententabellen validieren, symbolischen Code für erzeugende Funktionen testen oder Referenzwerte für ein anderes deterministisches Programm erzeugen. Die Ausgabe zählt ungeordnete Partitionen und keine Kompositionen: Eine andere Reihenfolge derselben Terme ist kein weiterer Fall. Wiederholungen sind in der Deutung mit ungeraden Teilen erlaubt, in der Deutung mit verschiedenen Teilen jedoch verboten.

Bewahren Sie große Antworten als Zeichenfolgen auf, sofern Ihr Zielsystem keine Ganzzahlen beliebiger Genauigkeit unterstützt. Brüche, fehlende Eingaben, Werte oberhalb der Grenze und negative Zahlen führen zu einem typisierten Eingabefehler.