Stirling-Zahlen zweiter Art

Stirling-Zahlen zweiter Art beantworten eine grundlegende Zählfrage der diskreten Mathematik: Gegeben n verschiedene Objekte, auf wie viele Arten können Sie sie in genau k nichtleere unbeschriftete Gruppen partitionieren? Die Antwort schreibt man S(n,k) oder manchmal {n choose k} mit geschweiften Klammern. Diese Zahlen treten auf, wenn Sie Personen in Teams ohne Teamnamen gruppieren, einen Schlüsselsatz in unbeschriftete Eimer teilen, surjektive Funktionen bis auf einen Faktorfaktor zählen, Bell-Zahlen als Summe über k bilden oder Hausaufgaben bewerten, die Mengenpartitionen statt Permutationen verlangen. Diese Fähigkeit akzeptiert nichtnegative Ganzzahlen n (Elementanzahl) und k (Anzahl nichtleerer Teilmengen) und liefert das exakte S(n,k) als Dezimalzeichenkette, berechnet mit BigInt-Dynamikprogrammierung, sodass Werte weit jenseits gewöhnlicher Safe-Integer-Grenzen zifferngenau korrekt bleiben. Eingaben mit negativem k oder mit k größer als n werden mit einem klaren Validierungsfehler abgelehnt statt eines stillen Nulls oder einer falschen Antwort.

So sind Stirling-Zahlen zweiter Art definiert

Eine Stirling-Zahl zweiter Art S(n,k) zählt die Partitionen einer n-elementigen Menge in genau k nichtleere unbeschriftete Teilmengen. Die Reihenfolge innerhalb einer Teilmenge spielt keine Rolle, und die Teilmengen selbst sind nicht geordnet: die Partition {{1,2},{3}} ist dieselbe wie {{3},{1,2}}. Die Standardrekurrenz ist S(n,k) = k · S(n−1,k) + S(n−1,k−1).

Intuitiv: wenn Sie das neueste Element n hinzufügen, bildet es entweder ein eigenes Singleton (dann bilden die restlichen n−1 Elemente k−1 Teilmengen, gezählt durch S(n−1,k−1)), oder es tritt einer der k bestehenden Teilmengen in einer Partition der ersten n−1 Elemente in k Blöcke bei (k Wahlen, mal S(n−1,k)). Basisfälle, die die Tabelle schließen, sind S(0,0) = 1, S(n,0) = 0 für n > 0, S(0,k) = 0 für k > 0, S(n,1) = 1 und S(n,n) = 1.

Klassische Lehrbuchprüfungen umfassen S(3,2) = 3, S(4,2) = 7, S(5,2) = 15 und S(5,3) = 25. Die Bell-Zahl B_n, die Gesamtzahl der Partitionen einer n-Menge mit beliebiger Blockzahl, ist die Summe von S(n,k) über k von null bis n. Verwandte, aber andere Objekte umfassen Stirling-Zahlen erster Art (die Permutationen nach Zykluszahl verfolgen) und Binomialkoeffizienten (die Elemente wählen, ohne den Rest zu partitionieren).

Diese Implementierung nutzt nie Gleitkomma-Näherung, Monte-Carlo-Sampling oder externe Tabellen: sie füllt eine Dynamikprogrammierungszeile mit exakter BigInt-Arithmetik, sodass jede Ziffer korrekt ist. Der Pfad ist vollständig deterministisch — ohne Zufallsseeds, Uhren, Netz und Modell-Drift — sodass dieselben n und k stets dieselbe Zeichenkette ergeben.

Wo Stirling-Zählungen zweiter Art in der Praxis vorkommen

Kombinatorik-Kurse und Programmierwettbewerbe fragen ständig, auf wie viele Arten man n beschriftete Personen in k unbeschriftete Teams teilen, wie viele Äquivalenzrelationen auf n Elementen genau k Klassen haben, oder auf wie viele Arten man n verschiedene Geschenke in k identische nichtleere Kisten verteilen kann — alles gleich S(n,k). Algorithmendesigner nutzen Stirling-Tabellen zweiter Art bei der Analyse von Mengenpartitions-Datenstrukturen, Clustering-Skizzen mit fester Clusterzahl oder beim Zählen der Wege, wie ein rekursiver Prozess Zwischenergebnisse gruppieren kann.

Wahrscheinlichkeits- und Statistikkurse verbinden S(n,k) mit der Anzahl der Wege, n verschiedene Ausgänge k nichtleeren unbeschrifteten Eimern zuzuweisen, und mit der geschlossenen Form der Anzahl der Surjektionen von einer n-Menge auf eine k-Menge, die k! · S(n,k) ist. Lehrkräfte und Interviewvorbereitung zeigen oft ein kurzes Dreieck kleiner S(n,k)-Werte; einen einzelnen Eintrag in einem Aufruf zu berechnen hält interaktive Demos mit Lehrbüchern und Lösungsschlüsseln ausgerichtet, ohne große Tabellen von Hand zu pflegen.

Wenn Sie später Stirling-Zahlen erster Art, nur Bell-Zahlen, Surjektionszählungen mit bereits angewandtem k!-Faktor oder eine explizite Partitionsliste statt der Zählung brauchen, behandeln Sie diese als getrennte Suchabsichten statt diese Seite zu überladen.