Stirling数

第一类：

定义

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

  

和带符号第一类Stirling数

  

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

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

  

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

 

所以

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

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 int t;//测试数据数量

 int n;//苹果数

 int m; //盘子数

 int tot=;//最多有几种放法

 int f(int a,int b)

 {

     if(a<=||b<=)//当只有一个苹果或一个盘时，只有一种放法

     return ;

     if(a<b)

     return f(a,a);//苹果数<盘数，则最多只有b个盘有苹果

     else

     return f(a,b-)+f(a-b,b);///如果有一个不放，则有 f(a,b-1)种；如果每个都放，则相当于 f(a-b,b)

  }

 int main()

 {

     cin>>t;

     for(int i=;i<=t;i++)

     {

         cin>>m>>n;

         cout<<f(m,n)<<endl;

      }

     return ; }

Code

第二类：

定义

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

  

或者

  

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

 

所以：

 

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

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 int t;

 int n;

 int m;

 int tot=;

 int f(int a,int b)

 {

     if(a<=||b<=)

     return ;

     if(a<b)

     return f(a,a);

     else

     return f(a-,b-)+f(a-,b)*b;

  }

 int main()

 {

     cin>>t;

     for(int i=;i<=t;i++)

     {

         cin>>m>>n;

         cout<<f(m,n)<<endl;

      }

     return ;

 }