|
组合数学中一个典型的问题是:把从1到n标号的n个球放到k个无区别的盒子里,要求每个盒子里至少有一个小球,问不同的放法数量。例如,如果用A、B、C、D分别表示4个球,要分成两组(即放入无区别的盒子里),其方法有7种:
{A,B},{C,D}
{A,C},{B,D}
{A,D},{B,C}
{A},{B,C,D}
{B},{A,C,D}
{C},{A,B,D}
{D},{A,B,C}
这个数量可以用第二类斯特林 (Stirling) 数来计算,表示为S(n,k),S(4,2)=7。第二类斯特林
(Stirling) 数也是计算机科学应用中很常见的公式。它有如下的递推公式:
http://img1.51cto.com/attachment/201105/230949145.png
整数参数n≥k≥0,且初始条件满足
http://img1.51cto.com/attachment/201105/231243496.png
式中http://img1.51cto.com/attachment/201105/231455266.png是Knuth推荐的第二类斯特林数的表示方式。
本题要求计算第二类斯特林数。(扩充:感兴趣的同学可以再看看相关的Bell数,以及第一类斯特林数)
输入:
参数n,k(n≥k≥0)
输出:
对应的第二类斯特林数值
样例输入:
4□2↵
样例输出:
7↵
|