Stirling-Zahl
# Stirling-Zahl

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

## Bezeichnung und Notation

Mit Hinweis auf eine bereits 1730 veröffentlichte Arbeit Stirlings, in der diese Zahlen untersucht werden, führte Niels Nielsen 1906 im Handbuch der Theorie der Gammafunktion die Bezeichnung „Stirlingsche Zahlen erster und zweiter Art“ ein („nombres de Stirling“ bereits in einem 1904 veröffentlichten Artikel).

Weder die Bezeichnung als Stirlingzahlen noch einheitliche Notationen haben sich durchgesetzt. In diesem Artikel werden Stirlingzahlen der ersten Art mit kleinem $s$ bezeichnet oder übereinander in eckigen Klammern geschrieben, Stirlingzahlen der zweiten Art mit großem $S$ bezeichnet oder übereinander in geschweiften Klammern geschrieben:

    $s_{n,k}=\left[{n \atop k}\right],\qquad S_{n,k}=\left\{{n \atop k}\right\}$.

Die Klammernotation, auch Karamata-Notation genannt, wurde 1935 von Jovan Karamata in Analogie zu den Binomialkoeffizienten ${\tbinom {n}{k}}$ eingeführt, 1992 setzte sich Donald Knuth mit einem ausführlichen Exkurs über die Stirling-Zahlen für diese Schreibweise ein.

## Stirling-Zahlen erster Art

Die Stirling-Zahl erster Art $s_{n,k}$ ist die Anzahl der Permutationen einer $n$-elementigen Menge, die genau $k$ Zyklen haben. Nach einer häufig verwendeten anderen Definition wird stattdessen $(-1)^{n-k}s_{n,k}$ als Stirling-Zahl erster Art bezeichnet.

### Beispiel

Die Menge $\{a,b,c,d\}$ mit $n=4$ Elementen kann auf folgende Weisen auf $k=2$ Zyklen aufgeteilt werden:

    $(abc)(d),{\text{ }}(acb)(d),{\text{ }}(abd)(c),{\text{ }}(adb)(c),{\text{ }}(acd)(b),{\text{ }}(adc)(b),{\text{ }}(bcd)(a),{\text{ }}(bdc)(a),{\text{ }}(ab)(cd),{\text{ }}(ac)(bd),{\text{ }}(ad)(bc)$

Also ist $s_{4,2}=11$. Für weitere Beispiele siehe Zykeltyp.

### Eigenschaften

Es gelten die expliziten Formeln

    $s_{n,k}=\!\!\!\sum _{0<i_{1}<i_{2}<\ldots <i_{n-k}<n}\!\!\!i_{1}i_{2}\cdots i_{n-k}=(n-1)!\!\!\!\sum _{0<j_{1}<j_{2}<\ldots <j_{k-1}<n}\!\!\!(j_{1}j_{2}\cdots j_{k-1})^{-1}$

und die rekursive Formel

    $s_{n+1,k}=s_{n,k-1}+n\,s_{n,k}$

mit den Anfangsbedingungen

    $s_{n,n}=1$ und
    $s_{n,k}=0$ für $k=0<n$ oder $n<k.$

Weitere spezielle Werte sind

* $s_{n,1}=(n-1)!$
* $s_{n,2}=(n-1)!\,H_{n-1},$ Folge A000254 in OEIS
* $s_{n,3}={\tfrac {1}{2}}\,(n-1)!\,(H_{n-1}^{2}-H_{n-1,2}),$ Folge A000399 in OEIS
* $s_{n,n-3}={\tbinom {n}{4}}{\tbinom {n}{2}}={\tfrac {1}{48}}\,n^{2}\,(n-1)^{2}\,(n-2)\,(n-3),$ Folge A001303 in OEIS
* $s_{n,n-2}={\tfrac {1}{24}}\,n\,(n-1)\,(n-2)\,(3n-1),$ Folge A000914 in OEIS
* $s_{n,n-1}={\tbinom {n}{2}}={\tfrac {1}{2}}\,n\,(n-1)$

für alle $n>0,$ wobei $H_{n-1}=1^{-1}+2^{-1}+...+(n-1)^{-1}$ die $(n-1)$-te harmonische Zahl und $H_{n-1,2}=1^{-2}+2^{-2}+...+(n-1)^{-2}$ eine verallgemeinerte harmonische Zahl ist.

Allgemein kann $s_{n,n-k}$ als Polynom in $n$ vom Grad $2k$ aufgefasst werden. Es hat den Leitkoeffizienten $1/(2^{k}k!)$ und enthält für alle $k>0$ die Faktoren n, n−1, …, n−k und für ungerade $k>1$ die Faktoren $n^2$ und $(n−1)^2.$ Das Polynom

    $\psi _{k}(n)=s_{n+1,n-k}/{\bigl(n+1)\,n\cdots (n-k){\bigr )}$

in $n$ vom Grad $k$ wird auch als Stirling-Polynom bezeichnet, siehe auch Abschnitt Stirling-Polynome.

Erzeugende Funktionen sind

    $\sum _{n=0}^{\infty }s_{n,k}\,{\frac {t^{n}}{n!}}={\frac {1}{k!}}{\bigl\!-\log(1-t){\bigr )}^{k}$ und $\sum _{k=0}^{\infty }\sum _{n=0}^{\infty }s_{n,k}\,{\frac {t^{n}}{n!}}\,u^{k}=(1-t)^{-u}$ und
    $\sum _{k=0}^{n}s_{n,k}\,x^{k}=(x)^{n}$

mit der steigenden Faktoriellen $(x)^{n}=x\,(x+1)\,\cdots \,(x+n-1).$

Ist $p$ eine Primzahl, dann ist $s_{p,k}$ für $1<k<p$ durch $p$ teilbar und für gerade $k<p-1$ durch $p^{2}$ teilbar (Nielsen 1893). Der Satz von Wolstenholme ist der Spezialfall $k=2.$

Da $n!$ die Anzahl aller Permutationen einer $n$-elementigen Menge ist, folgt

    $\sum _{k=0}^{n}s_{n,k}=n!$

und insbesondere $s_{n,k}\leq n!$ direkt aus der Definition von $s_{n,k}.$

Für jedes $n>2$ existiert ein $m_{n},$ so dass

    $s_{n,0}<s_{n,1}<\ldots <s_{n,m_{n}-1}<s_{n,m_{n}}>s_{n,m_{n}+1}>\ldots >s_{n,n}$

und $m_{n+1}=m_{n}$ oder $m_{n+1}=m_{n}+1$ (Erdős 1953).

Für jedes $n$ ist die Folge $s_{n,0},s_{n,1},...,s_{n,n}$ streng logarithmisch konkav, das heißt, $s_{n,k}^{2}>s_{n,k-1}s_{n,k+1}$ für $0<k<n.$

Das asymptotische Verhalten von $s_{n,k}$ unter der Annahme $k=o(\log n)$ ist

    $s_{n,k}\sim {\frac {(n-1)!}{(k-1)!}}\,(\gamma +\log n)^{k-1}$

mit der Euler-Mascheroni-Konstante $\gamma .$

## Stirling-Zahlen zweiter Art

Die Stirling-Zahl zweiter Art $S_{n,k}$ ist die Anzahl der $k$-elementigen Partitionen einer $n$-elementigen Menge, also die Anzahl der Möglichkeiten, eine $n$-elementige Menge in $k$ nichtleere disjunkte Teilmengen aufzuteilen.

$S_{n,k}$ ist auch die Anzahl der Möglichkeiten, $n$ unterscheidbare Bälle auf $k$ nicht unterscheidbare Fächer aufzuteilen, so dass mindestens ein Ball in jedem Fach liegt. Sind die Fächer unterscheidbar, so erhält man $k!S_{n,k}$ Möglichkeiten, dies ist auch die Anzahl surjektiver Abbildungen einer $n$-elementigen Menge auf eine $k$-elementige Menge.

### Beispiel

Die Menge $\{a,b,c,d\}$ mit $n=4$ Elementen kann auf folgende Weisen in $k=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\}\},\ \{\{a,c,d\},\{b\}\},\ \{\{b,c,d\},\{a\}\}.$

Also ist $S_{4,2}=7$.

### Eigenschaften

Es gelten die expliziten Formeln

    $S_{n,k}={\frac {1}{k!}}\sum _{j=0}^{k}(-1)^{k-j}{\binom {k}{j}}j^{\,n}$ und
    $S_{n,k}=\!\!\!\sum _{1\leq i_{1}\leq i_{2}\leq ...\leq i_{n-k}\leq k}\!\!\!i_{1}i_{2}\cdots i_{n-k}=\!\!\!\sum _{c_{1}+c_{2}+\cdots +c_{k}=n-k}\!\!\!1^{c_{1}}2^{c_{2}}\cdots k^{c_{k}}$

mit ganzzahligen nichtnegativen $c_{1},c_{2},...,c_{k}$ und die rekursive Formel

    $S_{n+1,k}=S_{n,k-1}+k\,S_{n,k}$

mit den Anfangsbedingungen

    $S_{n,n}=1$ und
    $S_{n,k}=0$ für $k=0<n$ oder $n<k.$

Weitere spezielle Werte sind

* $S_{n,1}=1$
* $S_{n,2}=2^{n-1}-1$
* $S_{n,3}={\tfrac {1}{2}}\,(3^{n-1}-2^{n}+1),$ Folge A000392 in OEIS
* $S_{n,n-3}={\tbinom {n}{4}}{\tbinom {n-2}{2}}={\tfrac {1}{48}}\,n\,(n-1)\,(n-2)^{2}\,(n-3)^{2},$ Folge A001297 in OEIS
* $S_{n,n-2}={\tfrac {1}{24}}\,n\,(n-1)\,(n-2)\,(3n-5),$ Folge A001296 in OEIS
* $S_{n,n-1}={\tbinom {n}{2}}={\tfrac {1}{2}}\,n\,(n-1)$

für alle $n>0.$

Auch $S_{n,n-k}$ kann als Polynom in $n$ vom Grad $2k$ aufgefasst werden. Es hat den Leitkoeffizienten $1/(2^{k}k!)$ und enthält für alle $k>0$ die Faktoren n, n−1, …, n−k und für ungerade $k>1$ die Faktoren $(n−k)^2$ und $(n−k+1)^2.$ Man erhält dasselbe Stirling-Polynom $k$-ten Grades wie bei den Stirling-Zahlen erster Art mittels

    $(-1)^{k}\psi _{k}(-n)=S_{n+k,n-1}/{\bigl(n+k)\,(n+k-1)\cdots (n-1){\bigr )}.$

Erzeugende Funktionen sind

    $\sum _{n=0}^{\infty }S_{n,k}\,{\frac {t^{n}}{n!}}={\frac {1}{k!}}(e^{t}-1)^{k}$ und $\sum _{k=0}^{\infty }\sum _{n=0}^{\infty }S_{n,k}\,{\frac {t^{n}}{n!}}\,u^{k}=e^{(e^{t}-1)u}$ und
    $\sum _{n=0}^{\infty }S_{n,k}\,u^{n}={\frac {u^{k}}{(1-u)(1-2u)\cdots (1-ku)}}$ und
    $\sum _{k=0}^{n}S_{n,k}\,(x)_{k}=x^{n}$

mit der fallenden Faktoriellen $(x)_{n}=x\,(x-1)\,\cdots \,(x-n+1).$

Ist $p$ eine Primzahl, dann ist $S_{p,k}$ für $1<k<p$ durch $p$ teilbar.

Da die Bellsche Zahl $B_{n}$ die Anzahl aller Partitionen einer $n$-elementigen Menge ist, gilt

    $\sum _{k=0}^{n}S_{n,k}=B_{n}.$

Die Bernoulli-Zahl $β_n$ erhält man als die alternierende Summe

    $\sum _{k=0}^{n}(-1)^{k}{\frac {k!}{k+1}}S_{n,k}=\beta _{n}.$

Mit Hilfe der Rekursionsformel kann man zeigen, dass für jedes $n>2$ ein $m_{n}$ existiert, so dass

    $S_{n,0}<S_{n,1}<\ldots <S_{n,m_{n}-1}\leq S_{n,m_{n}}>S_{n,m_{n}+1}>\ldots >S_{n,n}$

und $m_{n+1}=m_{n}$ oder $m_{n+1}=m_{n}+1$ gilt. Es ist eine offene Frage, ob ein $n>2$ existiert, für das der Fall $S_{n,m_{n}-1}=S_{n,m_{n}}$ eintritt.

Für jedes $n$ ist die Folge $S_{n,0},S_{n,1},...,S_{n,n}$ streng logarithmisch konkav, das heißt, $S_{n,k}^{2}>S_{n,k-1}S_{n,k+1}$ für $0<k<n.$

## Beziehung zwischen den Stirling-Zahlen erster und zweiter Art

Aus den Beziehungen

    $x^{n}=\sum _{k=0}^{n}S_{n,k}\,(x)_{k}$ und $(x)_{n}=\sum _{k=0}^{n}(-1)^{n-k}s_{n,k}\,x^{k},$

die auch häufig zur Definition der Stirling-Zahlen zweiter und erster Art verwendet werden, folgt, dass diese die Koeffizienten von zueinander inversen linearen Transformationen sind, der Stirling-Transformation und der inversen Stirling-Transformation. Das heißt, dass die unteren Dreiecksmatrizen ${\biglS_{n,k}{\bigr )}_{n,k}$ und ${\bigl(-1)^{n-k}s_{n,k}{\bigr )}_{n,k}$ zueinander inverse Matrizen sind:

    $\sum _{i=0}^{\infty }S_{n,i}\,(-1)^{i-k}s_{i,k}=\delta _{n,k}=\sum _{i=0}^{\infty }(-1)^{n-i}s_{n,i}\,S_{i,k}$

mit dem Kronecker-Delta $\delta _{n,k}=1$ für $n=k$ und $\delta _{n,k}=0$ für $n\neq k.$

Die Stirlingzahlen erster und zweiter Art lassen sich jeweils durch die anderen darstellen (Schlömilch 1852):

    $(-1)^{n-k}s_{n,k}=\sum _{j=0}^{n-k}(-1)^{j}{\binom {n+j-1}{k-1}}{\binom {2n-k}{n-k-j}}S_{n-k+j,j}$ und
    $S_{n,k}=\sum _{j=0}^{n-k}(-1)^{j}{\binom {n+j-1}{k-1}}{\binom {2n-k}{n-k-j}}(-1)^{n-k}s_{n-k+j,j}.$

Die Stirlingzahlen können eindeutig so auf negative ganze Indizes $n$ und $k$ fortgesetzt werden, dass die Rekursionsformeln

    $s_{n+1,k}=s_{n,k-1}+n\,s_{n,k}$ und $S_{n+1,k}=S_{n,k-1}+k\,S_{n,k}$

allgemein gelten und $S_{n,k}=0=s_{n,k}$ für $n<k=0.$ Man erhält die für alle ganzen Zahlen $n$ und $k$ gültige Dualität

    $S_{-n,-k}=s_{k,n}\,,$

die auch die beiden Rekursionsformeln ineinander überführt, außerdem $S_{n,k}=0=s_{n,k}$ für $n{\text{ }}k<0.$ Setzt man in die als Polynome in $n$ aufgefassten $S_{n,n-k}$ und $s_{n,n-k}$ für $n$ negative ganze Zahlen ein, so erhält man dieselbe Fortsetzung auf negative ganze Indizes und für die Polynome die Dualität

    $S_{n,n-k}=s_{(k-n),(k-n)-k}\,.$

## Analogie zu den Binomialkoeffizienten

Für die Binomialkoeffizienten gilt

    ${\binom {n+1}{k}}={\binom {n}{k-1}}+{\binom {n}{k}}.$

Die Karamata-Notation betont die Analogie:

    ${\Bigl{n+1 \atop k}{\Bigr ]}={\Bigl{n \atop k-1}{\Bigr ]}+n\,{\Bigl{n \atop k}{\Bigr ]}$
    ${\Bigl \{n+1 \atop k}{\Bigr \}}={\Bigl \{n \atop k-1}{\Bigr \}}+k\,{\Bigl \{n \atop k}{\Bigr \}}$

Entsprechend lassen sich die Stirling-Zahlen in einem Dreiecksschema ähnlich dem Pascalschen Dreieck anordnen und zeilenweise berechnen.

Dreieck für Stirling-Zahlen erster Art (erste Zeile $n=1,$ erste Spalte $k=1;$ Folge A130534 in OEIS):

Dreieck für Stirling-Zahlen zweiter Art (erste Zeile $n=1,$ erste Spalte $k=1;$ Folge A008277 in OEIS):

Als eine weitere Analogie gibt es $k!{\tbinom {n}{k}}$ injektive und $\textstyle n!{\bigl \\!{k \atop n}\!{\bigr \}}$ surjektive Funktionen mit $k$-elementiger Definitions- und $n$-elementiger Zielmenge.

## Stirling-Polynome

Die im Abschnitt Stirling-Zahlen erster Art eingeführten Stirling-Polynome werden auch durch die erzeugenden Funktionen

    ${\Bigl{\frac {t}{1-e^{-t}}}{\Bigr )}^{x+1}=1+(x+1)\sum _{k=0}^{\infty }\psi _{k}(x)\,t^{k+1}$ und
    ${\Bigl{\frac {-\log(1-t)}{t}}{\Bigr )}^{x}=1+x\sum _{k=0}^{\infty }\psi _{k}(x+k)\,t^{k+1}$

beschrieben, die man durch Verallgemeinerung erzeugender Funktionen von $S_{n,k}$ und $s_{n,k}$ erhält. Nach einer anderen Definition werden die Polynome $S_{0}(x)=1$ und $S_{k}(x)=k!(x+1)\psi _{k-1}(x)$ als Stirling-Polynome bezeichnet. Die Polynome $ψ_0(x),$ $ψ_1(x),$ …, $ψ_6(x)$ sind

    ${\tfrac {1}{2}},$ ${\tfrac {1}{24}}(3x+2),$ ${\tfrac {1}{48}}(x+1)\,x,$ ${\tfrac {1}{5760}}(15x^{3}+15x^{2}-10x-8),$ ${\tfrac {1}{11520}}(x+1)\,x\,(3x^{2}-x-6),$
    ${\tfrac {1}{2903040}}(63x^{5}-315x^{3}-224x^{2}+140x+96),$ ${\tfrac {1}{5806080}}(x+1)\,x\,(9x^{4}-18x^{3}-57x^{2}+34x+80),$

und spezielle Werte für $k>0$ sind

    $\psi _{k}(-1)=-\beta _{k+1}/((k+1)!(k+1))$ und $\psi _{k}(0)=\beta _{k+1}/(k+1)!$

mit der Bernoulli-Zahl $β_{k+1}.$ Berechnet werden können die Polynome mit den Formeln

    $\psi _{k}(x)=\sum _{j=0}^{k}{\frac {C_{k+1,j}}{(2k+2-j)!}}(x-k-1)_{k-j}$ und
    $(-1)^{k}\psi _{k}(-x)=\sum _{j=0}^{k}{\frac {{\overline {C}}_{k+1,j}}{(2k+2-j)!}}(x-2)_{k-j}$

mit den durch $C_{1,0}=1,$ $C_{k,j}=0$ für j ∉ {0, 1, …, k−1} und

    $C_{k+1,j}=(2k+1-j)\,(C_{k,j-1}+C_{k,j}),$ siehe Folge A111999 in OEIS,

und den durch $C̅_{1,0}$ = 1, $C̅_{k,j}$ = 0 für j ∉ {0, 1, …, k−1} und

    ${\overline {C}}_{k+1,j}=(k+1-j)\,{\overline {C}}_{k,j-1}+(2k+1-j)\,{\overline {C}}_{k,j}$

rekursiv definierten ganzzahligen Koeffizienten. Für $k>0$ erhält man

    $s_{n,n-k}=\sum _{j=0}^{k-1}C_{k,j}{\binom {n}{2k-j}}$ und $S_{n,n-k}=\sum _{j=0}^{k-1}{\overline {C}}_{k,j}{\binom {n}{2k-j}}.$

Diese Berechnung von $s_{n,n-k}$ und $S_{n,n-k}$ ist besonders für große $n$ und kleine $k$ effizient.

## Programmierbeispiel

Die Stirling-Zahlen lassen sich sehr einfach in einer rekursiven Methode implementieren. Beispielsweise können in Java die Stirling-Zahlen zweiter Art folgendermaßen implementiert werden.

Verlauf des Programmes:

* Wenn n = k = 0 ist, wird 1 zurückgegeben.
* Wenn n = 0 und k > 0 ist oder n > 0 und k = 0, wird 0 zurückgegeben.
* Wenn n und k beide größer als 0 sind, wird dieselbe Funktion zwei Mal in veränderter Form rekursiv aufgerufen und zurückgegeben.
* Wenn alle anderen Abfragen scheitern, heißt dass, das mindestens einer der beiden Werte negativ sein muss, und das Programm erzeugt einen Fehler.
