Partitionsfunktion

Die Partitionsfunktionen geben die Anzahl der Möglichkeiten an, positive, ganze Zahlen in positive, ganze Summanden zu zerlegen. Üblicherweise betrachtet man die Zerlegungen ohne Berücksichtigung der Reihenfolge. Jede solche Zerlegung wird in der Kombinatorik als (ungeordnete) Zahlpartition^[2] oder manchmal kurz Partition^[2] bezeichnet. Die Bestimmung aller Zahlpartitionen für eine bestimmte (große) natürliche Zahl ist ein wichtiges Problem sowohl in der theoretischen als auch der praktischen Informatik. Siehe dazu den Artikel Partitionierungsproblem.

Die Partitionsfunktion ohne Nebenbedingungen (Anzahl der ungeordneten Zahlpartitionen von ${\displaystyle n}$) wird als ${\displaystyle P(n)}$, manchmal auch als ${\displaystyle p(n)}$ notiert und ist Folge A000041 in OEIS. Es gibt eine Reihe von Funktionen, bei denen an die Summanden zusätzliche Bedingungen gestellt werden, zum Beispiel dass jeder Summand nur einmal vorkommen darf (strikte Zahlpartitionen). Diese Variante wird ebenfalls Partitionsfunktion, manchmal auch strikte Partitionsfunktion genannt, als ${\displaystyle Q(n)}$ oder ${\displaystyle q(n)}$ notiert und ist Folge A000009 in OEIS.^[3]

Mit einer aus der Partitionsfunktion ${\displaystyle P(n)}$ abgeleiteten zahlentheoretischen Funktion kann die Anzahl der Isomorphietypen für die endlichen abelschen Gruppen angegeben werden.

1. ↑ Florian Scheck: Theoretische Physik 5: Statistische Theorie der Wärme. Springer, 2008, ISBN 978-3-540-79823-1, S. 98 (eingeschränkte Vorschau in der Google-Buchsuche). 
2. ↑ ^{a b} Matoušek, Nešetřil (2002)
3. ↑ Eric W. Weisstein: Partition Function Q. In: MathWorld (englisch).