Einleitung

Die Stirling-Zahl zweiter Art \( S(n, k) \) gibt die Anzahl der \(k\)-elementigen Partitionen einer \(n\)-elementigen Menge an.

Eine Partition einer \(n\)-elementigen Menge kann höchstens \(n\) Blöcke enthalten. Daher ist

$$ S(n, k) = 0 \qquad \text{falls} \qquad k \gt n $$

Außerdem gibt es nur eine 1-Partition von \(n\) und eine \(n\)-Partition von \(n\).

$$ S(n, 1) = 1 \qquad \text{und} \qquad S(n,n) = 1 $$

Rekursive Berechnung

Alle weiteren Stirling-Zahlen zweiter Art können folgenderweise bestimmt werden.

$$ S(n, k) = S(n-1, k-1) + k \cdot S(n-1,k) $$

Beispiel

Die folgende Menge \( M \) mit \(n = 4\) Elementen kann in folgende 2-Partitionen zerlegt werden.

\begin{aligned} M = &\{a,b,c,d\} \\[4pt] 2\text{-Partitionen:} &\{\{a,b\},\{c,d\}\} \\[4pt] &\{\{a,c\},\{b,d\}\} \\[4pt] &\{\{a,d\},\{b,c\}\} \\[4pt] &\{\{a,b,c\},\{d\}\} \\[4pt] &\{\{a,b,d\},\{c\}\} \\[4pt] &\{\{a,c,d\},\{b\}\} \\[4pt] &\{\{b,c,d\},\{a\}\} \end{aligned}

Die Anzahl der 2-Partitionen beträgt \( 7 \). Dies kann mit Hilfe der Stirling-Zahl berechnet werden:

\begin{aligned} S(4,2) &= S(3,1) + 2 \cdot S(3,2) \\[4pt] &= 1 + 2 \cdot ( S(2,1) + 2 \cdot S(2,2) ) \\[4pt] &= 1 + 2 \cdot ( 1 + 2 \cdot 1 ) \\[4pt] &= 1 + 2 \cdot 3 \\[4pt] &= 7 \\[4pt] \end{aligned}

Tabelle

In der folgenden Tabelle befinden sich die Stirling-Zahlen für \( n \leq 8 \):

	\( S(1,k) \)	$$ 1 $$
	\( S(2,k) \)	$$ 1 \enspace\enspace 1 $$
	\( S(3,k) \)	$$ 1 \enspace\enspace 3 \enspace\enspace 1 $$
	\( S(4,k) \)	$$ 1 \enspace\enspace 7 \enspace\enspace 6 \enspace\enspace 1 $$
	\( S(5,k) \)	$$ 1 \enspace\enspace 15 \enspace\enspace 25 \enspace\enspace 10 \enspace\enspace 1 $$
	\( S(6,k) \)	$$ 1 \enspace\enspace 31 \enspace\enspace 90 \enspace\enspace 65 \enspace\enspace 15 \enspace\enspace 1 $$
	\( S(7,k) \)	$$ 1 \enspace\enspace 63 \enspace\enspace 301 \enspace\enspace 350 \enspace\enspace 140 \enspace\enspace 21 \enspace\enspace 1 $$
	\( S(8,k) \)	$$ 1 \enspace\enspace 127 \enspace\enspace 966 \enspace\enspace 1701 \enspace\enspace 1050 \enspace\enspace 266 \enspace\enspace 28 \enspace\enspace 1 $$

Quellen

• Wikipedia: Artikel über "Stirling-Zahl"

Name

(optional)

Email

(optional)

Spamschutz

=

Daten werden gesendet