OGF(普通生成函数)

What · 是什么

普通生成函数（ordinary generating function，OGF）把序列 a 编码为形式幂级数 F(x)=Σ_n a_n x^n。a 可为有限或无限序列，x^n 的系数就是 a_n（系数即通项）。基本运算：加减=对应项系数相加减；乘法（卷积）= F(x)G(x)=Σ_n x^n Σ_{i=0}^n a_i b_{n−i}，即新序列 c_n=Σ a_i b_{n−i}。常用封闭形式：⟨1,1,1,…⟩→1/(1−x)；等比数列 ⟨1,p,p²,…⟩→1/(1−px)；⟨1,2,3,…⟩→1/(1−x)²；⟨0,1,1,…⟩→x/(1−x)；⟨1,0,1,0,…⟩→1/(1−x²)；⟨C(m,n)⟩→(1+x)^m；⟨C(m+n,n)⟩→1/(1−x)^{m+1}；⟨n²⟩→x(1+x)/(1−x)³。OGF 适用于『无标号/多重集』类组合（整数分拆 ∏1/(1−x^k)、组合数、路径数等），与 EGF（标号结构）互补。配套操作：位移（乘 x 幂）、求导/积分、复合、逆等。

Why · 为什么

How · 实现

伪代码

# 多项式/形式幂级数 OGF 运算 (系数列表, 低次在前)

def add(a, b): return [(a[i] if i<len(a) else 0)+(b[i] if i<len(b) else 0) for i in range(max(len(a),len(b)))]

def mul(a, b):
  c = [0]*(len(a)+len(b)-1)
  for i,x in enumerate(a):
    for j,y in enumerate(b): c[i+j] += x*y
  return c

def diff(a):   # 求导
  return [i*a[i] for i in range(1, len(a))]

def integ(a):  # 积分 (x^k -> x^{k+1}/(k+1))
  return [0] + [a[k-1]//k for k in range(1, len(a)+1)]

def shift(a, d): return [0]*d + a    # 乘 x^d

def geometric(seq_len, p): return [p**i for i in range(seq_len)]  # 1/(1-px)

Python 实现

from math import comb


def ogf_add(a, b):
    n = max(len(a), len(b))
    return [((a[i] if i < len(a) else 0) + (b[i] if i < len(b) else 0)) for i in range(n)]


def ogf_mul(a, b):
    c = [0] * (len(a) + len(b) - 1)
    for i, x in enumerate(a):
        for j, y in enumerate(b):
            c[i + j] += x * y
    return c


def ogf_scale(a, k):
    return [x * k for x in a]


def geometric_series(n, p=1):
    """1/(1-px) 的前 n 项: [1, p, p^2, ...]."""
    res = [1]
    cur = 1
    for _ in range(n - 1):
        cur *= p
        res.append(cur)
    return res


def closed_1_minus_x2(n):
    """1/(1-x^2) 的前 n 项: [1,0,1,0,1,...]."""
    return [1 if i % 2 == 0 else 0 for i in range(n)]


def ogf_binom_fixed_m(n, m):
    """(1+x)^m 的前 n 项: [C(m,0), C(m,1), ...]."""
    return [comb(m, k) for k in range(min(n, m + 1))]


def ogf_inv_1_minus_x_km1(n, m):
    """1/(1-x)^{m+1} 的前 n 项: [C(m,0), C(m+1,1), ..., C(m+i,i)]."""
    return [comb(m + i, i) for i in range(n)]


def closed_form_multiplication(n):
    """验证 (1-x)^-2 = sum (k+1)x^k: 用乘法自检 1/(1-x)^2 系数."""
    a = geometric_series(n)
    b = ogf_mul(a, a)
    return b


if __name__ == "__main__":
    # 封闭形式(取前若干项) 验证
    assert geometric_series(6) == [1, 1, 1, 1, 1, 1]
    assert geometric_series(5, 2) == [1, 2, 4, 8, 16]
    assert closed_1_minus_x2(6) == [1, 0, 1, 0, 1, 0]
    # 1/(1-x)^2 = 1,2,3,4,...
    sq = closed_form_multiplication(6)
    assert sq[:6] == [1, 2, 3, 4, 5, 6]
    # 等比 * 等比 = 卷积
    assert ogf_mul(geometric_series(4), [1, 3]) == [1, 4, 4, 4, 3]
    # (1+x)^m 展开
    assert ogf_binom_fixed_m(6, 3) == [1, 3, 3, 1]
    # 1/(1-x)^4 系数 = C(3+i, i)
    assert ogf_inv_1_minus_x_km1(5, 3) == [comb(3, 0), comb(4, 1), comb(5, 2), comb(6, 3), comb(7, 4)]
    # OI Wiki 小练习: a=<0,1,1,1,...> => x/(1-x)
    x_over_1mx = ogf_mul([0, 1], geometric_series(6))
    assert x_over_1mx[:6] == [0, 1, 1, 1, 1, 1]
    print("ogf: all tests passed")

易错点

• 把 OGF 当普通函数求值（形式幂级数不能随便代 x=0.5）
• 卷积实现忘记初始化长度
• 封闭形式 1/(1−px) 的 p 写成 1
• 系数下标偏移（a_0 对应 x^0）
• 无标号用 EGF 或用 OGF 处理标号结构（应各自对应）

例题

信源

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