斯特林数

What · 是什么

斯特林数（Stirling numbers）是组合计数的两大核心表。第二类斯特林数 S(n,k)={n\brace k}：将 n 个两两不同的元素划分为 k 个互不区分的非空子集的方案数。递推 S(n,k)=S(n−1,k−1)+k·S(n−1,k)，通项 S(n,k)=Σ_{i=0}^k (−1)^{k−i} i^n /(i!(k−i)!)。第一类斯特林数 s(n,k)=[n\atop k]：将 n 个两两不同的元素划分为 k 个互不区分的非空轮换（cyclic arrangement，环形排列，旋转视为相同、翻转视为不同）的方案数。递推 s(n,k)=s(n−1,k−1)+(n−1)·s(n−1,k)。两类都与幂/阶乘幂互转：x^n = Σ_k S(n,k)·x^{\underline{k}}（普通幂→下降幂）、x^{\overline{n}} = Σ_k s(n,k)·x^k（上升幂→普通幂）、x^n = Σ_k S(n,k)(−1)^{n−k}x^{\overline{k}}、x^{\underline{n}} = Σ_k s(n,k)(−1)^{n−k}x^k。同一行/同一列可用生成函数 O(n log n)（NTT/多项式）计算：行生成函数 ∏_{i=0}^{n−1}(x+i)=x^{\overline{n}}（第一类），列用 EGF (e^x−1)^k/k!（第二类）。

Why · 为什么

How · 实现

伪代码

# 两类斯特林数 DP (0-indexed 表)

def stirling2(n, k):   # S(n,k) 第二类, 可带模
  S = [[0]*(k+1) for _ in range(n+1)]
  S[0][0] = 1
  for i in range(1, n+1):
    for j in range(1, min(i,k)+1):
      S[i][j] = (S[i-1][j-1] + j * S[i-1][j]) % MOD
  return S[n][k]

def stirling1(n, k):   # s(n,k) 第一类(无符号), 可带模
  s = [[0]*(k+1) for _ in range(n+1)]
  s[0][0] = 1
  for i in range(1, n+1):
    for j in range(1, min(i,k)+1):
      s[i][j] = (s[i-1][j-1] + (i-1) * s[i-1][j]) % MOD
  return s[n][k]

# 同一行: 第二类用通项卷积 O(n log n); 第一类用上升幂 O(n log^2 n) 或上升幂 O(n log n)

Python 实现

from math import factorial, comb

MOD = 998244353


def stirling2_row(n, mod=MOD):
    """第二类斯特林数整行 S(n,0..n) O(n^2) DP, 返回 list."""
    row = [0] * (n + 1)
    row[0] = 1
    for i in range(1, n + 1):
        for j in range(i, 0, -1):
            row[j] = (row[j - 1] + j * row[j]) % mod
        row[0] = 0
    return row


def stirling1_row(n, mod=MOD):
    """第一类(无符号)斯特林数整行 s(n,0..n) O(n^2) DP. 检验行生成函数 x^{overline n}."""
    row = [0] * (n + 1)
    row[0] = 1
    for i in range(1, n + 1):
        for j in range(i, 0, -1):
            row[j] = (row[j - 1] + (i - 1) * row[j]) % mod
        row[0] = 0
    return row


def rising_factorial_row(n, mod=MOD):
    """上升幂 x^{overline n} 的展开系数 = 第一类无符号斯特林数整行(交叉验证)."""
    poly = [1]
    for i in range(n):
        # 乘 (x + i)
        nxt = [0] * (len(poly) + 1)
        for j, c in enumerate(poly):
            nxt[j] = (nxt[j] + c * i) % mod
            nxt[j + 1] = (nxt[j + 1] + c) % mod
        poly = nxt
    return poly


def stirling2_explicit(n, k):
    """第二类通项公式(精确小值)."""
    tot = 0
    for i in range(k + 1):
        tot += ((-1) ** (k - i)) * comb(k, i) * (i ** n)
    return tot // factorial(k)


def change_basis_pow_to_falling(n, mod=MOD):
    """x^n = sum_k S(n,k) x^{underline k} 的系数(第二类斯特林数)."""
    return stirling2_row(n, mod)


def brute_set_partition(n, k):
    """暴力: 将 n 个元素分成 k 个无标号非空子集(集合划分数) 用于验证."""
    if n == 0 and k == 0:
        return 1
    if n < k or k == 0:
        return 0
    # 递归 S(n,k) = S(n-1,k-1) + k*S(n-1,k)
    return brute_set_partition(n - 1, k - 1) + k * brute_set_partition(n - 1, k)


if __name__ == "__main__":
    # 已知小值: S(n,k) 第二类三角形行:
    # n=4: 1 7 6 1; n=5: 1 15 25 10 1
    # 第二类整行(含 S(n,0)): n=5 -> 0 1 15 25 10 1
    r2 = stirling2_row(5)
    assert r2 == [0, 1, 15, 25, 10, 1], r2
    # 第一类无符号整行(含 s(n,0)): n=4 -> 0 6 11 6 1 (= x(x+1)(x+2)(x+3))
    r1 = stirling1_row(4)
    assert r1 == [0, 6, 11, 6, 1], r1
    assert rising_factorial_row(4) == [0, 6, 11, 6, 1]
    assert stirling2_explicit(5, 2) == 15 and stirling2_explicit(5, 3) == 25
    for n in range(0, 7):
        for k in range(0, n + 1):
            assert stirling2_row(n)[k] == brute_set_partition(n, k), (n, k)
    print("stirling-number: all tests passed")

易错点

• 第一类无符号与含符号版本混淆（符号 = (-1)^{n-k}）
• 第二类系数是 k（塞进 k 个现成组），第一类是 n−1（n−1 个插入位），别写反
• 边界 S(0,0)=1, S(n,0)=0(n>0) 等记错
• 整行计算直接套列 EGF 导致复杂度错误
• 无符号第一类数值巨大，忘取模溢出

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/combinatorics/stirling/
• oiwiki-raw✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/math/combinatorics/stirling.md
• mathworld✓ http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html
• CP-Algorithms✓ https://cp-algorithms.com/combinatorics/stirling_numbers.html