DISKRETE MATHEMATIK
Erich Prisner
Sommersemester 2000

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

k-Partitionen der Menge {1,2,...,n} haben entweder {n} als Element der Partition (also als ein P_i), 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 P_i in dem es liegt eliminieren---dieses P_i 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 P_i 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.