Stirling-Zahlen-Rechner
Erste Art · Zweite Art · Bell-Zahlen · Dreieckstabellen
Berechnen Sie S(n,k) für Mengenpartitionen, s(n,k) für Permutationszyklen und B(n) für Bell-Zahlen – mit vollständigen Rekursionsschritten und Dreieckstabellen.
Schnellbeispiele
Verwendete Rekursionsformeln
S(n,k) = k·S(n-1,k) + S(n-1,k-1)
S(0,0)=1 S(n,0)=0 S(0,k)=0
s(n,k) = (n-1)·s(n-1,k) + s(n-1,k-1)
s(0,0)=1 s(n,0)=0 s(0,k)=0
Zweite ArtRekursion für S(n,k) Schritt für Schritt
| n \ k | k-Spalten |
|---|
Erste ArtRekursion für s(n,k) Schritt für Schritt
| n \ k | k-Spalten |
|---|
Zweite ArtStirling-Zahlen S(n,k) — Dreieck
Anzahl der Partitionen von n Elementen in k nichtleere Teilmengen.
Erste ArtStirling-Zahlen s(n,k) — Dreieck
Anzahl der Permutationen von n Elementen mit genau k Zyklen.
BellBell-Zahlen von B(0) bis B(n)
| n | B(n) | = Summe S(n,k) | Bedeutung |
|---|
Bell-Dreieck (Aitkens Schema)
Jede Zeile beginnt mit dem letzten Element der vorherigen Zeile. Jedes weitere Element ist die Summe des linken Elements und des Elements links darüber. Das erste Element jeder Zeile ist eine Bell-Zahl.
Bell-Zahlen-Formeln
B(n+1) = ∑k=0n C(n,k) · B(k) (Rekursion über Binomialkoeffizienten)
B(0)=1, B(1)=1, B(2)=2, B(3)=5, B(4)=15, B(5)=52, B(6)=203
Was sind Stirling-Zahlen?
Stirling-Zahlen sind zwei Familien ganzer Zahlen aus der Kombinatorik. Sie beschreiben Mengenpartitionen und die Zyklenstruktur von Permutationen. Benannt sind sie nach dem schottischen Mathematiker James Stirling, der sie im 18. Jahrhundert systematisch untersuchte.
Stirling-Zahlen zweiter Art — S(n,k)
S(n,k) zählt die Möglichkeiten, eine Menge aus n verschiedenen Elementen in genau k nichtleere, ungeordnete Teilmengen zu zerlegen. Die zentrale Rekursion lautet:
S(n,k) = k · S(n-1,k) + S(n-1,k-1)
Das n-te Element wird entweder in eine der k vorhandenen Gruppen eingefügt oder bildet eine neue Einzelgruppe. Es gelten S(0,0)=1 und S(n,0)=S(0,k)=0 für positive n und k.
Stirling-Zahlen erster Art — s(n,k)
Die vorzeichenlose Stirling-Zahl erster Art s(n,k) zählt Permutationen von n Elementen mit genau k disjunkten Zyklen. Ihre Rekursion ist:
s(n,k) = (n-1) · s(n-1,k) + s(n-1,k-1)
Das neue Element wird an einer von n−1 Stellen in einen vorhandenen Zyklus eingefügt oder bildet einen eigenen Zyklus.
Bell-Zahlen — B(n)
Die Bell-Zahl B(n) zählt alle Partitionen einer n-elementigen Menge. Sie ist die Summe der Stirling-Zahlen zweiter Art einer Zeile:
B(n) = S(n,0) + S(n,1) + ··· + S(n,n)
Die Folge beginnt mit 1, 1, 2, 5, 15, 52, 203, 877 und 4140. Bell-Zahlen treten in der Wahrscheinlichkeitstheorie, Clusteranalyse und algebraischen Kombinatorik auf.
Verbindung zu fallenden Fakultäten
- Stirling-Zahlen zweiter Art stellen gewöhnliche Potenzen als Summen fallender Fakultäten dar.
- Stirling-Zahlen erster Art führen die umgekehrte Transformation aus.
- Vorzeichenbehaftete Werte erster Art unterscheiden sich durch den Faktor (−1)n−k.
Anwendungen
- Mengen in Gruppen oder Klassen aufteilen
- Permutationen nach ihrer Zyklenzahl zählen
- Momente von Wahrscheinlichkeitsverteilungen bestimmen
- Belegungsprobleme und erzeugende Funktionen untersuchen
James Stirling
James Stirling (1692–1770) veröffentlichte 1730 sein Werk Methodus Differentialis. Neben den nach ihm benannten Zahlen ist er für die Stirling-Näherung bekannt, mit der das Wachstum der Fakultät präzise abgeschätzt wird.