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

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

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][84kb]

题目描述

Ⅴ.第二类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)。      

输入

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

输出

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

样例输入

4 2

样例输出

7

提示

来源

[提交][状态]