Stirling-Zahl

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

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:
3 Stirling Zahlen zweiter Art
- 3.1 Beispiel:
- 3.2 Explizite Formel
4 Beweis
5 Alternative Herleitung
6 Analogie zu den Binomialkoeffizienten
7 Literatur

[Bearbeiten] Notation

Für die Stirlingzahlen existieren mehrere Notationsvarianten nebeneinander. Stirlingzahlen der ersten Art werden mit einem kleinen s geschrieben oder mit $\left[\right]$ Klammer geschrieben, Stirlingzahlen der zweiten Art werden mit großen S oder Mengenklammern $\left\{ \right\}$ geschrieben:

$s(n,r)=\left[\begin{matrix} n \\ r \end{matrix}\right].$

$S(n,r)= S_n^{(r)} = \left\{\begin{matrix} n \\ r \end{matrix}\right\}.$

Die Klammernotation wurde 1935 von Jovan Karamata in Analogie zu den Binomialkoeffizienten eingeführt und später von Donald Knuth populär gemacht. Die Klammernotation wird auch Karamata-Notation genannt.

[Bearbeiten] Stirling Zahlen erster Art

Die Stirling Zahl erster Art $s\left(n,r\right)$ beschreibt die Anzahl der unterschiedlichen Möglichkeiten eine Permutation mit $n$ Elementen in $r$ Zyklen zu zerlegen.

[Bearbeiten] Beispiel:

Die Menge $M {a, b, c, d}$ mit $\left|M\right| = n = 4$ kann auf folgende Weise in zwei Zyklen $(r = 2)$ zerlegt 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}$

$s\left(4,2\right)=11$

Da das Aufschreiben aller möglichen Zyklen recht aufwendig ist und mit der Anzahl der Elemente immer unübersichtlicher wird, gibt es eine rekursive Formel, um $s (n, r)$ zu berechnen:

$s\left(n,r\right) = s \left(n-1,r-1\right) + \left(n-1\right)s\left(n-1,r\right)$

mit den Anfangsbedingungen

$s\left(0,0\right) = 1$

$s\left(n,n\right) = 1$

$s\left(n,0\right) = 0\qquad\forall n > 0$

$s\left(0,r\right) = 0\qquad\forall r > 0$

[Bearbeiten] Stirling Zahlen zweiter Art

Die Stirling Zahl zweiter Art $S\left(n,r\right)$ beschreibt die Anzahl der unterschiedlichen Möglichkeiten aus einer Menge mit $n$ Elementen $r$ nichtleere, disjunkte Teilmengen zu bilden. Jede solche Möglichkeit ist eine Partition mit $r$ Teilmengen.

[Bearbeiten] Beispiel:

Die Menge $M = {a, b, c, d}$ mit $\left|M\right| = n = 4$ kann auf folgende Weise in $r = 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}$

$S\left(4,2\right)=7$

Da das Aufschreiben aller möglichen Partitionen recht aufwendig ist und mit der Anzahl der Elemente immer unübersichtlicher wird, gibt es eine rekursive Formel, um $S (n, r)$ zu berechnen:

$S\left(n,r\right) = S\left(n-1,r-1\right) + rS\left(n-1,r\right)$

mit den Anfangsbedingungen

$S\left(0,0\right) = 1$

$S\left(n,n\right) = 1$

$S\left(n,0\right) = 0\qquad\forall n > 0$

$S\left(0,r\right) = 0\qquad\forall r > 0$

[Bearbeiten] Explizite Formel

$S(n,r)=\frac{1}{r!}\sum_{j=0}^{r}(-1)^{j}{r \choose j}(r-j)^n$

Beispiele

S (10,4) = 34.105; S (19,4) = 11.259.666.950

[Bearbeiten] Beweis

Sei a ein fest gewähltes Element der $n$ -elementigen Menge $M$ . Die $r$ Partitionen von $M$ können nun danach klassifiziert werden, ob ${a}$ selber eine Klasse der Partition bildet oder nicht.

Trifft dies zu, so kann man aus $M\lbrace a\rbrace \left(M\setminus a\right)$ nur noch $r - 1$ Partitionen aus $n - 1$ Elementen bilden, also $S \left(n-1,r-1 \right)$ .

Bildet $\left\{a\right\}$ keine Klasse, so bedeutet dies, dass es $r$ Partitionen aus $n - 1$ Elementen gibt, also $S\left(n-1,r\right)$ . Da $a$ nun Element einer der Partitionen ist, es aber dafür $r$ Möglichkeiten gibt, ergibt sich die Multiplikation von $S\left(n-1,r\right)$ mit $r$ .

$S\left(n,r\right) = S\left(n-1,r-1\right) + r S\left(n-1,r\right)$

[Bearbeiten] Alternative Herleitung

Seien $V$ der Vektorraum aller reell- oder komplexwertigen Polynome und V_m der Unterraum der Polynome mit exaktem Grad m. Weiterhin seien q₀(x)=1, q₁(x)=x, ..., q_n(x)= x(x-1) $\cdots$ (x-n+1), ... und p₀(x)=1, p₁(x)=x, ..., p_n(x)= $x n$ , ... Basen für V_m. So gelten folgende Beziehungen:

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

2. $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 durchaus andere Vorzeichen auftreten, als in den zuvor gegebenen Definitionen.

[Bearbeiten] Analogie zu den Binomialkoeffizienten

Bei Verwendung der Karamatanotation sticht bei Betrachtung der Rekursionsformeln für die Stirlingzahlen der ersten und zweiten Art die Analogie zu den Binomialkoeffizienten ins Auge.

$\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:

                                 1

                              1     1

                           1     3     1

                        1     7     6     1

                     1     15     25     10   1

                  1     31     90    65    15    1

               1     ..    ..     ..    ..    ..    1

[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

Von „http://de.wikipedia.org../../../s/t/i/Stirling-Zahl_0bb0.html“

Kategorien: Kombinatorik | Zahl

Stirling-Zahl

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis

[Bearbeiten] Notation

[Bearbeiten] Stirling Zahlen erster Art

[Bearbeiten] Beispiel:

[Bearbeiten] Stirling Zahlen zweiter Art

[Bearbeiten] Beispiel:

[Bearbeiten] Explizite Formel

[Bearbeiten] Beweis

[Bearbeiten] Alternative Herleitung

[Bearbeiten] Analogie zu den Binomialkoeffizienten

[Bearbeiten] Literatur

Views

Navigation

Mitmachen

Suche

Andere Sprachen