1013 字
5 分钟
斯特林数 (Stirling Numbers)

斯特林数 (Stirling Numbers)#

第一类斯特林数(斯特林轮换数)#

将 nn 个不同元素,划分为 mm 个非空圆排列的方案数,记作 [nm]\begin{bmatrix} n \\ m \end{bmatrix} 或 s(n,m)s(n, m)。

递推式:

[nm]=[n−1m−1]+(n−1)[n−1m]\begin{bmatrix} n \\ m \end{bmatrix} = \begin{bmatrix} n - 1 \\ m - 1 \end{bmatrix} + (n - 1) \begin{bmatrix} n - 1 \\ m \end{bmatrix}

组合意义: nn 个人坐 mm 张圆桌的方案数。考虑第 nn 个人:

  1. 若单独坐一桌,前面 n−1n-1 人坐 m−1m-1 张桌子,方案数为 [n−1m−1]\begin{bmatrix} n-1 \\ m-1 \end{bmatrix};
  2. 若坐到已有人的桌子上,先让前 n−1n-1 个人坐 mm 张桌子,第 nn 个人可以坐到这 n−1n-1 个人中任意一个人的左边,方案数为 (n−1)[n−1m](n-1) \begin{bmatrix} n-1 \\ m \end{bmatrix}。

第二类斯特林数(斯特林子集数)#

将 nn 个不同元素,划分为 mm 个非空子集的方案数,记作 {nm}\begin{Bmatrix} n \\ m \end{Bmatrix} 或 S(n,m)S(n, m)。

递推式:

{nm}={n−1m−1}+m{n−1m}\begin{Bmatrix} n \\ m \end{Bmatrix} = \begin{Bmatrix} n - 1 \\ m - 1 \end{Bmatrix} + m \begin{Bmatrix} n - 1 \\ m \end{Bmatrix}

组合意义: nn 个不同的小球放入 mm 个无标号盒子的方案数。考虑第 nn 个小球:

  1. 若单独放入一个新盒子,前面 n−1n-1 个球放入 m−1m-1 个盒子,方案数为 {n−1m−1}\begin{Bmatrix} n-1 \\ m-1 \end{Bmatrix};
  2. 若放入已有球的盒子中,前面 n−1n-1 个球已放入 mm 个盒子,第 nn 个球有 mm 种选择,方案数为 m{n−1m}m \begin{Bmatrix} n-1 \\ m \end{Bmatrix}。

容斥通项公式:

{nm}=1m!∑i=0m(−1)m−i(mi)in\begin{Bmatrix} n \\ m \end{Bmatrix} = \frac{1}{m!} \sum_{i=0}^m (-1)^{m-i} \binom{m}{i} i^n

经典应用一:P4609 [FJOI2016] 建筑师#

高度为 nn 的建筑是一个分水岭,在它左边有 a−1a-1 个建筑群(每个建筑群左边一个最高建筑,剩下的建筑自由排列,数量等于圆排列的数量),在它右边有 b−1b-1 个建筑群。每个建筑群构成一个圆排列,共计 a+b−2a+b-2 个圆排列。即把 n−1n-1 个建筑划分成 a+b−2a+b-2 个圆排列,即 [n−1a+b−2]\begin{bmatrix} n-1 \\ a+b-2 \end{bmatrix}。然后从圆排列数中拿出 a−1a-1 个放在 nn 的左边,即 (a+b−2a−1)\binom{a+b-2}{a-1}。

答案:[n−1a+b−2]×(a+b−2a−1)\begin{bmatrix} n-1 \\ a+b-2 \end{bmatrix} \times \binom{a+b-2}{a-1}。

#include <bits/stdc++.h>
#define ll long long
#define N 50005
#define M 205
using namespace std;
ll t;
ll c[N][M];
ll s[N][M];
const int mod = 1e9 + 7;
void init() {
for (int i = 0; i < N; i++) {
c[i][0] = 1;
s[i][0] = (i == 0 ? 1 : 0);
}
for (int i = 1; i < N; i++) {
for (int j = 1; j < M; j++) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
}
for (int i = 1; i < N; i++) {
for (int j = 1; j < M; j++) {
s[i][j] = (s[i - 1][j - 1] + (i - 1) * s[i - 1][j]) % mod;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
cout.tie(nullptr);
init();
cin >> t;
while (t--) {
ll n, a, b;
cin >> n >> a >> b;
if (a + b - 2 >= M || a + b - 2 < 0) {
cout << 0 << '\n';
continue;
}
cout << (s[n - 1][a + b - 2] * c[a + b - 2][a - 1]) % mod << '\n';
}
return 0;
}

经典应用二:第二类斯特林数递推与高精度 (P3904)#

将 nn 个互不相同的元素划分为 mm 个非空集合的方案数,递推关系 S(i,j)=S(i−1,j−1)+j⋅S(i−1,j)S(i, j) = S(i-1, j-1) + j \cdot S(i-1, j)。

#include <bits/stdc++.h>
using namespace std;
// 高精度整数辅助类
struct BigInt {
vector<int> a;
BigInt(long long v = 0) {
if (v == 0)
a.push_back(0);
while (v > 0) {
a.push_back(v % 10);
v /= 10;
}
}
BigInt operator+(const BigInt &o) const {
BigInt c;
c.a.clear();
int carry = 0, n = max(a.size(), o.a.size());
for (int i = 0; i < n || carry; i++) {
if (i < a.size())
carry += a[i];
if (i < o.a.size())
carry += o.a[i];
c.a.push_back(carry % 10);
carry /= 10;
}
return c;
}
BigInt operator*(int m) const {
BigInt c;
c.a.clear();
long long carry = 0;
for (int i = 0; i < a.size() || carry; i++) {
if (i < a.size())
carry += 1LL * a[i] * m;
c.a.push_back(carry % 10);
carry /= 10;
}
while (c.a.size() > 1 && c.a.back() == 0)
c.a.pop_back();
return c;
}
void print() const {
for (int i = (int)a.size() - 1; i >= 0; i--)
cout << a[i];
cout << '\n';
}
};
BigInt S[105][105];
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m))
return 0;
S[0][0] = BigInt(1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
S[i][j] = S[i - 1][j - 1] + S[i - 1][j] * j;
}
}
S[n][m].print();
return 0;
}
斯特林数 (Stirling Numbers)
https://sanzenin.top/posts/obsidian/斯特林数/
作者
Sanzenin 凪
发布于
2026-09-03
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取