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 $\left[\right]$ Klammer geschrieben, Stirlingzahlen der zweiten Art werden mit großen S oder Mengenklammern $\left\{\right\}$ geschrieben:

$s(n,r)=\left[{\begin{matrix}n\\r\end{matrix}}\right].$

$S(n,r)=S_{n}^{(r)}=\left\{{\begin{matrix}n\\r\end{matrix}}\right\}.$

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 $s\left(n,r\right)$ beschreibt die Anzahl der unterschiedlichen Möglichkeiten eine Permutation mit $n$ Elementen in $r$ Zyklen zu zerlegen.

Beispiel:

Die Menge $M\lbrace a,b,c,d\rbrace$ mit $\left|M\right|=n=4$ kann auf folgende Weise in zwei Zyklen $(r=2)$ zerlegt werden:

$\lbrace a,b,c\rbrace ,\lbrace d\rbrace$

$\lbrace a,c,b\rbrace ,\lbrace d\rbrace$

$\lbrace a,b,d\rbrace ,\lbrace c\rbrace$

$\lbrace a,d,b\rbrace ,\lbrace c\rbrace$

$\lbrace a,c,d\rbrace ,\lbrace b\rbrace$

$\lbrace a,d,c\rbrace ,\lbrace b\rbrace$

$\lbrace a\rbrace ,\lbrace b,c,d\rbrace$

$\lbrace a\rbrace ,\lbrace b,d,c\rbrace$

$\lbrace a,b\rbrace ,\lbrace c,d\rbrace$

$\lbrace a,c\rbrace ,\lbrace b,d\rbrace$

$\lbrace a,d\rbrace ,\lbrace b,c\rbrace$

$s\left(4,2\right)=11$

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

$s\left(n,r\right)=s\left(n-1,r-1\right)+\left(n-1\right)s\left(n-1,r\right)$

mit den Anfangsbedingungen

$s\left(0,0\right)=1$

$s\left(n,0\right)=0\qquad \forall n>0$

$s\left(0,r\right)=0\qquad \forall r>0$

Stirling Zahlen zweiter Art

Die Stirling Zahl zweiter Art $S\left(n,r\right)$ beschreibt die Anzahl der unterschiedlichen Möglichkeiten aus einer Menge mit $n$ Elementen $r$ nicht leere Partitionen (Zerlegungen) zu bilden.

Beispiel:

Die Menge $M\lbrace a,b,c,d\rbrace$ mit $\left|M\right|=n=4$ kann auf folgende Weise in zwei Partitionen $(r=2)$ zerlegt werden:

$\lbrace a,b\rbrace ,\lbrace c,d\rbrace$

$\lbrace a,c\rbrace ,\lbrace b,d\rbrace$

$\lbrace a,d\rbrace ,\lbrace b,c\rbrace$

$\lbrace a,b,c\rbrace ,\lbrace d\rbrace$

$\lbrace a,b,d\rbrace ,\lbrace c\rbrace$

$\lbrace b,c,d\rbrace ,\lbrace a\rbrace$

$\lbrace a,c,d\rbrace ,\lbrace b\rbrace$

$S\left(4,2\right)=7$

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

$S\left(n,r\right)=S\left(n-1,r-1\right)+rS\left(n-1,r\right)$

mit den Anfangsbedingungen

$S\left(0,0\right)=1$

$S\left(n,0\right)=0\qquad \forall n>0$

$S\left(0,r\right)=0\qquad \forall r>0$

Explizite Formel

$S(n,r)={\frac {1}{r!}}\sum _{j=1}^{r}(-1)^{r-j}{r \choose j}j^{n}$

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 $\lbrace a\rbrace$ selber eine Klasse der Partition bildet oder nicht.

Trifft dies zu, so kann man aus $M\lbrace a\rbrace \left(M\setminus a\right)$ nur noch $r-1$ Partitionen aus $n-1$ Elementen bilden, also $S\left(n-1,r-1\right)$.

Bildet $\left\{a\right\}$ keine Klasse, so bedeutet dies, dass es $r$ Partitionen aus $n-1$ Elementen gibt, also $S\left(n-1,r\right)$. Da $a$ nun Element einer der Partitionen ist, es aber dafür $r$ Möglichkeiten gibt, ergibt sich die Multiplikation von $S\left(n-1,r\right)$ mit $r$.

$S\left(n,r\right)=S\left(n-1,r-1\right)+rS\left(n-1,r\right)$

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)$\cdots$(x-n+1), ... und p₀(x)=1, p₁(x)=x, ..., p_n(x)= $x^{n}$, ... Basen für V_m. So gelten folgende Beziehungen:

1. $q_{n}(x)=\sum _{k=0}^{n}s(n,k)p_{k}(x)$

2. $p_{n}(x)=\sum _{k=0}^{n}S(n,k)q_{k}(x)$

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.

$\left[{\begin{matrix}n\\k\end{matrix}}\right]=\left[{\begin{matrix}n-1\\k-1\end{matrix}}\right]+(n-1)\left[{\begin{matrix}n-1\\k\end{matrix}}\right]$

$\left\{{\begin{matrix}n\\k\end{matrix}}\right\}=\left\{{\begin{matrix}n-1\\k-1\end{matrix}}\right\}+k\left\{{\begin{matrix}n-1\\k\end{matrix}}\right\}$

Für Binomialkoeffizienten gilt bekanntlich

$\left({\begin{matrix}n\\k\end{matrix}}\right)=\left({\begin{matrix}n-1\\k-1\end{matrix}}\right)+\left({\begin{matrix}n-1\\k\end{matrix}}\right)$.

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