Online-Bibliothek

Stirling-Zahl

Die Stirling-Zahlen erster und zweiter Art, benannt nach James Stirling, werden in der Kombinatorik und der theoretischen Informatik verwendet.

Notation

Für die Stirlingzahlen existieren mehrere Notationsvarianten nebeneinander. Stirlingzahlen der ersten Art werden mit einem kleinen s geschrieben oder mit Klammer geschrieben, Stirlingzahlen der zweiten Art werden mit großen S oder Mengenklammern geschrieben:

Die Klammernotation wurde 1935 von Jovan Karamata in Analogie zu den Binomialkoeffizienten eingeführt und später von Donald Knuth populär gemacht. Die Klammernotation wird auch Karamata-Notation genannt.

Stirling Zahlen erster Art

Die Stirling Zahl erster Art beschreibt die Anzahl der unterschiedlichen Möglichkeiten eine Permutation mit n Elementen in r Zyklen zu zerlegen.

Beispiel:

Die Menge M{a,b,c,d} mit kann auf folgende Weise in zwei Zyklen (r = 2) zerlegt werden:

[a,b,c],[d]

{a,c,b},{d}

{a,b,d},{c}

{a,d,b},{c}

{a,c,d},{b}

{a,d,c},{b}

{a},{b,c,d}

{a},{b,d,c}

{a,b},{c,d}

{a,c},{b,d}

{a,d},{b,c}

Da das Aufschreiben aller möglichen Zyklen recht aufwendig ist und mit der Anzahl der Elemente immer unübersichtlicher wird, gibt es eine rekursive Formel, um s(n,r) zu berechnen:

mit den Anfangsbedingungen

Stirling Zahlen zweiter Art

Die Stirling Zahl zweiter Art beschreibt die Anzahl der unterschiedlichen Möglichkeiten aus einer Menge mit n Elementen r nichtleere, disjunkte Teilmengen zu bilden. Jede solche Möglichkeit ist eine Partition mit r Teilmengen.

Beispiel:

Die Menge M = {a,b,c,d} mit kann auf folgende Weise in r = 2 nichtleere, disjunkte Teilmengen zerlegt werden:

{a,b},{c,d}

{a,c},{b,d}

{a,d},{b,c}

{a,b,c},{d}

{a,b,d},{c}

{b,c,d},{a}

{a,c,d},{b}

Da das Aufschreiben aller möglichen Partitionen recht aufwendig ist und mit der Anzahl der Elemente immer unübersichtlicher wird, gibt es eine rekursive Formel, um S(n,r) zu berechnen:

mit den Anfangsbedingungen

Explizite Formel

Beispiele

S(10,4) = 34.105;S(19,4) = 11.259.666.950

Beweis

Sei a ein fest gewähltes Element der n-elementigen Menge M. Die r Partitionen von M können nun danach klassifiziert werden, ob {a} selber eine Klasse der Partition bildet oder nicht.

Trifft dies zu, so kann man aus nur noch r − 1 Partitionen aus n − 1 Elementen bilden, also .

Bildet keine Klasse, so bedeutet dies, dass es r Partitionen aus n − 1 Elementen gibt, also . Da a nun Element einer der Partitionen ist, es aber dafür r Möglichkeiten gibt, ergibt sich die Multiplikation von mit r.

Alternative Herleitung

Seien V der Vektorraum aller reell- oder komplexwertigen Polynome und V_m der Unterraum der Polynome mit exaktem Grad m. Weiterhin seien q₀(x)=1, q₁(x)=x, ..., q_n(x)= x(x-1)(x-n+1), ... und p₀(x)=1, p₁(x)=x, ..., p_n(x)= xⁿ, ... Basen für V_m. So gelten folgende Beziehungen:

1.

2.

So können alternativ die Stirling-Zahlen 1. und 2. Art erzeugt werden, mit dem Unterschied, dass hier durchaus andere Vorzeichen auftreten, als in den zuvor gegebenen Definitionen.

Analogie zu den Binomialkoeffizienten

Bei Verwendung der Karamatanotation sticht bei Betrachtung der Rekursionsformeln für die Stirlingzahlen der ersten und zweiten Art die Analogie zu den Binomialkoeffizienten ins Auge.

Für Binomialkoeffizienten gilt bekanntlich

.

Entsprechend lassen sich die Stirling-Zahlen in einem Dreiecksschema ähnlich dem pascalschen Dreieck anordnen:

                                 1
                              1     1
                           1     3     1
                        1     7     6     1
                     1     15     25     10   1
                  1     31     90    65    15    1
               1     ..    ..     ..    ..    ..    1

Literatur

• Manfred Wolff, Peter Hauck, Wolfgang Küchlin: Mathematik für Informatik und BioInformatik. Springer-Verlag, Berlin Heidelberg New-York, S.50, ISBN 3-540-20521-7