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,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) führte Niels Nielsen 1906 im Handbuch der Theorie der Gammafunktion die Bezeichnung „Stirlingsche Zahlen erster und zweiter Art“ einNielsen: Fakultäten und Fakultätenkoeffizienten, 1906, S. 66–67 („nombres de Stirling“ bereits in einem 1904 veröffentlichten Artikel).Niels Nielsen: Recherches sur les polynomes et les nombres de Stirling, Annali di matematica pura ed applicata 10, 1904, S. 287–318 (französisch)
Weder die Bezeichnung als Stirlingzahlen noch einheitliche Notationen haben sich durchgesetzt.Henry W. Gould: Noch einmal die Stirlingschen Zahlen, Jahresbericht der DMV 73, 1971/72, S. 149–152Donald E. Knuth: Two notes on notation, The American Mathematical Monthly 99, 1992, S. 403–422 (englisch; Zentralblatt-Rezension) 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,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) 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 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
Die Menge mit Elementen kann auf folgende Weisen auf Zyklen aufgeteilt werden:
Also ist . Für weitere Beispiele siehe Zykeltyp.
Eigenschaften
Es gelten die expliziten Formeln
und die rekursive Formel
mit den Anfangsbedingungen
und für oder
Weitere spezielle Werte sind
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, …, n−k und für ungerade die Faktoren n2 und (n−1)2. Das Polynom
in vom Grad wird auch als Stirling-Polynom bezeichnet,Nielsen: Fakultäten und Fakultätenkoeffizienten, 1906, S. 72 ff. siehe auch Abschnitt Stirling-Polynome.
Erzeugende Funktionen sind
und und
mit der steigenden Faktoriellen
Ist eine Primzahl, dann ist für durch teilbarComtet: Advanced combinatorics, 1974, S. 218 und für gerade durch teilbar (Nielsen 1893).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) 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).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)
Für jedes ist die Folge streng logarithmisch konkav,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) das heißt, für
Das asymptotische Verhalten von für bei festem ist
mit der Euler-Mascheroni-Konstante Die Asymptotik gilt auch für langsam wachsendes , genauer für .
Stirling-Zahlen zweiter Art
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
Die Menge mit Elementen kann auf folgende Weisen in nichtleere disjunkte Teilmengen zerlegt werden:
Also ist .
Eigenschaften
Es gelten die expliziten Formeln
und
mit ganzzahligen nichtnegativen und die rekursive Formel
mit den Anfangsbedingungen
und für oder
Weitere spezielle Werte sind
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, …, n−k und für ungerade die Faktoren (n−k)2 und (n−k+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.Comtet: Advanced combinatorics, 1974, S. 219
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.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)
Für jedes ist die Folge streng logarithmisch konkav, das heißt, für
Beziehung zwischen den Stirling-Zahlen erster und zweiter Art
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):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 )
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ätIra Gessel, Richard P. Stanley: Stirling polynomials (PDF-Datei, 534 kB), Journal of combinatorial theory A 24, 1978, S. 24–33 (englisch; Zentralblatt-Rezension)
Analogie zu den Binomialkoeffizienten
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 ):
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 ):
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.Antal E. Fekete: Apropos Two notes on notation, The American Mathematical Monthly 101, Oktober 1994, S. 771–778 (englisch; Zentralblatt-Rezension)
Stirling-Polynome
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. Berechnet werden können die Polynome mit den Formeln
und
mit den durch für j ∉ {0, 1, …, k−1} und
siehe ,Jordan: Stirling’s numbers, 1979, S. 147–153
und den durch C̅1,0 = 1, C̅k,j = 0 für j ∉ {0, 1, …, k−1} und
rekursiv definierten ganzzahligen Koeffizienten.Jordan: Stirling’s numbers, 1979, S. 168–173 Für erhält man
und
Diese Berechnung von und ist besonders für große und kleine 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 und ; 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 und ; 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 und ) 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
Weblinks