首页 > > 程序设计 > C/C++ >

Stirling数

2018-06-17 23:02:04来源：未知阅读 ()

第一类：

定义

第一类Stirling数表示表示将 n 个不同元素构成m个圆排列的数目。又根据正负性分为无符号第一类Stirling数

和带符号第一类Stirling数

。有无符号Stirling数分别表现为其升阶函数和降阶函数的各项系数[类似于二项式系数[3] ]，形式如下：

对于有无符号Stirling数之间的关系有

。组合数学中的第一类Stirling数一般指无符号的第一类Stirling数。意思是n个不同元素构成m个圆排列的方案数。

所以

f(a,b)=f(a,b-1)+f(a-b,b)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 int t;//测试数据数量
 7 int n;//苹果数 
 8 int m; //盘子数
 9 int tot=0;//最多有几种放法
10 int f(int a,int b)
11 {
12     if(a<=1||b<=1)//当只有一个苹果或一个盘时，只有一种放法 
13     return 1;
14     if(a<b)
15     return f(a,a);//苹果数<盘数，则最多只有b个盘有苹果
16     else 
17     return f(a,b-1)+f(a-b,b);///如果有一个不放，则有 f(a,b-1)种；如果每个都放，则相当于 f(a-b,b)
18  } 
19 int main()
20 {
21 
22     cin>>t;
23     for(int i=1;i<=t;i++)
24     {
25         cin>>m>>n;
26         cout<<f(m,n)<<endl;
27      } 
28     return 0; }

Code

第二类：

定义

第二类Stirling数实际上是集合的一个拆分，表示将n个不同的元素拆分成m个集合的方案数，记为

或者

。和第一类Stirling数不同的是，集合内是不考虑次序的，而圆排列是有序的。常常用于解决组合数学中几类放球模型。描述为：将n个不同的球放入m个无差别的盒子中，要求盒子非空，有几种方案？

所以：

f(n,m)=f(n-1,m-1)+f(n-1,m)*m

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 int t;
 7 int n;
 8 int m; 
 9 int tot=0;
10 int f(int a,int b)
11 {
12     if(a<=1||b<=1)
13     return 1;
14     if(a<b)
15     return f(a,a);
16     else 
17     return f(a-1,b-1)+f(a-1,b)*b;
18  } 
19 int main()
20 {
21 
22     cin>>t;
23     for(int i=1;i<=t;i++)
24     {
25         cin>>m>>n;
26         cout<<f(m,n)<<endl;
27      } 
28     return 0; 
29 }