斯特林数学习笔记

Cryn_Frog195 · 2025-07-29 21:12:50 · 算法·理论

前言

斯特林数是计数问题中的重要的特殊数，并且可以用来转化多项式，十分好用，这里整理一下相关的重要知识点。

定义

第一类斯特林数 n\brack k 指的是使 n 个不同元素排成 k 个按顺序的不同环的方法数。

第二类斯特林数 n\brace k 指的是将 n 个不同元素放入 k 个相同容器的方法数。

斯特林数的递推式

第一类斯特林数：首先 {n\brack 0} = [n = 0]，对于 {n\brack k}，考虑：

由于图有若干个换组成，再对环按指定方向定向，使每个点恰有一个入读和一个出度，我们可以将每个元素的唯一出边指向的点记下来使环映射到一个排列 p_i 上。
若 p_n = n 意味着第 n 个元素自成一环，那么剩下 n - 1 个元素有 {n - 1}\brack {k - 1} 种可能。
否则若 p_n = a,p_b = n，考虑在删除 n 后改 p_b = a 得到 n - 1 个元素，k 个环的状态，有 {n - 1}\brack k 种可能，而 p_n 有 n - 1 种情况，每种情况对称。

得出 {n\brack k} = (n - 1){{n - 1}\brack k} + {{n - 1}\brack{k - 1}}。

对于第二类斯特林数，{n\brace 0} = [n = 0]，第 n 个元素要么放一个新盒子要么放老盒子，知 {n\brace k} = k {{n - 1}\brace k} + {{n - 1}\brace{k - 1}}。

第一类斯特林数和

公式：\sum_{k = 0}^n {n\brack k} = n!。

证明：类似于转移公式上的方法，将每种 n 个元素组环的方法映射到排列上，由于有 n! 个排列故而 \sum_{k = 0}^n {n \brack k} = n!。

第二类斯特林数通项公式

公式：{n\brace k} = \frac{\sum_{t = 0}^k(-1)^t{k\choose t}(k - t)^n}{k!}

证：

由于 k^n = \sum_{t = 0}^k {k\choose t}t!{n\brace t}，由二项式反演得到 k!{n\brace k} = \sum_{t = 0}^k(-1)^t(^k_t)(k - t)^n，故 {n\brace k} = \frac{\sum_{t = 0}^k(-1)^t{k\choose t}(k - t)^n}{k!}。

斯特林数与数的幂

公式一：x^n = \sum_{k = 1}^n {n\brace k}x^{\underline k}。

证：将 n 个元素任意放到 x 个不同桶中有 x^n 种情况。我们还可以将 n 个元素先分 k 组在放到 k 个不同的桶中得出同样的效果，有 \sum_{k = 1}^n {n\brace k}x^{\underline k} 种，由此得证。

公式二：x^{\bar k} = \sum_{k = 0} ^ n{n\brack k}x^k。

证：我们设 \operatorname{F}_n(x) = \sum_{k = 0}^n{{n\brack k}x^k}，由 {n\brack k} = (n - 1){n - 1\brack k} + {n - 1\brack k - 1} 得：\operatorname{F}_n(x) = (n - 1 + x)\operatorname{F }_{n - 1}(x) = \prod_{i = 1}^{n}(i + x - 1) \operatorname{F}_0(x) = \prod_{i = 1}^{n}(i + x - 1) = x^{\bar k}。

公式三：x^{\underline n} = \sum_{k = 1}^n (-1)^{n - k} {n\brack k}x^{k}。

证：我们设 \operatorname{G}_n(x) = \sum_{k = 0}^n(-1)^{n - k}{{n\brack k}x^k}，由 {n\brack k} = (n - 1){n - 1\brack k} + {n - 1\brack k - 1} 得：\operatorname{G}_n(x) = (x + 1 - n)\operatorname{G }_{n - 1}(x) = \prod_{i = 1}^{n}(i + x - 1) \operatorname{G}_0(x) = \prod_{i = 1}^{n}(i + x - 1) = x^{\underline k}。

公式四：x^{n} = \sum_{k = 1}^n (-1)^{n - k} {n\brace k}x^{\bar k}。

证：(-1) ^ kx^{\bar k} = (-x) ^ {\underline k}。则：

\begin{aligned} (-x)^n &= \sum_{k = 1}^n {n\brace k}(-x)^{\underline k} \\ &= \sum_{k = 1}^n {n\brace k}(-1)^kx^{\bar k}\\ (-1) ^ n x^n &= \sum_{k = 1}^n {n\brace k}(-1)^kx^{\bar k} \\ x^n &= \sum_{k = 1}^n {n\brace k}(-1)^{k - n}x^{\bar k} \\ &= \sum_{k = 1}^n {n\brace k}(-1)^{n - k}x^{\bar k} \\ \end{aligned}

简记：

斯特林反演

我们由 x^n = \sum_{k = 1}^n(-1)^{n - k}{n\brace k}x^{\bar k} = \sum_{1\le m \le k \le n}(-1)^{n - k}{n\brace k}{k\brack m}x^m 知 \sum_{m \le k \le n}(-1)^{n - k}{n\brace k}{k\brack m} = [n = m]，再由 x^{\underline n} = \sum_{k = 1}^n(-1)^{n - k}{n\brack k}x^{k} = \sum_{1\le m\le k \le n}(-1)^{n - k}{n\brack k}{k\brace m}x^{\underline k} 知 \sum_{m\le k \le n}(-1)^{n - k}{n\brack k}{k\brace m} = [n - m]。

根据这两个式子推出：

\begin{aligned} f_n = \sum_{i = 1}^n [^n_i]g_i &\implies g_n = \sum_{i = 1}^n(-1)^{n - i}\{^n_i\}f_i \\ f_n = \sum_{i = 1}^n \{^n_i\}g_i &\implies g_n = \sum_{i = 1}^n(-1)^{n - i}[^n_i]f_i \\ \end{aligned}

得到斯特林反演公式。

例题集

1. 洛谷 P4609

求长为 n (n \le 50000) 排列的总数，使得对于维护单调递减的单调栈，从右往左插入时栈大小为 A(A \le 100)，从左往右是栈大小为 B(B \le 100)。

解：这意味着最大值左边 A - 1 组，右边 B - 1 组。每组任意排列要保证最大值在一边。这时每组可以是做环，转为序列时从最大元素开始向逆时针转遍历，得到 {{n - 1}\brack{A + B - 2}}{{A + B - 2}\choose{A - 1}}。

#include<bits/stdc++.h>
//考虑50000 * 200 的第一类string数，得到f(n,A,B) = (^{A + B - 2}_{A - 1}) * [^{n - 1}_{A + B - 2}]; 
using namespace std;
int T,n,A,B,c[209][209],s[500009][209];
const int mod = 1000000007;
int main(){
    scanf("%d",&T);
    c[0][0] = s[0][0] = 1;
    for(int i = 1; i <= 200; i ++)
    {
        c[i][0] = 1;
        for(int j = 1; j <= i; j ++){
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
    }
    for(int i = 1; i <= 50000; i ++){
        s[i][0] = 0;
        for(int j = 1; j <= i && j <= 200; j ++){
            s[i][j] = (1ll * s[i - 1][j] * (i - 1) % mod + s[i - 1][j - 1]) % mod;
        }
    }
    while(T--){
        scanf("%d %d %d",&n,&A,&B);
        printf("%d\n",1ll * c[A + B - 2][A - 1] * s[n - 1][A + B - 2] % mod);
    }
    return 0;
}

2. 洛谷 P8143

给定 n (n \le 10 ^ 6)，求 \sum_{k \mid 2} {n\brack k}。

解：

对于 n = 1 答案显然为 0。

否则：

在 n > 1 时 (-1)^{\bar k} = 0，此时答案为 \frac{n!}{2}。

3. CF932E

给定 n,k(n \le 10 ^ 9,k \le 5000)，求 \sum_{i = 1}^n{n\choose i}i^k。

解：

\begin{aligned} \sum_{i = 1}^n{n\choose i}i^k &= \sum_{i = 1}^n\sum_{j = 1}^k{n\choose i}{k\brack j}i^{\underline j}\\ &= \sum_{i = 1}^n\sum_{j = 1}^k{k\brack j}\frac{n!}{i!(n - i)!}\frac{i!}{(i - j)!}\\ &= \sum_{i = 1}^n\sum_{j = 1}^k{k\brack j}\frac{n!}{(n - i)!(i - j)!}\\ &= \sum_{j = 1}^k\sum_{i = j}^n{k\brack j}\frac{n!}{(n - i)!(i - j)!}\\ &= \sum_{j = 1}^n\sum_{i = j}^n{k\brack j}n^{\underline j}\frac{(n - j)!}{(n - i)!(i - j)!}\\ &= \sum_{j = 1}^n{k\brack j}n^{\underline j}\sum_{i = j}^n\frac{(n - j)!}{(n - i)!(i - j)!}\\ &= \sum_{j = 1}^n{k\brack j}n^{\underline j}\sum_{i = j}^n{{n - j}\choose {i - j}}\\ &= \sum_{j = 1}^n{k\brack j}n^{\underline j}2^{n - j}\\ \end{aligned}

得到 \operatorname{O}(k^2) 的算法。