EGF(指数生成函数)

What · 是什么

指数生成函数（exponential generating function，EGF）把序列 a 编码为 F̂(x)=Σ_n a_n x^n/n!。加减仍按项；乘法变为二项式卷积：F̂(x)Ĝ(x)=Σ_n x^n/n! · Σ_{i=0}^n C(n,i) a_i b_{n−i}，即新系数 c_n=Σ C(n,i)a_i b_{n−i}。这种『除以 n!』编码专为标号（labeled）结构设计：把 n 个有标号元素切成两块大小 i 和 n−i 时，分块有 C(n,i) 种选法，恰被 EGF 乘法的二项式系数吸收。常用封闭形式：⟨1,1,1,…⟩→e^x；等比 ⟨1,p,p²,…⟩→e^{px}；阶乘 ⟨n!⟩→1/(1−x)；贝尔数 B_n→e^{e^x−1}；错排 D_n→e^{−x}/(1−x)；第二类斯特林数（固定 k）→(e^x−1)^k/k!；第一类斯特林数（固定 k）→ln(1/(1−x))^k/k!。标号与无标号的对照：OGF 处理无标号（多重集），EGF 处理标号（排列、划分、标号树）。e^x 的组合意义是『按大小分块』的核心，exp 对应 SET 构造（无序标号集合）。

Why · 为什么

How · 实现

伪代码

# EGF 运算 (存储系数为 a_n/n! 的普通列表? 更常用存原始 a_n 并配 n!)
# 约定: 存原始序列 a, 运算时除以阶乘

def egf_mul_coeff(a, b):   # 返回原始系数 c_n = sum C(n,i) a_i b_{n-i}
  c = [0]*(len(a)+len(b)-1)
  for i in range(len(a)):
    for j in range(len(b)):
      c[i+j] += comb(i+j, i) * a[i] * b[j]
  return c

def exp_series(n, p=1):    # e^{px} 前 n 项, 原始系数 p^k
  return [p**k for k in range(n)]

def bell_egf(n):           # B_n 由 e^{e^x-1} 得 (需多项式 exp)
  ...

def derangement_egf(n):    # e^{-x}/(1-x) 的原始系数 = 错排 D_n
  a = exp_series(n, -1)    # e^{-x}: 系数 (-1)^k
  b = [1]*n                # 1/(1-x): 系数 1
  return egf_mul_coeff(a, b)

Python 实现

from math import comb, factorial


def egf_mul_coeff(a, b):
    """EGF 乘法(二项式卷积) 返回原始序列 c_n = sum_i C(n,i) a_i b_{n-i}."""
    c = [0] * (len(a) + len(b) - 1)
    for i, ai in enumerate(a):
        for j, bj in enumerate(b):
            c[i + j] += comb(i + j, i) * ai * bj
    return c


def egf_mul_from_hat(a_hat, b_hat):
    """若输入已是 a_n/n! 形式, 乘法直接卷积, 返回也是 b_n/n! 形式."""
    c_hat = [0] * (len(a_hat) + len(b_hat) - 1)
    for i, x in enumerate(a_hat):
        for j, y in enumerate(b_hat):
            c_hat[i + j] += x * y
    return c_hat


def derangement_egf(n):
    """错排 EGF e^{-x}/(1-x) = sum D_n x^n/n!. 返回 D_0..D_{n-1}."""
    a = [(-1) ** k for k in range(n)]     # e^{-x}
    b = [factorial(k) for k in range(n)]   # 1/(1-x) 是 n! 的 EGF
    c = egf_mul_coeff(a, b)
    return c


def bell_egf_naive(n, mod=998244353):
    """由 e^{e^x-1} 求贝尔数前 n 项(朴素 O(n^2) 多项式 exp)."""
    inv = [0] * (n + 1)
    for k in range(1, n + 1):
        inv[k] = pow(k, mod - 2, mod)
    a = [0] * (n + 1)
    for k in range(1, n + 1):
        a[k] = pow(inv[k], 1, mod)  # a_k = 1/k! = 对应 e^x-1 的 EGF 系数(除常数)
    # 构建 e^x-1 的 EGF 系数 (1, 1/1!, 1/2!, ...)
    a = [0] * (n + 1)
    f = [1] * (n + 1)
    for k in range(1, n + 1):
        f[k] = f[k - 1] * k % mod
    invf = [1] * (n + 1)
    invf[n] = pow(f[n], mod - 2, mod)
    for k in range(n, 0, -1):
        invf[k - 1] = invf[k] * k % mod
    for k in range(1, n + 1):
        a[k] = invf[k]
    # exp(a), a 常数项=0, 返回 b_hat (B_k/k!)
    b_hat = [0] * (n + 1)
    b_hat[0] = 1
    for k in range(1, n + 1):
        s = 0
        for j in range(k):
            s = (s + (k - j) * a[k - j] * b_hat[j]) % mod
        b_hat[k] = s * inv[k] % mod
    return [b_hat[k] * f[k] % mod for k in range(n + 1)]


if __name__ == "__main__":
    # EGF 乘法: 1/(1-x) (系数全1) * 自己 => c_n = sum C(n,i) = 2^n
    c = egf_mul_coeff([1, 1, 1, 1], [1, 1, 1, 1])
    assert c[:4] == [1, 2, 4, 8]
    # e^{-x}/(1-x): D_n
    d = derangement_egf(7)
    assert d[:6] == [1, 0, 1, 2, 9, 44]
    # 贝尔数 EGF
    b = bell_egf_naive(6)
    assert b[:7] == [1, 1, 2, 5, 15, 52, 203]
    # 二项式卷积直接与 C 匹配
    assert egf_mul_coeff([1, 1], [1, 1]) == [1, 2, 2]   # C(2,1)=2
    print("egf: all tests passed")

易错点

• 把 EGF 乘法当普通卷积（漏 C(n,i) 因子）
• 还原系数时忘乘 n!
• 标号结构误用 OGF（应 EGF）
• 多项式 exp 常数项必须为 0
• e^{e^x−1} 与 e^x 区分不清

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/poly/egf/
• oiwiki-raw✓ https://raw.githubusercontent.com/OI-wiki/OI-wiki/master/docs/math/poly/egf.md
• oiwiki-intro✓ https://oi-wiki.org/math/poly/intro/
• Wikipedia✓ https://en.wikipedia.org/wiki/Generating_function#Exponential_generating_function