Problem 1241. -- 集合划分问题

1241: 集合划分问题

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 96  Solved: 41
[Submit][Status][Web Board]

Description

n个元素的集合{1,2,…,n}可以划分为若干个非空子集。例如,当n=4时,集合{1,2,3,4}可以划分为15个不同的非空子集如下:
{{1},{2},{3},{4}},{{1,2},{3},{4}},{{1,3},{2},{4}},{{1,4},{2},{3}},{{2,3},{1},{4}},{{2,4},{1},{3}},{{3,4},{1},{2}},{{1,2},{3,4}},{{1,3},{2,4}},{{1,4},{2,3}},{{1,2,3},{4}},{{1,2,4},{3}},{{1,3,4},{2}},{{2,3,4},{1}},{{1,2,3,4}}
其中,集合{{1,2,3,4}}由1个子集组成;集合{{1,2},{3,4}},{{1,3},{2,4}},{{1,4},{2,3}},{{1,2,3},{4}},{{1,2,4},{3}},{{1,3,4},{2}},{{2,3,4},{1}}由2个子集组成;集合{{1,2},{3},{4}},{{1,3},{2},{4}},{{1,4},{2},{3}},{{2,3},{1},{4}},{{2,4},{1},{3}},{{3,4},{1},{2}}由3个子集组成;集合{{1},{2},{3},{4}}由4个子集组成。

Input

给定正整数n和m,计算出n个元素的集合{1,2,…,n}可以划分为多少个不同的由m个非空子集组成的集合。

Output

计算出的不同的由m个非空子集组成的集合数

Sample Input

4 3

Sample Output

6

HINT

所求的是第2类Stirling数,通过可递推出如下递归式:

S(n,m)=mS(n-1,m)+S(n-1,m-1);

S(n,n+1)=0,S(n,0)=0,S(0,0)=1

Source

[Submit][Status]