Stirling-Zahl

aus Wikipedia, der freien Enzyklopädie

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

Inhaltsverzeichnis

1 Notation
2 Stirling-Zahlen erster Art
- 2.1 Beispiel
- 2.2 Berechnung
3 Stirling-Zahlen zweiter Art
- 3.1 Beispiel
- 3.2 Berechnung
4 Beweis
5 Alternative Herleitung
6 Analogie zu den Binomialkoeffizienten
7 Gegenseitige Darstellung
8 Literatur
9 Weblinks

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

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

[Bearbeiten] 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),\ (b c d)(a),\ (b d c)(a),\ (a b)(c d),\ (a c)(b d),\ (a d)(b c)$

Also ist $s 4,2 = 11$ .

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

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

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

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

[Bearbeiten] 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}$ .

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

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

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

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

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

Stirling-Zahl

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis

[Bearbeiten] Notation

[Bearbeiten] Stirling-Zahlen erster Art

[Bearbeiten] Beispiel

[Bearbeiten] Berechnung

[Bearbeiten] Stirling-Zahlen zweiter Art

[Bearbeiten] Beispiel

[Bearbeiten] Berechnung

[Bearbeiten] Beweis

[Bearbeiten] Alternative Herleitung

[Bearbeiten] Analogie zu den Binomialkoeffizienten

[Bearbeiten] Gegenseitige Darstellung

[Bearbeiten] Literatur

[Bearbeiten] Weblinks

Ansichten

Persönliche Werkzeuge

Suche

Navigation

Mitmachen

Buch erstellen

Werkzeuge

Andere Sprachen