• 周六. 10月 8th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

斯特林数

admin

11月 28, 2021

第二类斯特林数

为什么先讲第二类,因为基本都是考第二类

定义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;
}

卷也卷不过,躺又躺不平

发表回复

您的电子邮箱地址不会被公开。