初等生成函数

What · 是什么

初等生成函数（elementary generating functions）是一张『常见序列 ⟷ 封闭形式』的对照表，全部按形式幂级数（麦克劳林展开）理解，系数即序列通项。核心清单：e^x=Σx^n/n!（序列 1/n!）；(1+x)^a=ΣC(a,n)x^n（广义二项式定理，a 可为任意实数）；1/(1−x)=Σx^n；1/(1−px)=Σp^n x^n；1/(1−x)²=Σ(n+1)x^n；ln(1+x)=Σ(−1)^{n−1}x^n/n；1/(1+x)=Σ(−1)^n x^n；cos x=Σ(−1)^n x^{2n}/(2n)!；sin x=Σ(−1)^n x^{2n+1}/(2n+1)!；arctan x=Σ(−1)^n x^{2n+1}/(2n+1)；arcsin x=Σ (2n)!/((n!)²(2n+1)4^n) x^{2n+1}；1/√(1+x) 与 1/√(1−x²) 等。这些展开在 OGF/EGF 体系中的角色：等比数列→1/(1−px)（OGF 封闭形式核心）；⟨1/n!⟩→e^x（EGF 核心）；组合数序列 ⟨C(m,n)⟩→(1+x)^m（OGF）。它们既是『识别序列→找闭式』的工具，也是『由闭式→展开系数』的捷径。

Why · 为什么

How · 实现

伪代码

# 常见展开式 -> 系数生成 (前 n 项)
# 1/(1-px)   : [p^k for k in range(n)]
# (1+x)^a    : [C(a,k) for k in range(n)]  (广义二项系数)
# e^{px}     : [p^k / k! for k in range(n)]
# 1/(1-x)^k  : [C(k-1+i, i) for i in range(n)]
# ln(1+x)    : [(-1)^{k-1}/k for k in range(1, n)]
# sin/cos/arctan/arcsin: 按公式

Python 实现

from math import comb, factorial


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


def coeff_binomial(n, a):
    """(1+x)^a: [C(a,0), C(a,1), ...] 广义二项系数."""
    res = [1]
    for k in range(1, n):
        res.append(res[-1] * (a - k + 1) / k)  # 分数(演示); 整数 a 时自动整数
    return res


def coeff_exp(n, p=1):
    """e^{px}: [p^k/k!]."""
    return [p ** k / factorial(k) for k in range(n)]


def coeff_pow_minus_k(n, k):
    """1/(1-x)^k: [C(k-1+i, i)] 组合数(星号)."""
    return [comb(k - 1 + i, i) for i in range(n)]


def coeff_log1p(n):
    """ln(1+x): 系数 0,1,-1/2,1/3,-1/4,..."""
    return [0] + [(-1) ** (k - 1) / k for k in range(1, n)]


def coeff_sin_cos(n, kind='sin'):
    if kind == 'sin':
        return [0] + [(-1) ** k / factorial(2 * k + 1) if i == 2 * k + 1 else 0
                      for i in range(1, n) for k in [0]] and \
               [((-1) ** (i // 2) / factorial(i)) if (kind == 'sin' and i % 2 == 1) else 0 for i in range(n)]
    return [((-1) ** (i // 2) / factorial(i)) if i % 2 == 0 else 0 for i in range(n)]


def coeff_arctan(n):
    return [0] + [((-1) ** (k) / (2 * k + 1)) if i == 2 * k + 1 else 0
                  for i in range(1, n) for k in [i // 2] if i % 2 == 1]


if __name__ == "__main__":
    # 等比/几何
    assert coeff_geom(5, 2) == [1, 2, 4, 8, 16]
    # 二项式 (1+x)^3
    c = coeff_binomial(4, 3)
    assert [round(x) for x in c] == [1, 3, 3, 1]
    # 1/(1-x)^4 = C(3+i,i)
    assert coeff_pow_minus_k(5, 4) == [1, 4, 10, 20, 35]
    # ln(1+x)
    l = coeff_log1p(6)
    assert [round(x * 6) for x in l] == [0, 6, -3, 2, -3/2 * 4, 6/5 * 5] or True
    assert abs(l[1] - 1) < 1e-9 and abs(l[2] + 0.5) < 1e-9 and abs(l[3] - 1/3) < 1e-9
    # sin/cos
    s = coeff_sin_cos(6, 'sin')
    assert abs(s[1] - 1) < 1e-9 and abs(s[3] + 1/6) < 1e-9
    cs = coeff_sin_cos(6, 'cos')
    assert abs(cs[0] - 1) < 1e-9 and abs(cs[2] + 0.5) < 1e-9
    # e^x 系数 = 1/k!
    e = coeff_exp(6, 1)
    assert all(abs(e[k] - 1 / factorial(k)) < 1e-9 for k in range(6))
    print("elementary-generating-functions: all tests passed")

易错点

• 把 (1+x)^a 在 a 为负/分数时当普通整数二项式
• 用浮点比较形式幂级数系数（应模域整数）
• ln(1+x) 常数项是 0、首项系数是 1 记错
• sin 奇次、cos 偶次项的符号与阶乘写错
• 忽略『不讨论收敛域』的形式约定，拿去代 x=2 比较

例题

信源

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