知识库
整数分拆的生成函数
$p(n)$ 是把正整数 $n$ 写成若干正整数之和的方法数,不考虑顺序,约定 $p(0)=1$。例如 $4=4=3+1=2+2=2+1+1=1+1+1+1$,$p(4)=5$。
大小为 $k$ 的加数可以用 $0,1,2,\dots$ 次,对应因子
LaTeX
$$1+x^k+x^{2k}+\cdots=\frac1{1-x^k}.$$
所有大小相乘,$x^n$ 的系数就是凑出 $n$ 的方法数:
LaTeX
$$\sum_{n\ge0}p(n)x^n=\prod_{k=1}^{\infty}\frac1{1-x^k}.$$
生成函数 的乘法在这里是「每种大小各自选多少个」的独立组合。这条路通向 Euler 五边形数定理、q 级数、Dedekind η 函数、模形式,以及 Hardy–Ramanujan 的分拆渐近公式。
背包问题里「完全背包求方案数」的 DP 数组,就是逐个乘上 $1/(1-x^{w})$ 的系数。
用到它的地方
- 知识库 生成函数
核对
这一条是文字讲解,由 AI 整理,没有可以数值核对的步骤;作者读过后才公开。