生成函数

设 `{a_n}` 是一个数列, 则 `sum_(n ge 0) a_n x^n`, `quad sum_(n ge 0) a_n x^n/n!`, `quad sum_(n ge 1) a_n /n^s` 分别称为这个数列的普通型生成函数, 指数型生成函数, Dirichlet 生成函数.

[来自群友 凡人比肩神明, 3b1b《奥数级别的数数问题》] 求集合 `A = [1...2000]` 中, 有多少个子集的元素之和是 10 的倍数?

[来自群友 subideal]
1. 用生成函数 `f(x) = prod_(k=1)^2000 (1+x^k)` 枚举 `A` 的子集: 对于 `A` 的任一子集 `B`, 如果 `k in B`, 就在因子 `1+x^k` 中选择 `x^k` 的部分, 否则选择 `1` 的部分. 于是 `f(x)` 的 `n` 次项系数 `"coef"(f, n)` 正好表示元素和等于 `n` 的子集个数.
2. 下面求 `sum_(k ge 0) "coef"(f, 10k)`. 回忆这个相关的问题: 求一个多项式 `f` 的偶次项系数和, 可以将 `f` 的系数和 `f(1)` 与系数交错和 `f(-1)` 相加再除以 `2`. 我们的问题正是此问题的推广. 记 `1^(1//10) = "e"^(2pi"i"//10)`, 考虑和式 `sum_(j=0)^9 1^(j k//10)`. 当 `k` 为 `10` 的倍数时, 它的值为 `10`. 否则记 `q = 1^(k//10) != 1`, 利用 `q^10 = 1` 有 `sum_(j=0)^9 q^j` `= (1 - q^10)/(1-q) = 0`. 因此 `sum_(j=0)^9 f(1^(j//10))` `= sum_(k ge 0) "coef"(f, k) sum_(j=0)^9 1^(j k//10)` `= 10 sum_(k ge 0) "coef"(f, 10k)`.
3. [来自 fran] 利用公式 `prod_(0 lt k lt n) cos{:(k pi)/n:} = 2^(1-n) * cos((n-1)pi//2)`, 计算 `prod_(k=0)^9 (1 + 1^(j k // 10))`
   `= prod_(k=0)^9 cos(2pi j k // 20) * 2 * 1^(j k // 20)`
   `= 2^10 "i" prod_(k=0)^9 cos(pi j k // 10)`. `j = 0` 时, 上式为 `2^10`; `j` 与 `10` 互素, 或者 `j = 5` 时, 上式为 0; `j = 2, 4, 6, 8` 时, `prod_(k=0)^9 cos(pi j k // 10)` `= (prod_(k=0)^4 cos(pi (j//2) k // 5))^2` `= 2^-8`. 于是原题答案为 `1/10 sum_(j=0)^9 f(1^(j//10))`
   `= 1/10 sum_(j=0)^9 prod_(k=1)^2000 (1+1^(j k//10))`
   `= 1/10 sum_(j=0)^9 (prod_(k=0)^9 (1 + 1^(j k//10)))^200`
   `= 1/10 (2^2000 + 4 * (2^2 "i")^200)`
   `= 1/10 (2^2000 + 2^402)`
   `= 1148...0288`. 一共有 602 位数.

分拆数

分拆数 (partition number) [在线计算] [A000041] `p_n(m)` 定义为非负整数 `m` 拆成 `n ge 1` 个非负整数之和的方法数. 这等于将 `m` 拆成不超过 `n` 个正整数之和的方法数. 例如, 将 `m` 个相同苹果放入 `n` 个相同篮子. 特别简记 `p_n = p_n(n)`, 并约定 `p_0 = 1`. 例如, 5 = 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 5*1, 共 7 种分拆方法, 因此 `p_5 = 7`.

* *
* *
*

找零问题 用 10 张 1 元、3 张 2 元、2 张 5 元的零钞支付 17 元, 共有几种可能的方法?

考虑生成函数 `f(x) = (1 + x + cdots + x^10)(1 + x^2 + x^4 + x^6)(1 + x^5 + x^10)`, 每个因子代表一种面额, 因子的项数代表该种面额的钞票可取的数目. 支付时, 从每种面额中取出一定的数目, 即从每个因子中取出一项相乘, 因此 `f(x)` 的 17 次项系数就是所求的答案.

分拆数的生成函数 `sum_(n ge 0) p_n x^n` `= prod_(n ge 1) 1/(1-x^n)`.

这是找零问题的推广. 我们有任意正整数面额的钞票, 每种钞票可取任意多张. 因此生成函数为 `prod_(n ge 1) (1 + x^n + x^(2n) + cdots)` `= prod_(n ge 1) 1/(1-x^n)`.

Euler 等分定理 `n` 的分拆中每份大小都不同的方法数, 等于 `n` 的分拆中每份大小都为奇数的方法数: `p_n("distinct") = p_n("odd")`.

计算两者的生成函数. 对于 `p_n("distinct")`, 每份的大小 `l_k = 0` 或 `1`, `sum_(n ge 0) p_n("distinct") x^n` `= prod_(n ge 1) (1 + x^n)`, 对于 `p_n("odd")`, 只保留 `p_n` 的生成函数乘积中的第奇数个因子: `sum_(n ge 0) p_n("odd") x^n` `= prod_(n ge 1) 1/(1-x^(2n-1))`. 为证明两式相等, 相除等到 `prod_(n ge 1) (1 + x^n)(1-x^(2n-1))` `= prod_(n ge 1) (1 + x^(2n)) (1+x^(2n-1))(1-x^(2n-1))` `= prod_(n ge 1) (1 + x^(2n)) (1 - x^(4n-2))`. 上式记为 `f(x)`, 则有 `f(x) = f(x^2)`. 由连续性知道 `f(x) -= f(0) = 1`.

Euler 五角数定理 `prod_(n ge 1) (1-x^n)` `= sum_(n=-oo)^oo (-1)^n x^(n(3n-1)//2)`. 注: 将 `n=5` 代入 `n` 角数通项公式 `(n-2)k(k-1)//2 + k` 得到 `k(3k-1)//2`.

形式幂级数

全体形式幂级数记为 `CC[[x]]`, 其中的元素形如 `sum_(n ge 0) a_n x^n`; 全体形式 Laurent 级数记为 `CC((x))`, 其中元素形如 `sum_(n ge -N) a_n x^n`. `CC[[x]]` 和 `CC((x))` 分别构成环和域. 在研究形式级数的时候, 我们只进行形式的计算, 不关心它们的收敛性.
若 `f` 是形式级数, 我们用 `[x^n] f(x)` 表示它的 `n` 次项系数. 特别当 `f` 是形式幂级数时, 有 `[x^n] f(x) = 1/n! {:("d"^n f)/dx^n|_(x=0)`.

1. 设 `f(x)` 是形式 Laurent 级数, 则 `[x^-1] f'(x) = 0`.
2. 设 `f(x)` 是形式幂级数, `f(0) = 0`, `f'(0) != 0`, 则对任意整数 `n`, `[x^-1] f(x)^n f'(x) = { 1, if n = -1; 0, otherwise :}`

1. 这是因为 `(x^n)' = n x^(n-1)`.
2. 若 `n != -1`, `f(x)^n f'(x) = 1/(n+1) (f(x)^(n+1))'`, 由 1 知道它的 `-1` 次项系数等于 `0`. 若 `n = -1`, 记 `f(x) = sum_(k ge 1) a_k x^k`, 有 `(f'(x))/(f(x))` `= (a_1 + 2 a_2 x + cdots)/(a_1 x + a_2 x^2 + cdots)` `= (a_1 + 2 a_2 x + cdots)/(a_1 x) 1/(1 + g(x))` `= (x^-1 + 2 a_2//a_1 + cdots) (1 - g(x) + g(x)^2 - cdots)`. 其中 `g(x) = (a_2 x^2 + cdots)//a_1 x`. 容易看出上式的最低次项, 即 `-1` 次项系数为 `1`.

Lagrange 反演公式 设 `f(x), g(x)` 是形式幂级数, `f(0) = 0`, `f'(0) != 0`, `g(0) = 0`, `g'(0) != 0`. 若 `f, g` 互逆, 即 `g(f(x)) = f(g(x)) = x`, 则 `[x^n] g(x) = [x^-1] 1//f(x)^n = [x^(n-1)] (x//f(x))^n`.

设 `g(x) = sum_(k ge 1) b_k x^k`, 由 `g(f(x)) = x` 知道 `sum_(k ge 1) b_k f(x)^k = x`. 两边求导, 再同除以 `f(x)^n` 得 `sum_(k ge 1) k b_k f(x)^(k-1-n) f'(x) = f(x)^-n`. 两边取 `-1` 次项系数, 由引理 `[x^-1] f(x)^(k-1-n) f'(x) = 1` 当且仅当 `k = n`, 因而 `n b_n = [x^-1] f(x)^-n`. 证毕.