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,^[1] führte Niels Nielsen 1906 im Handbuch der Theorie der Gammafunktion die Bezeichnung „Stirlingsche Zahlen erster und zweiter Art“ ein^[2] („nombres de Stirling“ bereits in einem 1904 veröffentlichten Artikel).^[3]

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

${\displaystyle 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 ${\displaystyle {\tbinom {n}{k}}}$ eingeführt,^[6] 1992 setzte sich Donald Knuth mit einem ausführlichen Exkurs über die Stirling-Zahlen für diese Schreibweise ein.^[5]

Stirling-Zahlen erster Art

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

Beispiel

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

${\displaystyle (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 ${\displaystyle s_{4,2}=11}$. Für weitere Beispiele siehe Zykeltyp.

Eigenschaften

Es gelten die expliziten Formeln

${\displaystyle 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

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

mit den Anfangsbedingungen

${\displaystyle s_{n,n}=1}$     und

${\displaystyle s_{n,k}=0}$     für   ${\displaystyle k=0<n}$   oder   ${\displaystyle n<k.}$

Weitere spezielle Werte sind

• ${\displaystyle s_{n,1}=(n-1)!}$
• ${\displaystyle s_{n,2}=(n-1)!\,H_{n-1},}$ Folge A000254 in OEIS
• ${\displaystyle s_{n,3}={\tfrac {1}{2}}\,(n-1)!\,(H_{n-1}^{2}-H_{n-1,2}),}$ Folge A000399 in OEIS
• ${\displaystyle 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
• ${\displaystyle s_{n,n-2}={\tfrac {1}{24}}\,n\,(n-1)\,(n-2)\,(3n-1),}$ Folge A000914 in OEIS
• ${\displaystyle s_{n,n-1}={\tbinom {n}{2}}={\tfrac {1}{2}}\,n\,(n-1)}$

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

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

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

in ${\displaystyle n}$ vom Grad ${\displaystyle k}$ wird auch als Stirling-Polynom bezeichnet,^[7] siehe auch Abschnitt Stirling-Polynome.

Erzeugende Funktionen sind

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

${\displaystyle \sum _{k=0}^{n}s_{n,k}\,x^{k}=(x)^{n}}$

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

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

Da ${\displaystyle n!}$ die Anzahl aller Permutationen einer ${\displaystyle n}$-elementigen Menge ist, folgt

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

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

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

${\displaystyle 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 ${\displaystyle m_{n+1}=m_{n}}$ oder ${\displaystyle m_{n+1}=m_{n}+1}$ (Erdős 1953).^[10]

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

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

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

mit der Euler-Mascheroni-Konstante ${\displaystyle \gamma .}$

Stirling-Zahlen zweiter Art

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

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

Beispiel

Die Menge ${\displaystyle \{a,b,c,d\}}$ mit ${\displaystyle n=4}$ Elementen kann auf folgende Weisen in ${\displaystyle k=2}$ nichtleere disjunkte Teilmengen zerlegt werden:

${\displaystyle \{\{a,b\},\{c,d\}\},\ \{\{a,c\},\{b,d\}\},\ \{\{a,d\},\{b,c\}\},}$

${\displaystyle \{\{a,b,c\},\{d\}\},\ \{\{a,b,d\},\{c\}\},\ \{\{a,c,d\},\{b\}\},\ \{\{b,c,d\},\{a\}\}.}$

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

Eigenschaften

Es gelten die expliziten Formeln

${\displaystyle S_{n,k}={\frac {1}{k!}}\sum _{j=0}^{k}(-1)^{k-j}{\binom {k}{j}}j^{\,n}}$     und

${\displaystyle 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 ${\displaystyle c_{1},c_{2},...,c_{k}}$ und die rekursive Formel

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

mit den Anfangsbedingungen

${\displaystyle S_{n,n}=1}$     und

${\displaystyle S_{n,k}=0}$     für   ${\displaystyle k=0<n}$   oder   ${\displaystyle n<k.}$

Weitere spezielle Werte sind

• ${\displaystyle S_{n,1}=1}$
• ${\displaystyle S_{n,2}=2^{n-1}-1}$
• ${\displaystyle S_{n,3}={\tfrac {1}{2}}\,(3^{n-1}-2^{n}+1),}$ Folge A000392 in OEIS
• ${\displaystyle 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
• ${\displaystyle S_{n,n-2}={\tfrac {1}{24}}\,n\,(n-1)\,(n-2)\,(3n-5),}$ Folge A001296 in OEIS
• ${\displaystyle S_{n,n-1}={\tbinom {n}{2}}={\tfrac {1}{2}}\,n\,(n-1)}$

für alle ${\displaystyle n>0.}$

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

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

Erzeugende Funktionen sind

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

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

${\displaystyle \sum _{k=0}^{n}S_{n,k}\,(x)_{k}=x^{n}}$

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

Ist ${\displaystyle p}$ eine Primzahl, dann ist ${\displaystyle S_{p,k}}$ für ${\displaystyle 1<k<p}$ durch ${\displaystyle p}$ teilbar.^[12]

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

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

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

${\displaystyle \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 ${\displaystyle n>2}$ ein ${\displaystyle m_{n}}$ existiert, so dass

${\displaystyle 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 ${\displaystyle m_{n+1}=m_{n}}$ oder ${\displaystyle m_{n+1}=m_{n}+1}$ gilt. Es ist eine offene Frage, ob ein ${\displaystyle n>2}$ existiert, für das der Fall ${\displaystyle S_{n,m_{n}-1}=S_{n,m_{n}}}$ eintritt.^[13]

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

Beziehung zwischen den Stirling-Zahlen erster und zweiter Art

Aus den Beziehungen

${\displaystyle x^{n}=\sum _{k=0}^{n}S_{n,k}\,(x)_{k}}$     und     ${\displaystyle (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 ${\displaystyle {\bigl (}S_{n,k}{\bigr )}_{n,k}}$ und ${\displaystyle {\bigl (}(-1)^{n-k}s_{n,k}{\bigr )}_{n,k}}$ zueinander inverse Matrizen sind:

${\displaystyle \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 ${\displaystyle \delta _{n,k}=1}$ für ${\displaystyle n=k}$ und ${\displaystyle \delta _{n,k}=0}$ für ${\displaystyle n\neq k.}$

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

${\displaystyle (-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

${\displaystyle 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 ${\displaystyle n}$ und ${\displaystyle k}$ fortgesetzt werden, dass die Rekursionsformeln

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

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

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

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

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

Analogie zu den Binomialkoeffizienten

Für die Binomialkoeffizienten gilt

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

Die Karamata-Notation betont die Analogie:

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

${\displaystyle {\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 ${\displaystyle n=1,}$ erste Spalte ${\displaystyle k=1;}$ Folge A130534 in OEIS):

                             1
                          1     1
                       2     3     1
                    6    11     6     1
                24    50    35    10     1
             120   274   225   85    15     1
          720  1764  1624   735   175   21     1
      5040  13068 13132 6769  1960   322   28     1
  40320 109584 118124 67284 22449 4536  546   36     1
...   ...    ...   ...   ...   ...   ...   ...   ...    1

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

                             1
                          1     1
                       1     3     1
                    1     7     6     1
                 1    15    25    10     1
              1    31    90    65    15     1
           1    63    301   350   140   21     1
        1    127   966  1701  1050   266   28     1
     1    255  3025  7770  6951  2646  462    36     1
  1    ...   ...   ...   ...   ...   ...   ...   ...    1

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

Stirling-Polynome

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

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

${\displaystyle {\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 ${\displaystyle S_{n,k}}$ und ${\displaystyle s_{n,k}}$ erhält. Nach einer anderen Definition werden die Polynome ${\displaystyle S_{0}(x)=1}$ und ${\displaystyle S_{k}(x)=k!(x+1)\psi _{k-1}(x)}$ als Stirling-Polynome bezeichnet. Die Polynome ψ₀(x), ψ₁(x), …, ψ₆(x) sind

${\displaystyle {\tfrac {1}{2}},}$     ${\displaystyle {\tfrac {1}{24}}(3x+2),}$     ${\displaystyle {\tfrac {1}{48}}(x+1)\,x,}$     ${\displaystyle {\tfrac {1}{5760}}(15x^{3}+15x^{2}-10x-8),}$     ${\displaystyle {\tfrac {1}{11520}}(x+1)\,x\,(3x^{2}-x-6),}$

${\displaystyle {\tfrac {1}{2903040}}(63x^{5}-315x^{3}-224x^{2}+140x+96),}$     ${\displaystyle {\tfrac {1}{5806080}}(x+1)\,x\,(9x^{4}-18x^{3}-57x^{2}+34x+80),}$

und spezielle Werte für ${\displaystyle k>0}$ sind

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

mit der Bernoulli-Zahl β_k+1.^[7] Berechnet werden können die Polynome mit den Formeln

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

${\displaystyle (-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 ${\displaystyle C_{1,0}=1,}$ ${\displaystyle C_{k,j}=0}$ für j ∉ {0, 1, …, k−1} und

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

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

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

rekursiv definierten ganzzahligen Koeffizienten.^[18] Für ${\displaystyle k>0}$ erhält man

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

Diese Berechnung von ${\displaystyle s_{n,n-k}}$ und ${\displaystyle S_{n,n-k}}$ ist besonders für große ${\displaystyle n}$ und kleine ${\displaystyle 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.

static int stirling(int n, int k) {
	if (n == 0 && k == 0) {
		return 1;
	} else if ((n == 0 && k > 0) || (n > 0 && k == 0)) {
		return 0;
	} else if (n > 0 && k > 0){
		return stirling(n - 1, k - 1) + k * stirling(n - 1, k);
	}
	throw new IllegalArgumentException("Weder n noch k darf negativ sein.");
}

Literatur

• Niels Nielsen: Fakultäten und Fakultätenkoeffizienten, Kapitel 5 in Handbuch der Theorie der Gammafunktion, B. G. Teubner, Leipzig 1906, S. 66–78 (Umrechnung ${\displaystyle C_{n}^{p}=s_{n,n-p}}$ und ${\displaystyle {\mathfrak {C}}_{\,n}^{\,p}=S_{n-1+p,n-1}}$; im Internet-Archiv, dito, dito; Jahrbuch-Bericht)
• Leonard Eugene Dickson: History of the theory of numbers. Volume I: Divisibility and primality, Carnegie Institution, Washington 1919, besonders S. 95–103 (englisch; Umrechnung ${\displaystyle S_{n,m}=s_{m+1,m+1-n}}$ und ${\displaystyle \sigma _{n,m}=S_{m+n,m}}$; im Internet-Archiv; Jahrbuch-Bericht)
• Károly Jordan (Charles Jordan): Stirling’s numbers, Kapitel 4 in Calculus of finite differences, Chelsea, Budapest 1939, 2. Auflage New York 1947 1960, 3. Auflage 1965 1979, ISBN 0-8284-0033-4, S. 142–229 (englisch; Umrechnung ${\displaystyle S_{n}^{m}=(-1)^{n-m}s_{n,m}}$ und ${\displaystyle {\mathfrak {S}}_{n}^{m}=S_{n,m}}$)
• Milton Abramowitz, Irene A. Stegun (Hrsg.): Handbook of mathematical functions with formulas, graphs, and mathematical tables (10. Auflage), US Department of Commerce/National Bureau of Standards, 1972, S. 822, 824–825, 833–835 (englisch; bei ConvertIt.com; bei der SFU Burnaby; Zentralblatt-Rezension)
• Louis Comtet: Advanced combinatorics: the art of finite and infinite expansions, D. Reidel, Dordrecht 1974, ISBN 90-277-0441-4, S. 204–229 (englisch)
• Martin Aigner: Combinatorial Theory. Springer, Berlin 1997, ISBN 3-540-61787-6 (englisch; Neuauflage der Ausgabe von 1979; Zentralblatt-Rezension)
• Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Concrete mathematics: a foundation for computer science, Addison-Wesley, Reading 1988, 2. Auflage 1994, ISBN 0-201-55802-5, S. 257–266 (englisch; Knuths Webseite zum Buch mit Errata: Concrete Mathematics, Second Edition; Zentralblatt-Rezension)

Einzelnachweise

1. ↑ James Stirling: Methodus Differentialis: sive Tractatus de Summatione et Interpolatione Serierum Infinitarum, G. Strahan, Londini (London) 1730 (lateinisch; Tafel der Stirling-Zahlen zweiter Art auf S. 8, der Stirling-Zahlen erster Art auf S. 11)
2. ↑ Nielsen: Fakultäten und Fakultätenkoeffizienten, 1906, S. 66–67
3. ↑ Niels Nielsen: Recherches sur les polynomes et les nombres de Stirling, Annali di matematica pura ed applicata 10, 1904, S. 287–318 (französisch)
4. ↑ Henry W. Gould: Noch einmal die Stirlingschen Zahlen, Jahresbericht der DMV 73, 1971/72, S. 149–152
5. ↑ ^{a b} Donald E. Knuth: Two notes on notation, The American Mathematical Monthly 99, 1992, S. 403–422 (englisch; Zentralblatt-Rezension)
6. ↑ Jovan Karamata: Théorèmes sur la sommabilité exponentielle et d’autres sommabilités s’y rattachant (21. Mai 1932), Mathematica (Cluj) 9, 1935, S. 164–178 (französisch; Zentralblatt-Rezension)
7. ↑ ^{a b} Nielsen: Fakultäten und Fakultätenkoeffizienten, 1906, S. 72 ff.
8. ↑ Comtet: Advanced combinatorics, 1974, S. 218
9. ↑ Niels Nielsen: Om Potenssummer af hele Tal, Nyt Tidsskrift for Mathematik B 4, 1893, S. 1–10 (dänisch; Formel 17 auf S. 4 mit ${\displaystyle A_{n,p}=s_{n+1,n+1-p}}$; Jahrbuch-Bericht)
10. ↑ Paul Erdős: On a conjecture of Hammersley, Journal of the London Mathematical Society 28, 1953, S. 232–236 (englisch; nur der Beweis für ${\displaystyle s_{n,m_{n}-1}\neq s_{n,m_{n}}}$ ist nicht elementar; Zentralblatt-Rezension)
11. ↑ ^{a b} Elliott H. Lieb: Concavity properties and a generating function for Stirling numbers, Journal of Combinatorial Theory 5, September 1968, S. 203–206 (englisch; Zentralblatt-Rezension)
12. ↑ Comtet: Advanced combinatorics, 1974, S. 219
13. ↑ E. Rodney Canfield, Carl Pomerance: On the problem of uniqueness for the maximum Stirling number(s) of the second kind, Integers 2, 2002, A01 (englisch; Corrigendum; Zentralblatt-Rezension)
14. ↑ Oskar Schlömilch: Recherches sur les coefficients des facultés analytiques, Journal für die reine und angewandte Mathematik 44, 1852, S. 344–355 (französisch; Formel 14 auf S. 346 mit ${\displaystyle C_{k}^{+n}=s_{n,n-k}}$ und ${\displaystyle C_{k}^{-n}=S_{n+k,n}}$)
15. ↑ Ira Gessel, Richard P. Stanley: Stirling polynomials (PDF-Datei, 534 kB), Journal of combinatorial theory A 24, 1978, S. 24–33 (englisch; Zentralblatt-Rezension)
16. ↑ Antal E. Fekete: Apropos Two notes on notation, The American Mathematical Monthly 101, Oktober 1994, S. 771–778 (englisch; Zentralblatt-Rezension)
17. ↑ Jordan: Stirling’s numbers, 1979, S. 147–153
18. ↑ Jordan: Stirling’s numbers, 1979, S. 168–173

Weblinks

Wikiversity: Eine Vorlesung über Partitionen und Stirling-Zahlen zweiter Art im Rahmen eines Kurses zur diskreten Mathematik – Kursmaterialien

• Eric W. Weisstein: Stirling Number of the First Kind, Stirling Number of the Second Kind, Stirling Transform und Stirling Polynomial. In: MathWorld. (englisch)
• Stirling number of the first kind und Stirling number of the second kind bei The Wolfram Functions Site (englisch; mit Berechnungsmöglichkeit)
• Set Partitions: Stirling Numbers in der NIST Digital Library of Mathematical Functions (englisch)