第二类斯特林数
第二类 S t i r l i n g Stirling Stirling数实际上是集合的一个拆分，表示将 n n n个不同的元素拆分成 m m m个集合的方案数，记为 S ( n , m ) S(n,m) S(n,m)或者 { n m } {n\brace m} { mn}.常常用于解决组合数学中几类放球模型。描述为：将 n n n个不同的球放入 m m m个无差别的盒子中，要求盒子非空，有几种方案？
第二类 S t i r l i n g Stirling Stirling数要求盒子是无区别的，所以可以得到其方案数公式:
S ( n , m ) S(n,m) S(n,m) = 1 m ! ∑ k = 0 m ( − 1 ) k ( m k ) ( m − k ) n \frac{1}{m!}\sum_{k=0}^{m}(-1)^k\dbinom{m}{k}(m-k)^n m!1∑k=0m(−1)k(km)(m−k)n
递推式
第二类 S t i r l i n g Stirling Stirling数的推导和第一类 S t i r l i n g Stirling Stirling数类似，可以从定义出发考虑第 n + 1 n+1 n+1个元素的情况，假设要把 n + 1 n+1 n+1个元素分成 m m m个集合则分析如下：
（1）如果 n n n个元素构成了 m − 1 m-1 m−1个集合，那么第 n + 1 n+1 n+1个元素单独构成一个集合。方案数 S ( n , m − 1 ) S(n,m-1) S(n,m−1)。
（2）如果 n n n个元素已经构成了 m m m个集合，将第 n + 1 n+1 n+1个元素插入到任意一个集合。方案数 m*S(n,m) 。
综合两种情况得： S ( n + 1 , m ) = S ( n , m − 1 ) + m S ( n , m ) S(n+1,m)=S(n,m-1)+mS(n,m) S(n+1,m)=S(n,m−1)+mS(n,m)
应用举例
第二类 S t i r l i n g Stirling Stirling数主要是用于解决组合数学中的几类放球模型。主要是针对于球之前有区别的放球模型：
（1） n n n个不同的球，放入 m m m个无区别的盒子，不允许盒子为空。
方案数： S ( n , m ) S(n,m) S(n,m) 。这个跟第二类 S t i r l i n g Stirling Stirling数的定义一致。
（2） n n n个不同的球，放入 m m m个有区别的盒子，不允许盒子为空。
方案数： m ! S ( n , m ) m!S(n,m) m!S(n,m)。因盒子有区别，乘上盒子的排列即可。
（3） n n n个不同的球，放入 m m m个无区别的盒子，允许盒子为空。
方案数： ∑ k = 0 m S ( n , k ) \sum_{k=0}^{m}S(n,k) ∑k=0mS(n,k) 。枚举非空盒的数目便可。
（4） n n n个不同的球，放入 m m m个有区别的盒子，允许盒子为空。
①方案数： ∑ k = 0 m P ( m , k ) S ( n , k ) \sum_{k=0}^{m}P(m,k)S(n,k) ∑k=0mP(m,k)S(n,k) 。同样可以枚举非空盒的数目，注意到盒子有区别，乘上一个排列系数。
②既然允许盒子为空，且盒子间有区别，那么对于每个球有m种选择，每个球相互独立。有方案数： m n m^n mn
m n m^n mn= ∑ k = 0 m P ( m , k ) S ( n , k ) \sum_{k=0}^{m}P(m,k)S(n,k) ∑k=0mP(m,k)S(n,k)
上述式子可以应用于第二类 S t i r l i n g Stirling Stirling数通项的求解。
代码：
#include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10,mod=1e9+7; typedef long long ll; typedef pair<int,int> PII; int fac[N]; int ifac[N]; int binpower(int a,int b) { int res=1; while(b) { if(b&1) res=(res*a)%mod; a=a*a%mod; b/=2; } return res%mod; } int inv(int a) { return binpower(a,mod-2)%mod; } void init() { fac[0]=1; for(int i=1;i<=N;i++) fac[i]=fac[i-1]*i%mod; for(int i=0;i<=N;i++) ifac[i]=inv(fac[i])%mod; } int C(int n,int m) { if (m < 0 || m > n || n < 0) { return 0; } return ((fac[n]*ifac[n-m])%mod*ifac[m]%mod)%mod; } signed main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n,m; cin>>n>>m; init(); int S=0; for(int i=0;i<=m;i++) { int c=C(m,i); if(i%2==1) S=(S-c*binpower(m-i,n)%mod+mod)%mod; else S=(S+c*binpower(m-i,n)%mod)%mod; } S=S*ifac[m]%mod; cout<<S<<endl; return 0; } 讯享网
链接: problem
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/13139.html