第二类斯特林数

把$n$个不同的球放到$r$个相同的盒子里，假设没有空盒，则放球方案数记做$S(n, r)$或$S_n^r$，称为第二类 Stirling 数。

显然$S_n^1=1,S_n^0=0,S_n^n=1$

递推形式

考虑最后一个球，如果把它单独放一个盒子，则有$S(n-1,r-1)$种方案，如果把它同前面的某一个球放到同一个盒子，有$rS(n-1,r)$种方案

$S(n,r)=rS(n-1, r) + S(n-1,r-1)\ (n>r\ge 1)$

其他公式

$\large S(n,m)=\frac{1}{m!}\sum_{k=0}^m(-1)^kC_m^k(m-k)^n$，其中$C_m^k$为组合数$C(m, k)$

容斥原理可得上式，由于盒子相同，最后要除以$m!$

$\large n^k=\sum_{i=0}^k i!S(k,i)C(n,i)$

左边就是k个球可以任意放置在n个盒子里。 右边就是枚举非空盒子的数量i，那么把k个球放在i个盒子（盒子不同，需要乘上一个i!）里面再乘上选出i个非空盒子的方案数。

第一类斯特林数

$s(n,r)$是把$n$个不同的球排成$r$个非空循环排列的方法数

设多项式$x(x-1)(x-2)...(x-n+1)$，展开式型如$s_nx^n-s_{n-1}x^{n-1}+s_{n-2}x^{n-2}-...$

不考虑各项系数符号，$x^r$的系数的绝对值记作为$s(n,r)$，称为第一类斯特林数。

递推形式

$s(n,r)=(n-1)s(n-1,r)+s(n-1,r-1)\ (n>r\ge 1)$

考虑最后一个球，若它单独放一个圈，有$s(n-1,r-1)$种放法；若是放在前面的某一个球的左边，则有$(n-1)s(n-1,r)$种放法。

$s(0,0)=1, s(n,0)=0, s(n,n)=1$

例题 HDU 3625

有 n 个房间，编号为 1 到 n，每个房间对应有一把钥匙。现在把这 n 把钥匙随机地放在这 n 个房间中，并把门锁上。现在要将这 n 个房间的门都打开，你有 k 次把门炸开的机会，不过 1 号房间的门过于坚固炸不开。问能够成功打开所有门的概率。

---

也就是说，1号房间的钥匙不能在1号房内，且$n$个房间组成的环数不大于$k$

当$n$个房间组成$i$个环，有合法方案数$ans_i=s(n,i)-s(n-1,i-1)$，$s(n,i)$为$n$个数组成$i$个环的方案数，$s(n-1,i-1)$为$2\to n$组成了$i-1$个环（即$1$号房自己成环）的方案数。

答案为$\large\frac{\sum_{i=1}^kans_i}{n!}$

AC代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll stirling[30][30], fac[30];
void solve(){
    ll n, k;
    cin >> n >> k;
    double ans = 0;
    for(int i=1; i<=k; i++){
        ans = ans + (1.0 * (stirling[n][i] - stirling[n-1][i-1]) / fac[n]);
    }
    cout << fixed << setprecision(4) << ans << endl;
}

void init(){
    stirling[0][0] = fac[0] = 1;
    for(int i=1; i<=20; i++){
        fac[i] = fac[i-1] * i;
        for(int j=1; j<=i; j++){
            stirling[i][j] = (i-1) * stirling[i-1][j] + stirling[i-1][j-1];
        }
    }
}

signed main(){
    init();
    int t; cin >> t;
    while(t--) solve();
}

例题 HDU 4372

不知道为什么用逆元求组合数会WA。

BTW，垃圾HDU，OOM报的是WA。

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll mod = 1e9 + 7;
const int maxn = 2020;
ll stirling[maxn][maxn], comb[maxn][maxn];

void solve(){
    ll n, f, b;
    cin >> n >> f >> b;
    ll ans = comb[f+b-2][f-1] * stirling[n-1][f+b-2] % mod;
    cout << ans << '\n';
}

void init(){
    stirling[0][0] = comb[0][0] = 1;
    for(int i=1; i<maxn; i++){
        comb[i][0] = 1;
        for(int j=1; j<=i; j++){
            comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % mod;
            stirling[i][j] = ((i-1) * stirling[i-1][j] % mod + stirling[i-1][j-1]) % mod;
        }
    }
}

signed main(){
    init();
    int t; cin >> t;
    while(t--) solve();
}