Rechner für Zahlpartitionen

Über diesen Rechner

Eine Partition einer positiven ganzen Zahl n ist eine Darstellung als Summe positiver ganzer Zahlen, bei der die Reihenfolge keine Rolle spielt – 4 lässt sich zum Beispiel als 4, 3+1, 2+2, 2+1+1 oder 1+1+1+1 zerlegen, was p(4) = 5 ergibt. Dieser Rechner berechnet p(n) mit einer Rekursion der dynamischen Programmierung, die alle solchen verschiedenen Summen zählt, für jedes n von 0 bis 250.

Mathematiker und Studierende der Kombinatorik nutzen Partitionszahlen als grundlegendes Thema der Zahlentheorie, und die zugrunde liegende Rekursion taucht auch in der Informatik auf – Wettbewerbsprogrammierer setzen Algorithmen zum Zählen von Partitionen bei Aufgaben zu Münzwechsel-Kombinationen, erzeugenden Funktionen und anderen kombinatorischen Zählproblemen ein.