Stirling-Zahl

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

Bezeichnung und Notation[Bearbeiten]

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 s bezeichnet oder übereinander in eckigen Klammern geschrieben, Stirlingzahlen der zweiten Art mit großem S bezeichnet oder übereinander in geschweiften Klammern geschrieben:

\textstyle s_{n,k} = \bigl[{n \atop k}\bigr], \qquad S_{n,k} = \bigl\{\!{n \atop k}\!\bigr\}.

Die Klammernotation, auch Karamata-Notation genannt, wurde 1935 von Jovan Karamata in Analogie zu den Binomialkoeffizienten \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[Bearbeiten]

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

Beispiel[Bearbeiten]

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

(a b c)(d),\text{ }(a c b)(d),\text{ }(a b d)(c),\text{ }(a d b)(c),\text{ }(a c d)(b),\text{ }(a d c)(b),\text{ }(b c d)(a),\text{ }(b d c)(a),\text{ }(a b)(c d),\text{ }(a c)(b d),\text{ }(a d)(b c)

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

Eigenschaften[Bearbeiten]

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

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 2 k aufgefasst werden. Es hat den Leitkoeffizienten 1/(2^k k!) und enthält für alle k > 0 die Faktoren n, n−1, …, nk und für ungerade k > 1 die Faktoren n2 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,[7] 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[8] und für gerade k < p-1 durch p^2 teilbar (Nielsen 1893).[9] 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).[10]

Für jedes n ist die Folge s_{n,0}, s_{n,1}, ..., s_{n,n} streng logarithmisch konkav,[11] 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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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

für alle n > 0.

Auch S_{n,n-k} kann als Polynom in n vom Grad 2 k aufgefasst werden. Es hat den Leitkoeffizienten 1/(2^k k!) und enthält für alle k > 0 die Faktoren n, n−1, …, nk und für ungerade k > 1 die Faktoren (nk)2 und (nk+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.[12]

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.[13]

Für jedes n ist die Folge S_{n,0}, S_{n,1}, ..., S_{n,n} streng logarithmisch konkav,[11] 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[Bearbeiten]

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 \bigl(S_{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):[14]

(-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 Sn,nk und sn,nk 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[15]

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

Analogie zu den Binomialkoeffizienten[Bearbeiten]

Für die Binomialkoeffizienten gilt

\tbinom{n+1}{k} = \tbinom{n}{k-1} + \tbinom{n}{k}.

Die Karamata-Notation betont die Analogie:

\textstyle\bigl[{n+1 \atop k}\bigr] = \bigl[{n \atop k-1}\bigr] + n\,\bigl[{n \atop k}\bigr]
\textstyle\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.

Dreieck für Stirling-Zahlen erster Art (erste Zeile n=1, erste Spalte 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 n=1, erste Spalte 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 k! \tbinom{n}{k} injektive und \textstyle n!\bigl\{\!{k \atop n}\!\bigr\} surjektive Funktionen mit k-elementiger Definitions- und n-elementiger Zielmenge.[16]

Stirling-Polynome[Bearbeiten]

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} (3 x + 2),     \tfrac{1}{48} (x + 1)\,x,     \tfrac{1}{5760} (15 x^3 + 15 x^2 - 10 x - 8),     \tfrac{1}{11520} (x + 1)\,x\,(3 x^2 - x - 6),
\tfrac{1}{2903040} (63 x^5 - 315 x^3 - 224 x^2 + 140 x + 96),     \tfrac{1}{5806080} (x+1)\,x\,(9 x^4 - 18 x^3 - 57 x^2 + 34 x + 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.[7] 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,[17]

und den durch 1,0 = 1, 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.[18] 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.

Literatur[Bearbeiten]

Einzelnachweise[Bearbeiten]

  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)
  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)
  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 \scriptstyle A_{n,p}=s_{n+1,n+1-p})
  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 \scriptstyle s_{n,m_n-1} \neq s_{n,m_n} ist nicht elementar; Zentralblatt-Rezension: [1])
  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)
  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)
  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 \scriptstyle C^{+n}_k = s_{n,n-k} und \scriptstyle C^{-n}_k = 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)
  16. Antal E. Fekete: Apropos Two notes on notation, The American Mathematical Monthly 101, Oktober 1994, S. 771–778 (englisch)
  17. Jordan: Stirling’s numbers, 1979, S. 147–153
  18. Jordan: Stirling’s numbers, 1979, S. 168–173

Weblinks[Bearbeiten]