Rechner für Stirling-Zahlen (zweiter Art)

Formel

How this is calculated

Gib zwei nichtnegative Ganzzahlen ein: n, die Anzahl der verschiedenen (beschrifteten) Objekte, und k, die Anzahl der nichtleeren Teilmengen, in die du sie aufteilen möchtest. Die Teilmengen selbst sind unbeschriftet, sodass nur die Gruppierung zählt, nicht die Reihenfolge der Gruppen.

Der Rechner verwendet die klassische Rekursion S(n, k) = k · S(n−1, k) + S(n−1, k−1). Anschaulich: wenn du das n-te Objekt hinzufügst, legst du es entweder in eine der k bestehenden Teilmengen (k · S(n−1, k) Möglichkeiten) oder beginnst eine brandneue Teilmenge mit ihm allein (S(n−1, k−1) Möglichkeiten). Die Basisfälle sind S(0,0) = 1 (eine Möglichkeit, nichts in nichts zu partitionieren) und S(n,0) = 0 für n > 0, und S(n,k) = 0, wann immer k > n. Die Rekursion wird aus Effizienzgründen mit dynamischer Programmierung über eine einzige Zeile ausgewertet.

Das Balkendiagramm zeigt S(n, k) für jedes k von 1 bis n, und ihre Summe ist die Bell-Zahl B(n), die Gesamtzahl der Partitionen einer n-elementigen Menge. Die Ergebnisse sind exakte Ganzzahlen; die Eingaben sind auf n ≤ 170 begrenzt, sodass die Anzahlen im Bereich der doppelten Genauigkeit bleiben. Nicht ganzzahlige Eingaben werden auf die nächste Ganzzahl gerundet.