stirling數

stirling數是將n個有區別的球放入k個無標號的盒子中( n>=k>=1，且盒子不允許為空)的方案數就是stirling數.(即含 n 個元素的集合劃分為 k 個集合的情況數)。

將n個有區別的球的球放入k個無標號的盒子中( n>=k>=1，且盒子不允許為空)的方案數就是stirling數.(即含 n 個元素的集合劃分為 k 個集合的情況數)
遞推公式:
S(n,0) = 0
S(n,1) = 1 (k = 1)
S(n,n) = 1
S(n,k) = 0 (k > n)
S(n,k) = S(n-1,k-1)+k*S(n-1,k) (n >= k >= 2)
分析：設有n個不同的球，分別用b1,b2,...,bn表示。從中取出一個球bn，bn的放法有以下兩種：
1.bn獨占一個盒子，那么剩下的球只能放在k-1個盒子裡，方案數為S（n-1,k-1);
2.bn與別的球共占一個盒子，那么可以將b1,b2,...,bn-1這n-1個球放入k個盒子裡，然後將bn放入其中一個盒子中，方案數為k*S(n-1,k).
附程式：
program stirling;
var f:array[0..10000,0..10000] of longint;
n,m,i,j:longint;
begin
readln(n,m);
for i:=1 to n do
begin
f[i,0]:=0;
f[i,1]:=1;
f[i,i]:=1;
for j:=i+1 to n do f[i,j]:=0;
end;
for i:=2 to n do
begin
for j:=2 to m do
f[i,j]:=j*f[i-1,j]+f[i-1,j-1];
end;
writeln(f[n,m]);
end.