Logo

DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

Stirling-Zahlen der zweiten Art

Für natürliche Zahlen 0 k n ist die Stirling-Zahl zweiter Art S(n,k) die Anzahl der k-Partitionen einer n-elementigen Menge.

Diese Zahl hängt mit der Anzahl der surjektiven Abbildungen von {1,2,...,n} nach {1,2,...,k} zusammen. Für jede solche surjektive Abbildung f ist natürlich {f-1({1}),f-1({2}),..., f-1({k}) eine k-Partition von {1,2,...,n}. Umgekehrt kann man für jede k-Partition k! solche surjektive Abbildungen konstruieren. Nach dem Prinzip der doppelten Abzählung gibt es also k! S(n,k) solche surjektive Abbildungen. Wenn wir diese Formel mit einer anderen Formel über die Zahl solcher surjektiver Abbildungen vergleichen, so erhalten wir

S(n,k) = 1
k!


0 i k 
(-1)i (
k
i
) (k-i)n.

Aber gemach! Vielleicht hätten wir mit der Rekursionsformel anfangen sollen. Zuerst einmal machen wir uns klar daß 0=S(n,0), 1=S(n,1) und 1=S(n,n) für n 1.

k-Partitionen der Menge {1,2,...,n} haben entweder {n} als Element der Partition (also als ein Pi), oder nicht. Im ersten Fall hat die k-Partition Typ 1, andernfalls Typ 2. Offenbar gibt es S(n-1,k-1) k-Partitionen vom Typ 1. Aus jeder k-Partition vom Typ 2 erzeugen wir eine k-Partition von {1,2,...,n-1} indem wir n aus dem Pi in dem es liegt eliminieren---dieses Pi enthält ja mindestens 2 Elemente. Umgekehrt können wir aus jeder k-Partition von {1,2,...,n-1} k k-Partitionen von {1,2,...,n} vom Typ 2 erzeugen, je nachdem, in welche der Mengen Pi das Element n kommt. Mit dem Prinzip der doppelten Abzählung gibt es also k S(n-1,k) k-Partitionen von {1,2,...,n} vom Typ 2, also ist

S(n,k) = k S(n-1,k) + S(n-1,k-1).

Man rechnet einfach (??) nach, daß obige Gleichung diese Rekursionsgleichung erfüllt. Muss ja.


Zurück zu Anzahlen.
Erich Prisner
File partially translated from TEX by T TH, version 2.53.
erstellt im Februar 2000.