Stirling-Zahlen-Rechner

Willkommen beim Stirling-Zahlen-Rechner, einem umfassenden Kombinatorik-Tool zur Berechnung von Stirling-Zahlen der ersten Art (vorzeichenlos — Permutationen in Zyklen) und der zweiten Art (Mengenpartitionen in nicht-leere Teilmengen). Mit interaktiven Dreiecksvisualisierungen, Schritt-für-Schritt-Rekursionsherleitungen, Balkendiagramm-Verteilungen und tiefgehenden kombinatorischen Interpretationen ist dieser Rechner für Studenten, Lehrer, Forscher und Programmierer konzipiert, die schnelle, genaue Ergebnisse im pädagogischen Kontext benötigen.

Was sind Stirling-Zahlen?

Stirling-Zahlen sind zwei Zahlenfamilien, die natürlicherweise in der Kombinatorik, Algebra und Analysis vorkommen. Benannt nach dem schottischen Mathematiker James Stirling (1692–1770), schlagen sie die Brücke zwischen Fakultäten, Binomialkoeffizienten und Polynomidentitäten. Obwohl sie weniger bekannt sind als das Pascalsche Dreieck, sind sie ebenso fundamental und tauchen in der gesamten diskreten Mathematik auf.

Stirling-Zahlen erster Art

Die vorzeichenlosen Stirling-Zahlen erster Art, bezeichnet als \(|s(n,k)|\) oder \(\left[{n \atop k}\right]\), geben die Anzahl der Permutationen von \(n\) Elementen an, die in genau \(k\) disjunkte Zyklen zerfallen.

Intuition: Überlegen Sie, wohin das Element \(n\) geht. Entweder wird es in einen der bestehenden Zyklen eingefügt (es gibt \(n-1\) Positionen zum Einfügen, eine vor jedem der \(n-1\) anderen Elemente) — was zum Term \((n-1)\cdot|s(n-1,k)|\) führt — oder es bildet einen eigenen neuen 1-Zyklus, was \(|s(n-1,k-1)|\) beisteuert.

Wichtige Fakten:

• \(|s(n,1)| = (n-1)!\) — zyklische Permutationen (ein großer Zyklus)
• \(|s(n,n)| = 1\) — die identische Permutation (alles Fixpunkte)
• \(|s(n,n-1)| = \binom{n}{2}\) — eine Transposition
• \(\sum_{k=0}^{n} |s(n,k)| = n!\) — Gesamtzahl der Permutationen

Stirling-Zahlen zweiter Art

Die Stirling-Zahlen zweiter Art, bezeichnet als \(S(n,k)\) oder \(\left\{{n \atop k}\right\}\), geben die Anzahl der Möglichkeiten an, eine Menge von \(n\) Elementen in genau \(k\) nicht-leere Teilmengen zu partitionieren.

Intuition: Überlegen Sie, wohin das Element \(n\) geht. Entweder tritt es einer der \(k\) bestehenden Teilmengen bei (\(k\) Möglichkeiten) — was zum Term \(k \cdot S(n-1,k)\) führt — oder es bildet eine eigene neue einelementige Teilmenge, was \(S(n-1,k-1)\) beisteuert.

Wichtige Fakten:

• \(S(n,1) = 1\) — nur ein Weg: alle Elemente in einer Menge
• \(S(n,n) = 1\) — nur ein Weg: jedes Element ist eine eigene Teilmenge
• \(S(n,2) = 2^{n-1} - 1\) — Wege zur Aufteilung in zwei nicht-leere Teilmengen
• \(S(n,n-1) = \binom{n}{2}\) — Auswahl des Paares, das sich eine Teilmenge teilt
• \(\sum_{k=0}^{n} S(n,k) = B(n)\) — die \(n\)-te Bell-Zahl

Explizite Formel (Zweite Art)

Anwendung des Rechners

1. n eingeben: Die Gesamtzahl der Elemente (0 bis 200).
2. k eingeben: Die Anzahl der Zyklen (erste Art) oder Teilmengen (zweite Art), wobei 0 ≤ k ≤ n.
3. Art auswählen: Wählen Sie erste Art, zweite Art oder beides für einen direkten Vergleich.
4. Berechnen: Klicken Sie auf "Stirling-Zahlen berechnen", um Ergebnisse mit Herleitung, Dreieck und Diagramm zu sehen.

Vergleich: Erste Art vs. Zweite Art

Anwendungen von Stirling-Zahlen

Polynomumwandlung

Stirling-Zahlen verbinden verschiedene Polynombasen:

• Steigende Faktorielle: \(x^{(n)} = \sum_{k} |s(n,k)|\, x^k\)
• Gewöhnliche Potenz: \(x^n = \sum_{k} S(n,k)\, x^{\underline{k}}\) (fallende Faktorielle)

Wahrscheinlichkeit und Statistik

Stirling-Zahlen erscheinen bei der Berechnung von Momenten von Wahrscheinlichkeitsverteilungen, insbesondere bei der Umrechnung zwischen gewöhnlichen und faktoriellen Momenten. Sie sind essenziell in der Analyse von Zufallspermutationen.

Informatik

In der Algorithmenanalyse tauchen Stirling-Zahlen beim Zählen von Möglichkeiten auf, Objekte in Behälter zu verteilen, bei der Analyse von Hash-Tabellen und beim Studium von Zufallspermutationen. Die zweite Art steht in direktem Zusammenhang mit der Zählung surjektiver Funktionen: Die Anzahl der surjektiven Funktionen von einer n-Menge in eine k-Menge ist \(k!\, S(n,k)\).

Zahlentheorie

Stirling-Zahlen hängen mit Bernoulli-Zahlen, harmonischen Zahlen und verschiedenen Summationsidentitäten zusammen. Sie erscheinen in der Differenzenrechnung und in der Euler-Maclaurin-Formel.

Häufig gestellte Fragen (FAQ)

Was sind Stirling-Zahlen erster Art?

Vorzeichenlose Stirling-Zahlen erster Art |s(n,k)| zählen Permutationen von n Elementen mit genau k disjunkten Zyklen. Sie folgen der Rekursion |s(n,k)| = (n−1)·|s(n−1,k)| + |s(n−1,k−1)|.

Was sind Stirling-Zahlen zweiter Art?

Stirling-Zahlen zweiter Art S(n,k) zählen die Partitionen einer n-elementigen Menge in genau k nicht-leere Teilmengen. Sie folgen der Rekursion S(n,k) = k·S(n−1,k) + S(n−1,k−1).

Was ist der Unterschied zwischen Stirling-Zahlen erster und zweiter Art?

Die erste Art (vorzeichenlos) zählt Permutationen mit k Zyklen (Reihenfolge im Zyklus wichtig), die zweite Art zählt Partitionen in k Teilmengen (Reihenfolge unwichtig). Sie sind über die Matrizeninversion miteinander verknüpft.

Wie werden Stirling-Zahlen in der Mathematik verwendet?

Sie werden zur Basisumwandlung von Polynomen, in der Kombinatorik, zur Momentenberechnung in der Statistik und zur Analyse von Algorithmen verwendet.

Wie ist das Verhältnis zwischen Stirling-Zahlen und Bell-Zahlen?

Die Bell-Zahl B(n) ist die Summe aller Stirling-Zahlen zweiter Art für ein festes n über alle möglichen k (0 bis n).

Gibt es eine explizite Formel für Stirling-Zahlen?

Ja, für die zweite Art existiert eine explizite Formel basierend auf dem Inklusions-Exklusions-Prinzip. Die erste Art wird meist rekursiv berechnet.

Zusätzliche Ressourcen

• Stirling Numbers of the First Kind - Wikipedia (Englisch)