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

 .

Die Klammernotation, auch Karamata-Notation genannt, wurde 1935 von Jovan Karamata in Analogie zu den Binomialkoeffizienten   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   ist die Anzahl der Permutationen einer  -elementigen Menge, die genau   Zyklen haben. Nach einer häufig verwendeten anderen Definition wird stattdessen   als Stirling-Zahl erster Art bezeichnet.

Beispiel

Bearbeiten

Die Menge   mit   Elementen kann auf folgende Weisen auf   Zyklen aufgeteilt werden:

 

Also ist  . Für weitere Beispiele siehe Zykeltyp.

Eigenschaften

Bearbeiten

Es gelten die expliziten Formeln

 

und die rekursive Formel

 

mit den Anfangsbedingungen

      und
      für       oder    

Weitere spezielle Werte sind

  •  
  •   Folge A000254 in OEIS
  •   Folge A000399 in OEIS
  •   Folge A001303 in OEIS
  •   Folge A000914 in OEIS
  •  

für alle   wobei   die  -te harmonische Zahl und   eine verallgemeinerte harmonische Zahl ist.

Allgemein kann   als Polynom in   vom Grad   aufgefasst werden. Es hat den Leitkoeffizienten   und enthält für alle   die Faktoren n, n−1, …, nk und für ungerade   die Faktoren n2 und (n−1)2. Das Polynom

 

in   vom Grad   wird auch als Stirling-Polynom bezeichnet,[7] siehe auch Abschnitt Stirling-Polynome.

Erzeugende Funktionen sind

      und           und
 

mit der steigenden Faktoriellen  

Ist   eine Primzahl, dann ist   für   durch   teilbar[8] und für gerade   durch   teilbar (Nielsen 1893).[9] Der Satz von Wolstenholme ist der Spezialfall  

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

 

und insbesondere   direkt aus der Definition von  

Für jedes   existiert ein   so dass

 

und   oder   (Erdős 1953).[10]

Für jedes   ist die Folge   streng logarithmisch konkav,[11] das heißt,   für  

Das asymptotische Verhalten von   unter der Annahme   ist

 

mit der Euler-Mascheroni-Konstante  

Stirling-Zahlen zweiter Art

Bearbeiten

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

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

Beispiel

Bearbeiten

Die Menge   mit   Elementen kann auf folgende Weisen in   nichtleere disjunkte Teilmengen zerlegt werden:

 
 

Also ist  .

Eigenschaften

Bearbeiten

Es gelten die expliziten Formeln

      und
 

mit ganzzahligen nichtnegativen   und die rekursive Formel

 

mit den Anfangsbedingungen

      und
      für       oder    

Weitere spezielle Werte sind

  •  
  •  
  •   Folge A000392 in OEIS
  •   Folge A001297 in OEIS
  •   Folge A001296 in OEIS
  •  

für alle  

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

 

Erzeugende Funktionen sind

      und           und
      und
 

mit der fallenden Faktoriellen  

Ist   eine Primzahl, dann ist   für   durch   teilbar.[12]

Da die Bellsche Zahl   die Anzahl aller Partitionen einer  -elementigen Menge ist, gilt

 

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

 

Mit Hilfe der Rekursionsformel kann man zeigen, dass für jedes   ein   existiert, so dass

 

und   oder   gilt. Es ist eine offene Frage, ob ein   existiert, für das der Fall   eintritt.[13]

Für jedes   ist die Folge   streng logarithmisch konkav,[11] das heißt,   für  

Beziehung zwischen den Stirling-Zahlen erster und zweiter Art

Bearbeiten

Aus den Beziehungen

      und      

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   und   zueinander inverse Matrizen sind:

 

mit dem Kronecker-Delta   für   und   für  

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

      und
 

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

      und      

allgemein gelten und   für   Man erhält die für alle ganzen Zahlen   und   gültige Dualität

 

die auch die beiden Rekursionsformeln ineinander überführt, außerdem   für   Setzt man in die als Polynome in   aufgefassten   und   für   negative ganze Zahlen ein, so erhält man dieselbe Fortsetzung auf negative ganze Indizes und für die Polynome die Dualität[15]

 

Analogie zu den Binomialkoeffizienten

Bearbeiten

Für die Binomialkoeffizienten gilt

 

Die Karamata-Notation betont die Analogie:

 
 

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   erste Spalte   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   erste Spalte   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   injektive und   surjektive Funktionen mit  -elementiger Definitions- und  -elementiger Zielmenge.[16]

Stirling-Polynome

Bearbeiten

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

      und
 

beschrieben, die man durch Verallgemeinerung erzeugender Funktionen von   und   erhält. Nach einer anderen Definition werden die Polynome   und   als Stirling-Polynome bezeichnet. Die Polynome ψ0(x), ψ1(x), …, ψ6(x) sind

                         
       

und spezielle Werte für   sind

      und      

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

      und
 

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

  siehe Folge A111999 in OEIS,[17]

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

 

rekursiv definierten ganzzahligen Koeffizienten.[18] Für   erhält man

      und      

Diese Berechnung von   und   ist besonders für große   und kleine   effizient.

Programmierbeispiel

Bearbeiten

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

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; 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  ; 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   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   und  )
  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
Bearbeiten