Stirling-Zahlen der zweiten Art

Grundlagen

Gegeben sei eine Menge von n benannten Objekten. Die Stirling-Zahlen der zweiten Art geben die Anzahl der möglichen Partitionen in k unbenannte nicht-leere Mengen an. Bspw:

Menge: 1 2 3 4

Mögliche Einteilungen:
1 2 ; 3 4
1 3 ; 2 4
1 4 ; 2 3
1 ; 2 3 4
2 ; 1 3 4 
3 ; 1 2 4
4 ; 1 2 3

Dh. wir erhalten für n=4 und k=2 eine Anzahl von 7 möglichen Partitionierungen der Menge.

Berechnung

Die Stirling-Zahlen zweiter Art werden folgendermaßen berechnet:

<m> delim{lbrace}{matrix{2}{1}n_k}{rbrace} = 1_k sum{j=0}{k}{(-1)^{k-j} (matrix{2}{1}k_j)j^n} </m>

Beispiel

Setzen wir die Zahlen von oben ein, erhalten wir:

<m> delim{lbrace}{matrix{2}{1}4_2}{rbrace} = 1_4 *( - (matrix{2}{1}2_0)0^4 + (matrix{2}{1}2_1)1^4 - (matrix{2}{1}2_2)2^4) = 1_4 * ( 0 -2 + 16) = 7 </m>

Aufgabe

Implementieren Sie eine Funktion in einer beliebigen Programmiersprache, die die Stirling-Zahlen der zweiten Art berechnet.

Mögliche Lösungen