www.wikidata.de-de.nina.az

Stirling Zahl Die en erster und zweiter Art benannt nach James Stirling werden in der Kombinatorik und der theoretischen

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 Bearbeiten

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 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, 1992 setzte sich Donald Knuth mit einem ausführlichen Exkurs über die Stirling-Zahlen für diese Schreibweise ein.

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

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, siehe auch Abschnitt Stirling-Polynome.

Erzeugende Funktionen sind

mit der steigenden Faktoriellen

Ist eine Primzahl, dann ist für durch teilbar und für gerade durch teilbar (Nielsen 1893). 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).

Für jedes ist die Folge streng logarithmisch konkav, 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

mit ganzzahligen nichtnegativen und die rekursive Formel

mit den Anfangsbedingungen

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

mit der fallenden Faktoriellen

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

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.

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

Beziehung zwischen den Stirling-Zahlen erster und zweiter Art Bearbeiten

Aus den Beziehungen

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):

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

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

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.

Stirling-Polynome Bearbeiten

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

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

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

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

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

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

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. ↑ 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. ↑ 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. ↑ 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

Weblinks Bearbeiten

Wikiversity: Eine Vorlesung über Partitionen und Stirling-Zahlen zweiter Art im Rahmen eines Kurses zur diskreten Mathematik – Kursmaterialien
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Stirling Zahlen erster und zweiter Art benannt nach James Stirling werden in der Kombinatorik und der theoretischen Informatik verwendet Inhaltsverzeichnis 1 Bezeichnung und Notation 2 Stirling Zahlen erster Art 2 1 Beispiel 2 2 Eigenschaften 3 Stirling Zahlen zweiter Art 3 1 Beispiel 3 2 Eigenschaften 4 Beziehung zwischen den Stirling Zahlen erster und zweiter Art 5 Analogie zu den Binomialkoeffizienten 6 Stirling Polynome 7 Programmierbeispiel 8 Literatur 9 Einzelnachweise 10 WeblinksBezeichnung und Notation BearbeitenMit Hinweis auf eine bereits 1730 veroffentlichte Arbeit Stirlings in der diese Zahlen untersucht werden 1 fuhrte 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 veroffentlichten 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 displaystyle s nbsp bezeichnet oder ubereinander in eckigen Klammern geschrieben Stirlingzahlen der zweiten Art mit grossem S displaystyle S nbsp bezeichnet oder ubereinander in geschweiften Klammern geschrieben s n k n k S n k n k displaystyle s n k left n atop k right qquad S n k left n atop k right nbsp Die Klammernotation auch Karamata Notation genannt wurde 1935 von Jovan Karamata in Analogie zu den Binomialkoeffizienten n k displaystyle tbinom n k nbsp eingefuhrt 6 1992 setzte sich Donald Knuth mit einem ausfuhrlichen Exkurs uber die Stirling Zahlen fur diese Schreibweise ein 5 Stirling Zahlen erster Art BearbeitenDie Stirling Zahl erster Art s n k displaystyle s n k nbsp ist die Anzahl der Permutationen einer n displaystyle n nbsp elementigen Menge die genau k displaystyle k nbsp Zyklen haben Nach einer haufig verwendeten anderen Definition wird stattdessen 1 n k s n k displaystyle 1 n k s n k nbsp als Stirling Zahl erster Art bezeichnet Beispiel Bearbeiten Die Menge a b c d displaystyle a b c d nbsp mit n 4 displaystyle n 4 nbsp Elementen kann auf folgende Weisen auf k 2 displaystyle k 2 nbsp Zyklen aufgeteilt werden a b c d a c b d a b d c a d b c a c d b a d c b b c d a b d c a a b c d a c b d a d b c 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 nbsp Also ist s 4 2 11 displaystyle s 4 2 11 nbsp Fur weitere Beispiele siehe Zykeltyp Eigenschaften Bearbeiten Es gelten die expliziten Formeln s n k 0 lt i 1 lt i 2 lt lt i n k lt n i 1 i 2 i n k n 1 0 lt j 1 lt j 2 lt lt j k 1 lt n j 1 j 2 j k 1 1 displaystyle s n k sum 0 lt i 1 lt i 2 lt ldots lt i n k lt n i 1 i 2 cdots i n k n 1 sum 0 lt j 1 lt j 2 lt ldots lt j k 1 lt n j 1 j 2 cdots j k 1 1 nbsp und die rekursive Formel s n 1 k s n k 1 n s n k displaystyle s n 1 k s n k 1 n s n k nbsp mit den Anfangsbedingungen s n n 1 displaystyle s n n 1 nbsp und s n k 0 displaystyle s n k 0 nbsp fur k 0 lt n displaystyle k 0 lt n nbsp oder n lt k displaystyle n lt k nbsp Weitere spezielle Werte sind s n 1 n 1 displaystyle s n 1 n 1 nbsp s n 2 n 1 H n 1 displaystyle s n 2 n 1 H n 1 nbsp Folge A000254 in OEIS s n 3 1 2 n 1 H n 1 2 H n 1 2 displaystyle s n 3 tfrac 1 2 n 1 H n 1 2 H n 1 2 nbsp Folge A000399 in OEIS s n n 3 n 4 n 2 1 48 n 2 n 1 2 n 2 n 3 displaystyle s n n 3 tbinom n 4 tbinom n 2 tfrac 1 48 n 2 n 1 2 n 2 n 3 nbsp Folge A001303 in OEIS s n n 2 1 24 n n 1 n 2 3 n 1 displaystyle s n n 2 tfrac 1 24 n n 1 n 2 3n 1 nbsp Folge A000914 in OEIS s n n 1 n 2 1 2 n n 1 displaystyle s n n 1 tbinom n 2 tfrac 1 2 n n 1 nbsp fur alle n gt 0 displaystyle n gt 0 nbsp wobei H n 1 1 1 2 1 n 1 1 displaystyle H n 1 1 1 2 1 n 1 1 nbsp die n 1 displaystyle n 1 nbsp te harmonische Zahl und H n 1 2 1 2 2 2 n 1 2 displaystyle H n 1 2 1 2 2 2 n 1 2 nbsp eine verallgemeinerte harmonische Zahl ist Allgemein kann s n n k displaystyle s n n k nbsp als Polynom in n displaystyle n nbsp vom Grad 2 k displaystyle 2k nbsp aufgefasst werden Es hat den Leitkoeffizienten 1 2 k k displaystyle 1 2 k k nbsp und enthalt fur alle k gt 0 displaystyle k gt 0 nbsp die Faktoren n n 1 n k und fur ungerade k gt 1 displaystyle k gt 1 nbsp die Faktoren n2 und n 1 2 Das Polynom ps k n s n 1 n k n 1 n n k displaystyle psi k n s n 1 n k bigl n 1 n cdots n k bigr nbsp in n displaystyle n nbsp vom Grad k displaystyle k nbsp wird auch als Stirling Polynom bezeichnet 7 siehe auch Abschnitt Stirling Polynome Erzeugende Funktionen sind n 0 s n k t n n 1 k log 1 t k displaystyle sum n 0 infty s n k frac t n n frac 1 k bigl log 1 t bigr k nbsp und k 0 n 0 s n k t n n u k 1 t u displaystyle sum k 0 infty sum n 0 infty s n k frac t n n u k 1 t u nbsp und k 0 n s n k x k x n displaystyle sum k 0 n s n k x k x n nbsp mit der steigenden Faktoriellen x n x x 1 x n 1 displaystyle x n x x 1 cdots x n 1 nbsp Ist p displaystyle p nbsp eine Primzahl dann ist s p k displaystyle s p k nbsp fur 1 lt k lt p displaystyle 1 lt k lt p nbsp durch p displaystyle p nbsp teilbar 8 und fur gerade k lt p 1 displaystyle k lt p 1 nbsp durch p 2 displaystyle p 2 nbsp teilbar Nielsen 1893 9 Der Satz von Wolstenholme ist der Spezialfall k 2 displaystyle k 2 nbsp Da n displaystyle n nbsp die Anzahl aller Permutationen einer n displaystyle n nbsp elementigen Menge ist folgt k 0 n s n k n displaystyle sum k 0 n s n k n nbsp und insbesondere s n k n displaystyle s n k leq n nbsp direkt aus der Definition von s n k displaystyle s n k nbsp Fur jedes n gt 2 displaystyle n gt 2 nbsp existiert ein m n displaystyle m n nbsp so dass s n 0 lt s n 1 lt lt s n m n 1 lt s n m n gt s n m n 1 gt gt s n n displaystyle s n 0 lt s n 1 lt ldots lt s n m n 1 lt s n m n gt s n m n 1 gt ldots gt s n n nbsp und m n 1 m n displaystyle m n 1 m n nbsp oder m n 1 m n 1 displaystyle m n 1 m n 1 nbsp Erdos 1953 10 Fur jedes n displaystyle n nbsp ist die Folge s n 0 s n 1 s n n displaystyle s n 0 s n 1 s n n nbsp streng logarithmisch konkav 11 das heisst s n k 2 gt s n k 1 s n k 1 displaystyle s n k 2 gt s n k 1 s n k 1 nbsp fur 0 lt k lt n displaystyle 0 lt k lt n nbsp Das asymptotische Verhalten von s n k displaystyle s n k nbsp unter der Annahme k o log n displaystyle k o log n nbsp ist s n k n 1 k 1 g log n k 1 displaystyle s n k sim frac n 1 k 1 gamma log n k 1 nbsp mit der Euler Mascheroni Konstante g displaystyle gamma nbsp Stirling Zahlen zweiter Art BearbeitenDie Stirling Zahl zweiter Art S n k displaystyle S n k nbsp ist die Anzahl der k displaystyle k nbsp elementigen Partitionen einer n displaystyle n nbsp elementigen Menge also die Anzahl der Moglichkeiten eine n displaystyle n nbsp elementige Menge in k displaystyle k nbsp nichtleere disjunkte Teilmengen aufzuteilen S n k displaystyle S n k nbsp ist auch die Anzahl der Moglichkeiten n displaystyle n nbsp unterscheidbare Balle auf k displaystyle k nbsp nicht unterscheidbare Facher aufzuteilen so dass mindestens ein Ball in jedem Fach liegt Sind die Facher unterscheidbar so erhalt man k S n k displaystyle k S n k nbsp Moglichkeiten dies ist auch die Anzahl surjektiver Abbildungen einer n displaystyle n nbsp elementigen Menge auf eine k displaystyle k nbsp elementige Menge Beispiel Bearbeiten Die Menge a b c d displaystyle a b c d nbsp mit n 4 displaystyle n 4 nbsp Elementen kann auf folgende Weisen in k 2 displaystyle k 2 nbsp nichtleere disjunkte Teilmengen zerlegt werden a b c d a c b d a d b c displaystyle a b c d a c b d a d b c nbsp a b c d a b d c a c d b b c d a displaystyle a b c d a b d c a c d b b c d a nbsp Also ist S 4 2 7 displaystyle S 4 2 7 nbsp Eigenschaften Bearbeiten Es gelten die expliziten Formeln S n k 1 k j 0 k 1 k j k j j n displaystyle S n k frac 1 k sum j 0 k 1 k j binom k j j n nbsp undS n k 1 i 1 i 2 i n k k i 1 i 2 i n k c 1 c 2 c k n k 1 c 1 2 c 2 k c k 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 nbsp mit ganzzahligen nichtnegativen c 1 c 2 c k displaystyle c 1 c 2 c k nbsp und die rekursive Formel S n 1 k S n k 1 k S n k displaystyle S n 1 k S n k 1 k S n k nbsp mit den Anfangsbedingungen S n n 1 displaystyle S n n 1 nbsp und S n k 0 displaystyle S n k 0 nbsp fur k 0 lt n displaystyle k 0 lt n nbsp oder n lt k displaystyle n lt k nbsp Weitere spezielle Werte sind S n 1 1 displaystyle S n 1 1 nbsp S n 2 2 n 1 1 displaystyle S n 2 2 n 1 1 nbsp S n 3 1 2 3 n 1 2 n 1 displaystyle S n 3 tfrac 1 2 3 n 1 2 n 1 nbsp Folge A000392 in OEIS S n n 3 n 4 n 2 2 1 48 n n 1 n 2 2 n 3 2 displaystyle S n n 3 tbinom n 4 tbinom n 2 2 tfrac 1 48 n n 1 n 2 2 n 3 2 nbsp Folge A001297 in OEIS S n n 2 1 24 n n 1 n 2 3 n 5 displaystyle S n n 2 tfrac 1 24 n n 1 n 2 3n 5 nbsp Folge A001296 in OEIS S n n 1 n 2 1 2 n n 1 displaystyle S n n 1 tbinom n 2 tfrac 1 2 n n 1 nbsp fur alle n gt 0 displaystyle n gt 0 nbsp Auch S n n k displaystyle S n n k nbsp kann als Polynom in n displaystyle n nbsp vom Grad 2 k displaystyle 2k nbsp aufgefasst werden Es hat den Leitkoeffizienten 1 2 k k displaystyle 1 2 k k nbsp und enthalt fur alle k gt 0 displaystyle k gt 0 nbsp die Faktoren n n 1 n k und fur ungerade k gt 1 displaystyle k gt 1 nbsp die Faktoren n k 2 und n k 1 2 Man erhalt dasselbe Stirling Polynom k displaystyle k nbsp ten Grades wie bei den Stirling Zahlen erster Art mittels 1 k ps k n S n k n 1 n k n k 1 n 1 displaystyle 1 k psi k n S n k n 1 bigl n k n k 1 cdots n 1 bigr nbsp Erzeugende Funktionen sind n 0 S n k t n n 1 k e t 1 k displaystyle sum n 0 infty S n k frac t n n frac 1 k e t 1 k nbsp und k 0 n 0 S n k t n n u k e e t 1 u displaystyle sum k 0 infty sum n 0 infty S n k frac t n n u k e e t 1 u nbsp und n 0 S n k u n u k 1 u 1 2 u 1 k u displaystyle sum n 0 infty S n k u n frac u k 1 u 1 2u cdots 1 ku nbsp und k 0 n S n k x k x n displaystyle sum k 0 n S n k x k x n nbsp mit der fallenden Faktoriellen x n x x 1 x n 1 displaystyle x n x x 1 cdots x n 1 nbsp Ist p displaystyle p nbsp eine Primzahl dann ist S p k displaystyle S p k nbsp fur 1 lt k lt p displaystyle 1 lt k lt p nbsp durch p displaystyle p nbsp teilbar 12 Da die Bellsche Zahl B n displaystyle B n nbsp die Anzahl aller Partitionen einer n displaystyle n nbsp elementigen Menge ist gilt k 0 n S n k B n displaystyle sum k 0 n S n k B n nbsp Die Bernoulli Zahl bn erhalt man als die alternierende Summe k 0 n 1 k k k 1 S n k b n displaystyle sum k 0 n 1 k frac k k 1 S n k beta n nbsp Mit Hilfe der Rekursionsformel kann man zeigen dass fur jedes n gt 2 displaystyle n gt 2 nbsp ein m n displaystyle m n nbsp existiert so dass S n 0 lt S n 1 lt lt S n m n 1 S n m n gt S n m n 1 gt gt S n n displaystyle S n 0 lt S n 1 lt ldots lt S n m n 1 leq S n m n gt S n m n 1 gt ldots gt S n n nbsp und m n 1 m n displaystyle m n 1 m n nbsp oder m n 1 m n 1 displaystyle m n 1 m n 1 nbsp gilt Es ist eine offene Frage ob ein n gt 2 displaystyle n gt 2 nbsp existiert fur das der Fall S n m n 1 S n m n displaystyle S n m n 1 S n m n nbsp eintritt 13 Fur jedes n displaystyle n nbsp ist die Folge S n 0 S n 1 S n n displaystyle S n 0 S n 1 S n n nbsp streng logarithmisch konkav 11 das heisst S n k 2 gt S n k 1 S n k 1 displaystyle S n k 2 gt S n k 1 S n k 1 nbsp fur 0 lt k lt n displaystyle 0 lt k lt n nbsp Beziehung zwischen den Stirling Zahlen erster und zweiter Art BearbeitenAus den Beziehungen x n k 0 n S n k x k displaystyle x n sum k 0 n S n k x k nbsp und x n k 0 n 1 n k s n k x k displaystyle x n sum k 0 n 1 n k s n k x k nbsp die auch haufig 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 heisst dass die unteren Dreiecksmatrizen S n k n k displaystyle bigl S n k bigr n k nbsp und 1 n k s n k n k displaystyle bigl 1 n k s n k bigr n k nbsp zueinander inverse Matrizen sind i 0 S n i 1 i k s i k d n k i 0 1 n i s n i S i k 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 nbsp mit dem Kronecker Delta d n k 1 displaystyle delta n k 1 nbsp fur n k displaystyle n k nbsp und d n k 0 displaystyle delta n k 0 nbsp fur n k displaystyle n neq k nbsp Die Stirlingzahlen erster und zweiter Art lassen sich jeweils durch die anderen darstellen Schlomilch 1852 14 1 n k s n k j 0 n k 1 j n j 1 k 1 2 n k n k j S n k j j 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 nbsp undS n k j 0 n k 1 j n j 1 k 1 2 n k n k j 1 n k s n k j j 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 nbsp Die Stirlingzahlen konnen eindeutig so auf negative ganze Indizes n displaystyle n nbsp und k displaystyle k nbsp fortgesetzt werden dass die Rekursionsformeln s n 1 k s n k 1 n s n k displaystyle s n 1 k s n k 1 n s n k nbsp und S n 1 k S n k 1 k S n k displaystyle S n 1 k S n k 1 k S n k nbsp allgemein gelten und S n k 0 s n k displaystyle S n k 0 s n k nbsp fur n lt k 0 displaystyle n lt k 0 nbsp Man erhalt die fur alle ganzen Zahlen n displaystyle n nbsp und k displaystyle k nbsp gultige Dualitat S n k s k n displaystyle S n k s k n nbsp die auch die beiden Rekursionsformeln ineinander uberfuhrt ausserdem S n k 0 s n k displaystyle S n k 0 s n k nbsp fur n k lt 0 displaystyle n text k lt 0 nbsp Setzt man in die als Polynome in n displaystyle n nbsp aufgefassten S n n k displaystyle S n n k nbsp und s n n k displaystyle s n n k nbsp fur n displaystyle n nbsp negative ganze Zahlen ein so erhalt man dieselbe Fortsetzung auf negative ganze Indizes und fur die Polynome die Dualitat 15 S n n k s k n k n k displaystyle S n n k s k n k n k nbsp Analogie zu den Binomialkoeffizienten BearbeitenFur die Binomialkoeffizienten gilt n 1 k n k 1 n k displaystyle binom n 1 k binom n k 1 binom n k nbsp Die Karamata Notation betont die Analogie n 1 k n k 1 n n k displaystyle Bigl n 1 atop k Bigr Bigl n atop k 1 Bigr n Bigl n atop k Bigr nbsp n 1 k n k 1 k n k displaystyle Bigl n 1 atop k Bigr Bigl n atop k 1 Bigr k Bigl n atop k Bigr nbsp Entsprechend lassen sich die Stirling Zahlen in einem Dreiecksschema ahnlich dem Pascalschen Dreieck anordnen und zeilenweise berechnen Dreieck fur Stirling Zahlen erster Art erste Zeile n 1 displaystyle n 1 nbsp erste Spalte k 1 displaystyle k 1 nbsp 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 fur Stirling Zahlen zweiter Art erste Zeile n 1 displaystyle n 1 nbsp erste Spalte k 1 displaystyle k 1 nbsp 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 n k displaystyle k tbinom n k nbsp injektive und n k n displaystyle textstyle n bigl k atop n bigr nbsp surjektive Funktionen mit k displaystyle k nbsp elementiger Definitions und n displaystyle n nbsp elementiger Zielmenge 16 Stirling Polynome BearbeitenDie im Abschnitt Stirling Zahlen erster Art eingefuhrten Stirling Polynome werden auch durch die erzeugenden Funktionen t 1 e t x 1 1 x 1 k 0 ps k x t k 1 displaystyle Bigl frac t 1 e t Bigr x 1 1 x 1 sum k 0 infty psi k x t k 1 nbsp und log 1 t t x 1 x k 0 ps k x k t k 1 displaystyle Bigl frac log 1 t t Bigr x 1 x sum k 0 infty psi k x k t k 1 nbsp beschrieben die man durch Verallgemeinerung erzeugender Funktionen von S n k displaystyle S n k nbsp und s n k displaystyle s n k nbsp erhalt Nach einer anderen Definition werden die Polynome S 0 x 1 displaystyle S 0 x 1 nbsp und S k x k x 1 ps k 1 x displaystyle S k x k x 1 psi k 1 x nbsp als Stirling Polynome bezeichnet Die Polynome ps0 x ps1 x ps6 x sind 1 2 displaystyle tfrac 1 2 nbsp 1 24 3 x 2 displaystyle tfrac 1 24 3x 2 nbsp 1 48 x 1 x displaystyle tfrac 1 48 x 1 x nbsp 1 5760 15 x 3 15 x 2 10 x 8 displaystyle tfrac 1 5760 15x 3 15x 2 10x 8 nbsp 1 11520 x 1 x 3 x 2 x 6 displaystyle tfrac 1 11520 x 1 x 3x 2 x 6 nbsp 1 2903040 63 x 5 315 x 3 224 x 2 140 x 96 displaystyle tfrac 1 2903040 63x 5 315x 3 224x 2 140x 96 nbsp 1 5806080 x 1 x 9 x 4 18 x 3 57 x 2 34 x 80 displaystyle tfrac 1 5806080 x 1 x 9x 4 18x 3 57x 2 34x 80 nbsp und spezielle Werte fur k gt 0 displaystyle k gt 0 nbsp sind ps k 1 b k 1 k 1 k 1 displaystyle psi k 1 beta k 1 k 1 k 1 nbsp und ps k 0 b k 1 k 1 displaystyle psi k 0 beta k 1 k 1 nbsp mit der Bernoulli Zahl bk 1 7 Berechnet werden konnen die Polynome mit den Formeln ps k x j 0 k C k 1 j 2 k 2 j x k 1 k j displaystyle psi k x sum j 0 k frac C k 1 j 2k 2 j x k 1 k j nbsp und 1 k ps k x j 0 k C k 1 j 2 k 2 j x 2 k j displaystyle 1 k psi k x sum j 0 k frac overline C k 1 j 2k 2 j x 2 k j nbsp mit den durch C 1 0 1 displaystyle C 1 0 1 nbsp C k j 0 displaystyle C k j 0 nbsp fur j 0 1 k 1 und C k 1 j 2 k 1 j C k j 1 C k j displaystyle C k 1 j 2k 1 j C k j 1 C k j nbsp siehe Folge A111999 in OEIS 17 und den durch C 1 0 1 C k j 0 fur j 0 1 k 1 und C k 1 j k 1 j C k j 1 2 k 1 j C k j displaystyle overline C k 1 j k 1 j overline C k j 1 2k 1 j overline C k j nbsp rekursiv definierten ganzzahligen Koeffizienten 18 Fur k gt 0 displaystyle k gt 0 nbsp erhalt man s n n k j 0 k 1 C k j n 2 k j displaystyle s n n k sum j 0 k 1 C k j binom n 2k j nbsp und S n n k j 0 k 1 C k j n 2 k j displaystyle S n n k sum j 0 k 1 overline C k j binom n 2k j nbsp Diese Berechnung von s n n k displaystyle s n n k nbsp und S n n k displaystyle S n n k nbsp ist besonders fur grosse n displaystyle n nbsp und kleine k displaystyle k nbsp effizient Programmierbeispiel BearbeitenDie Stirling Zahlen lassen sich sehr einfach in einer rekursiven Methode implementieren Beispielsweise konnen in Java die Stirling Zahlen zweiter Art folgendermassen implementiert werden Verlauf des Programmes Wenn n k 0 ist wird 1 zuruckgegeben Wenn n 0 und k gt 0 ist oder n gt 0 und k 0 wird 0 zuruckgegeben Wenn n und k beide grosser als 0 sind wird dieselbe Funktion zwei Mal in veranderter Form rekursiv aufgerufen und zuruckgegeben Wenn alle anderen Abfragen scheitern heisst 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 amp amp k 0 return 1 else if n 0 amp amp k gt 0 n gt 0 amp amp k 0 return 0 else if n gt 0 amp amp k gt 0 return stirling n 1 k 1 k stirling n 1 k throw new IllegalArgumentException Weder n noch k darf negativ sein Literatur BearbeitenNiels Nielsen Fakultaten und Fakultatenkoeffizienten Kapitel 5 in Handbuch der Theorie der Gammafunktion B G Teubner Leipzig 1906 S 66 78 Umrechnung C n p s n n p displaystyle C n p s n n p nbsp und C n p S n 1 p n 1 displaystyle mathfrak C n p S n 1 p n 1 nbsp 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 S n m s m 1 m 1 n displaystyle S n m s m 1 m 1 n nbsp und s n m S m n m displaystyle sigma n m S m n m nbsp im Internet Archiv Jahrbuch Bericht Karoly 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 S n m 1 n m s n m displaystyle S n m 1 n m s n m nbsp und S n m S n m displaystyle mathfrak S n m S n m nbsp 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 Bearbeiten 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 Nielsen Fakultaten und Fakultatenkoeffizienten 1906 S 66 67 Niels Nielsen Recherches sur les polynomes et les nombres de Stirling Annali di matematica pura ed applicata 10 1904 S 287 318 franzosisch Henry W Gould Noch einmal die Stirlingschen Zahlen Jahresbericht der DMV 73 1971 72 S 149 152 a b Donald E Knuth Two notes on notation The American Mathematical Monthly 99 1992 S 403 422 englisch Zentralblatt Rezension Jovan Karamata Theoremes sur la sommabilite exponentielle et d autres sommabilites s y rattachant 21 Mai 1932 Mathematica Cluj 9 1935 S 164 178 franzosisch Zentralblatt Rezension a b Nielsen Fakultaten und Fakultatenkoeffizienten 1906 S 72 ff Comtet Advanced combinatorics 1974 S 218 Niels Nielsen Om Potenssummer af hele Tal Nyt Tidsskrift for Mathematik B 4 1893 S 1 10 danisch Formel 17 auf S 4 mit A n p s n 1 n 1 p displaystyle A n p s n 1 n 1 p nbsp Jahrbuch Bericht Paul Erdos On a conjecture of Hammersley Journal of the London Mathematical Society 28 1953 S 232 236 englisch nur der Beweis fur s n m n 1 s n m n displaystyle s n m n 1 neq s n m n nbsp ist nicht elementar Zentralblatt Rezension 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 Comtet Advanced combinatorics 1974 S 219 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 Oskar Schlomilch Recherches sur les coefficients des facultes analytiques Journal fur die reine und angewandte Mathematik 44 1852 S 344 355 franzosisch Formel 14 auf S 346 mit C k n s n n k displaystyle C k n s n n k nbsp und C k n S n k n displaystyle C k n S n k n nbsp Ira Gessel Richard P Stanley Stirling polynomials PDF Datei 534 kB Journal of combinatorial theory A 24 1978 S 24 33 englisch Zentralblatt Rezension Antal E Fekete Apropos Two notes on notation The American Mathematical Monthly 101 Oktober 1994 S 771 778 englisch Zentralblatt Rezension Jordan Stirling s numbers 1979 S 147 153 Jordan Stirling s numbers 1979 S 168 173Weblinks Bearbeiten nbsp Wikiversity Eine Vorlesung uber 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 Berechnungsmoglichkeit Set Partitions Stirling Numbers in der NIST Digital Library of Mathematical Functions englisch Abgerufen von https de wikipedia org w index php title Stirling Zahl amp oldid 230068435