Karamata-Notation

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

Notation

Für die Stirlingzahlen existieren mehrere Notationen. Stirlingzahlen der ersten Art werden mit kleinem s bezeichnet oder übereinander in eckigen Klammern geschrieben, Stirlingzahlen der zweiten Art werden mit großem S bezeichnet oder übereinander in geschweiften Klammern geschrieben:

$s_{n,k} = \left[\begin{smallmatrix} n \\ k \end{smallmatrix}\right]$

$S_{n,k} = S_n^{(k)} = \left\{\begin{smallmatrix} n \\ k \end{smallmatrix}\right\}$

Die Klammernotation wurde 1935 von Jovan Karamata in Analogie zu den Binomialkoeffizienten $\tbinom{n}{k}$ eingeführt und später von Donald Knuth populär gemacht. Sie wird auch Karamata-Notation genannt.

Stirling-Zahlen erster Art

Die Stirling-Zahl erster Art s_n,k ist die Anzahl der Permutationen einer n-elementigen Menge, die genau k Zykeln haben.

Beispiel

Die Menge {a,b,c,d} mit n = 4 Elementen kann auf folgende Weisen auf k = 2 Zykeln 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),\ (a)(b c d),\ (a)(b d c),\ (a b)(c d),\ (a c)(b d),\ (a d)(b c)$

Also ist s_4,2 = 11.

Berechnung

Es gilt die rekursive Formel

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

mit den Anfangsbedingungen

s_0,0 = 1 = s_n,n     und     s_n,0 = 0 = s_0,k     für alle   $n,\,k > 0.$

Insbesondere gilt s_n,1 = (n − 1)! und $s_{n,n-1} = \tfrac{1}{2}\,n\,(n-1)$ für alle n > 0.

Stirling-Zahlen zweiter Art

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.

Beispiel

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}}, {{b,c,d},{a}}, {{a,c,d},{b}}

Also ist S_4,2 = 7.

Berechnung

Es gelten die explizite Formel

$S_{n,k} = \frac{1}{k!} \sum_{j=0}^{k} (-1)^{k-j} \binom{k}{j} j^n$

und die rekursive Formel

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

mit den Anfangsbedingungen

S_0,0 = 1 = S_n,n     und     S_n,0 = 0 = S_0,k     für alle   $n,\,k > 0.$

Insbesondere gilt S_n,1 = 1, S_n,2 = 2^{n − 1} − 1 und $S_{n,n-1} = \tfrac{1}{2}\,n\,(n-1)$ für alle n > 0.

Beweis

Es sei a ein fest gewähltes Element der n-elementigen Menge M. Die k-Partitionen von M können nun danach klassifiziert werden, ob {a} ein Element der Partition ist oder nicht.

Trifft dies zu, so bleiben ohne {a} noch alle S_{n − 1,k − 1} möglichen (k − 1)-Partitionen aus den übrigen n − 1 Elementen von M.

Ist $\left\{a\right\}$ kein Element der Partition, erhält man nach Entfernung von a alle S_{n − 1,k} möglichen k-Partitionen der übrigen n − 1 Elemente von M. Da a in jeder der Möglichkeiten Element eines der Elemente der k-Partition ist und es dafür k Möglichkeiten gibt, sind es insgesamt $k\,S_{n-1,k}$ Möglichkeiten, also

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

Alternative Herleitung

Es seien V der Vektorraum aller reell- oder komplexwertigen Polynome und V_m der Unterraum der Polynome mit Grad $\leq m$. Weiterhin seien

$q_0(x)=1,\; q_1(x)=x, \;\ldots, q_n(x)= x(x-1)\cdots (x-n+1), \ldots$

und

$p_0(x)=1,\; p_1(x)=x, \ldots, p_n(x)= x^n \ldots$

Basen für V_m. So gelten folgende Beziehungen:

$q_{n}(x) = \sum_{k=0}^{n} s_{n,k} p_{k}(x)$

$p_{n}(x) = \sum_{k=0}^{n} S_{n,k} q_{k}(x)$

So können alternativ die Stirling-Zahlen 1. und 2. Art erzeugt werden, mit dem Unterschied, dass hier andere Vorzeichen auftreten als in den zuvor gegebenen Definitionen.

Analogie zu den Binomialkoeffizienten

Die Karamata-Notation betont die Analogie zu den Binomialkoeffizienten:

$\left[\begin{matrix} n \\ k \end{matrix}\right] = \left[\begin{matrix} n-1 \\ k-1 \end{matrix}\right] + (n-1) \left[\begin{matrix} n-1 \\ k \end{matrix}\right]$

$\left\{\begin{matrix} n \\ k \end{matrix}\right\} = \left\{\begin{matrix} n-1 \\ k-1 \end{matrix}\right\} + k \left\{\begin{matrix} n-1 \\ k \end{matrix}\right\}$

Für Binomialkoeffizienten gilt bekanntlich

$\left(\begin{matrix} n \\ k \end{matrix}\right) = \left(\begin{matrix} n-1 \\ k-1 \end{matrix}\right) + \left(\begin{matrix} n-1 \\ k \end{matrix}\right)$.

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

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

Dreieck für Stirling-Zahlen zweiter Art (erste Zeile n = 1, erste Spalte k = 1):

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

Gegenseitige Darstellung

Die Stirlingzahlen erster und zweiter Art lassen sich jeweils durch die anderen darstellen:

$\left[{n\atop k}\right] = (-1)^{n-k} \sum_{j=0}^{n-k} (-1)^j {n-1+j \choose n-k+j} {2n-k \choose n-k-j} \left\{ {n-k+j \atop j} \right\}$

und

$\left\{{n\atop k}\right\} = \sum_{j=0}^{n-k} (-1)^{n-k+j} {n-1+j \choose n-k+j} {2n-k \choose n-k-j} \left[ {n-k+j \atop j} \right].$

Literatur

• Manfred Wolff, Peter Hauck, Wolfgang Küchlin: Mathematik für Informatik und BioInformatik. Springer-Verlag, Berlin Heidelberg New-York, S.50, ISBN 3-540-20521-7

• Martin Aigner: Combinatorial Theory. Springer-Verlag, Originally published as volume 234 in the series: Grundlehren der mathematischen Wissenschaften, Reprint of the 1st ed. Berlin Heidelberg New York 1979, 1997, ISBN 978-3-540-61787-7

Weblinks

• Eric W. Weisstein: Stirling-Zahl erster Art auf MathWorld (englisch)
• Eric W. Weisstein: Stirling-Zahl zweiter Art auf MathWorld (englisch)
• Eric W. Weisstein: Stirling-Transformation auf MathWorld (englisch)
• Stirling-Zahlen erster Art: Folge A130534 in OEIS ohne Vorzeichen, Folge A008275 in OEIS mit Vorzeichen (englisch)
• Stirling-Zahlen zweiter Art: Folge A008277 in OEIS (englisch)