第二类斯特林(Stirling)数

问题描述:

组合数学中一个典型的问题是：把从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) 数也是计算机科学应用中很常见的公式。它有如下的递推公式： 整数参数n≥k≥0，且初始条件满足 式中 是Knuth推荐的第二类斯特林数的表示方式。 本题要求计算第二类斯特林数。（扩充：感兴趣的同学可以再看看相关的Bell数，以及第一类斯特林数） 输入： 参数n,k(n≥k≥0) 输出： 对应的第二类斯特林数值 样例输入： 4□2↵ 样例输出： 7↵

参考代码(java实现)：

1. import java.util.Scanner; 
2. public class Stirling{ 
3.     public static void main(String[] args) 
4.     { 
5.         Scanner cin; int n,k; 
6.         cin=new Scanner(System.in); 
7.         n=cin.nextInt(); k=cin.nextInt(); 
8.         System.out.println(Stirling(n,k)); 
9.     } 
10.     public static int Stirling(int n, int k) 
11.     { 
12.         if(n==1 && k==0) return 1;    
13.         else if( k==1 || n==k ) return 1;    
14.         else return Stirling(n-1, k)*k+Stirling(n-1, k-1); 
15.     } 
16. } 

转载于:https://blog.51cto.com/pengjh/568221