Problem 26407 --【递推】Ⅴ.第二类Stirling数(例题)

26407: 【递推】Ⅴ.第二类Stirling数(例题)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][84kb]

Description

Ⅴ.第二类Stirling(斯特林)数

    【定义2】n个有区别的球放到m个相同的盒子中,要求无一空盒,其不同的方案数用S(n,m)表示,称为第二类Stirling数。

    下面就让我们根据定义来推导带两个参数的递推关系——第二类Stirling数。

    解:设有n个不同的球,分别用b1,b2,……bn表示。从中取出一个球bn,bn的放法有以下两种:

        ①bn独自占一个盒子;那么剩下的球只能放在m-1个盒子中,方案数为S2(n-1,m-1);

        ②bn与别的球共占一个盒子;那么可以事先将b1,b2,……bn-1这n-1个球放入m个盒子中,然后再将球bn可以放入其中一个盒子中,方案数为mS2(n-1,m)。

    综合以上两种情况,可以得出第二类Stirling数定理:

    【定理】S2(n,m)=mS2(n-1,m)+S2(n-1,m-1)   (n>1,m1)

    边界条件可以由定义2推导出:

     S2(n,0)=0;S2(n,1)=1;S2(n,n)=1;S2(n,k)=0(k>n)。      

Input

    两个正整数n和m,1=<n,m<=20。

Output

    第二类Stirling数 S(n,m),结果在long long范围内。

Sample Input

4 2

Sample Output

7

HINT

Source

[Submit][Status]