第二类斯特林数
为什么先讲第二类，因为基本都是考第二类
定义1:(n)个不同的元素拆分成(m)个集合的方案数
定义2:(n)个不同的球放入(m)个无差别的盒子中，要求盒子非空，有几种方案？
两种定义显然是一样的，但是基本都是用定义2(我感觉)
怎么写呢其实本质上就是(dp)
设(dp[i][j])表示(i)个球放到(j)个盒子的方案数
那么(dp[i][j]=dp[i-1][j-1]+j*dp[i-1][j])
其实就是第(i)个球是否单独放在一个盒子中
如果单独放在一个盒子中，那么答案就是(dp[i-1][j-1])
如果不是单独放在一个盒子中，那么就有(j)个盒子可以放入答案就是(j*dp[i-1][j])
再来介绍一下第二类斯特林数的通项公式
(Large S2(n,m)=frac{1}{m!}sum_{k=0}^{m}(-1)^kC(m,k)(m-k)^n)
这个式子本质上就是利用到容斥的思路求的
首先假设(m)个盒子不同并且不考虑非空的情况下 答案即为(m^n)
但是里面包含空盒的情况
假设有(k)个空盒，那么答案即为(C(m,k)*(m-k)^n) 但是显然不能保证剩下的(m-k)个盒子为非空
那么就需要容斥 其实就是正负交替进行即可
最后除以(m!)的原因是因为第二类斯特林数的盒子都是相同的
再来扯一扯应用
1 (n)个不同的球，放入(m)个无区别的盒子，不允许盒子为空。
就是定义答案即为(S2(n,m))
2 (n)个不同的球，放入(m)个有区别的盒子，不允许盒子为空。
其实就是对盒子进行全排列即可 (m!*S2(n,m))
3 (n)个不同的球，放入(m)个无区别的盒子，允许盒子为空。
枚举放了几个盒子即可 (sum_{k=0}^m S2(n,k))
4 (n)个不同的球，放入(m)个有区别的盒子，允许盒子为空。
这个应该是最简单的了 每个球随便放 (m^n)
第一类斯特林数
这个不是很常用
定义(n) 个不同元素构成(m)个圆排列的数目
圆排列是啥呢，其实就是(1 2 3 4)和(2341)一样因为可以进行循环移位
这个求解也是(dp)
设(dp[i][j])表示前(i)个元素构成(j)个全排列
(dp[i][j]=dp[i-1][j-1]+(i-1)*dp[i-1][j-1])
也是分为两种情况是否单独是一个圆排列
如果单独一个圆排列 那么即为(dp[i-1][j-1])
不是单独圆排列 那么可以放在任意元素的左边 即为((i-1)*dp[i-1][j-1])
好像没有通项公式
放个第一类斯特林数的模板题 链接
题意如下
给出N个房间，每个房间的钥匙随机放在某个房间内，概率相同。有K次炸门的机会，求能进入所有房间的可能性
为多大。但是1号房间不能打开
思路 钥匙与门呈环形对应关系。打开一个门之后，环内的所有房间都可以进入。问题转变为N个房间形成1~K个环
的可能性有多大。因为1号门不能破坏，所以s(n,k)-s(n-1,k-1)为实际的构成k个环的方法数，也就是去掉1号独立成
环的情况。
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define debug printf(" I am here
");
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
mt19937 rnd(time(0));
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=20+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-10;
int n,k;
ll dp[maxn][maxn];
ll fac[maxn];
signed main(){
for(int i=0;i<=20;i++){
dp[0][i]=1;
if(i==0){
fac[i]=1;
}else{
fac[i]=fac[i-1]*i;
}
}
for(int i=1;i<=20;i++){
for(int j=1;j<=20;j++){
dp[i][j]=dp[i-1][j-1]+(i-1)*dp[i-1][j];
}
}
int _;scanf("%d",&_);
while(_--){
scanf("%d%d",&n,&k);
double ans=1.0*(dp[n][k]-dp[n-1][k-1])/fac[n];
printf("%.4f
",ans);
}
return 0;
}