第1卷 第10章 分拆数

学习目标

• 能解释无序分拆与硬币支付的对应关系，并用递推或代码不重不漏地计算小规模值
• 能推导分拆数的生成函数，说明形式幂级数中的固定系数为什么只需有限个因子
• 能构造按最小部件分组的单射，证明斐波那契上界并判断它何时已经足够
• 能推导参数函数的最小值，回答“精确计数、粗上界和指数平方根上界分别解决什么问题？”

先问：数值一定要精确算出来吗

想象一排硬币，金额相同但摆放顺序不同。你要统计的是“用了哪些面值”，还是“硬币依次怎么摆”？如果不先固定对象，计数会把同一个方法重复很多次。

本章还追问另一件事：如果目标只是证明某个数小于 1000，是否必须知道它的精确值？不必。先找到一个可靠的安全边界，往往比逐项枚举更快；边界越紧，代价通常也越高。

先预测：3+1 和 1+3 是两种吗？为什么 P_0 不能写成 0？每一种面值为什么会对应一个等比级数？固定 x^n 的系数时，无限乘积真的需要处理无限条信息吗？

分拆数与硬币支付

本节的分拆数与硬币支付是同一个对象的两种说法：把正整数 $n$ 写成若干正整数之和并忽略加数顺序，等价于用面值 $1,2,3,\ldots$ 的硬币支付 $n$ 元，每种面值可以使用任意多枚。

分拆数 记为 $P_n$。例如 5 的七种分拆是：

$$5,\quad4+1,\quad3+2,\quad3+1+1,\quad2+2+1,\quad2+1+1+1,\quad1+1+1+1+1.$$

这个式子在说：七种写法对应七种无序硬币选择，因此 $P_5=7$；把同一行的加数调换位置不会创造新对象。

硬币模型的好处是能把“选择面值”变成“选择每种硬币的枚数”。枚数一旦固定，总金额就固定；反过来，一个无序分拆也唯一决定每种面值用了几枚。

P0等于1与小规模枚举

P0等于1与小规模枚举是后续递推的边界起点。支付 0 元只有一种合法方式：什么硬币都不取，也就是空分拆，所以 $P_0=1$，而不是 0。

列举得到 $P_1=1,P_2=2,P_3=3,P_4=5,P_5=7$；到 $P_9$ 时，手工漏项的风险明显增加，正确值为 $P_9=30$。为了让“不重不漏”成为状态的一部分，令 $q(n,k)$ 表示只使用不超过 $k$ 的部件分拆 $n$ 的数量。

每个分拆要么不用 $k$，要么至少使用一个 $k$。第二类删掉一个 $k$ 后仍是只使用不超过 $k$ 的分拆，因此

$$q(n,k)=q(n,k-1)+q(n-k,k).$$

这个式子在说：按是否使用最大部件拆成两类，左右两类没有重叠且能恢复原对象。边界是 $q(0,k)=1$、正数满足 $q(n,0)=0$，最终 $P_n=q(n,n)$。

n − 1n + 1重置当前 n = 5

整数分拆的乘法重数表示

整数分拆的乘法重数表示把每一种面值的出现次数单独记录。设 $m_k$ 是部件 $k$ 的出现次数，则

$$n=1m_1+2m_2+3m_3+\cdots,\qquad m_k\in\{0,1,2,\ldots\}.$$

这个式子在说：一个无序分拆等价于一条非负整数重数向量。例如 $5=2+2+1$ 对应 $m_1=1,m_2=2$，其余重数为 0；顺序信息已经被有意删除。

重数向量把计数拆成彼此独立的选择：先选 1 元硬币的枚数，再选 2 元硬币的枚数，最后用指数总和检查金额。正是这个结构让乘法原理和生成函数能够接手枚举。

有限硬币模型与系数计数

有限硬币模型与系数计数先用 1、2、3 三种面值，并且每种只允许一枚。是否取 1 元由 $1+x$ 记录，是否取 2 元由 $1+x^2$ 记录，三元同理：

$$(1+x)(1+x^2)(1+x^3)=1+x+x^2+2x^3+x^4+x^5+x^6.$$

这个式子在说：展开时从每个因子各选一项，指数相加就是总金额；$x^3$ 的系数 2 来自 3 与 2+1 两条选择路径。

有限模型提醒我们，乘法展开不是形式游戏。每一项都代表一条选择路径，合并同次项则把金额相同的路径计数到同一个系数里。

无限项和的无限项积

无限项和的无限项积允许每种面值使用任意多枚。面值 $k$ 的选择因子是

$$1+x^k+x^{2k}+x^{3k}+\cdots=\frac1{1-x^k}.$$

这个式子在说：指数 $km_k$ 记录使用 $m_k$ 枚面值 $k$ 的硬币，常数项对应一枚也不选。所有面值相乘，就同时组合了每个 $m_k$ 的选择。

把前面的因子全部乘起来：

$$P(x)=\prod_{k=1}^{\infty}(1+x^k+x^{2k}+\cdots).$$

这个式子在说：乘积的每个完整选择对应一条重数向量；相乘后的总指数就是分拆的总和。它还没有依赖 $x$ 的具体数值，可以先当作形式对象读。

分拆数的生成函数

分拆数的生成函数把整列计数装进一个系数序列：

$$P(x)=\sum_{n=0}^{\infty}P_nx^n=\prod_{k=1}^{\infty}\frac1{1-x^k}.$$

这个式子在说：$x^n$ 的系数恰好统计金额为 $n$ 的全部重数向量，也就是 $P_n$。这里的 生成函数不是神奇的通项公式，而是一台把“组合对象”翻译成“系数问题”的编码器。

从 $P(x)$ 取一个固定系数时，使用的是 形式幂级数的视角。若目标是 $[x^n]P(x)$，所有 $k>n$ 的因子只能选择常数项 1，因而固定系数只依赖前 $n$ 个因子；无限的外观不会带来无限次实际计算。

若把 $x$ 当成实数再讨论 $P(x)$ 的函数值，就必须另外声明收敛范围。形式幂级数保证的是系数运算，不自动保证每个数值代入都收敛；区分两种语境是读生成函数的第一道安全检查。

斐波那契上界

斐波那契上界给出一条便宜的安全路线：只要证明 $P_n\le F_{n+1}$，就能立刻得到 $P_{15}\le F_{16}=987\lt1000$，不必先求出 $P_{15}=176$。

上界

回答的是“它不会超过多少”，不是“它实际等于多少”。观察边界 $P_0=1\le F_1$、$P_1=1\le F_2$ 后，核心只剩下证明

$$P_{k+2}\le P_{k+1}+P_k.$$

这个式子在说：所有 $k+2$ 的分拆都能被无重复地送进一个大小为 $P_{k+1}+P_k$ 的目标集合。它不是根据前几项猜出的数值关系，而是一个需要构造的集合映射。

按最小部件分组的单射

按最小部件分组的单射把 $k+2$ 的分拆分成三类。第一类的最小部件为 1：删去一个 1，得到 $k+1$ 的分拆；第二类的最小部件为 2：删去一个 2，得到不含 1 的 $k$ 的分拆。

第三类的最小部件为 $m\ge3$。把一个 $m$ 临时换成一个 2 与 $m-2$ 个 1，再删除那个 2，得到 $k$ 的分拆。输出中的 1 全来自替换，因此数出 1 的个数 $r$ 就能恢复 $m=r+2$；第二类没有 1，两个去处不会相撞。

这个 单射是可逆信息的压缩：每个左侧分拆都有唯一右侧记录，但右侧不一定每个对象都被填满，所以结论是“不超过”而不是“相等”。

数学归纳法完成全称证明

数学归纳法完成全称证明的顺序是：先验证 $n=0,1$，再假设前两级不等式成立，使用单射得到下一层，最后把斐波那契递推代入。若 $P_k\le F_{k+1}$ 且 $P_{k+1}\le F_{k+2}$，则

$$P_{k+2}\le P_{k+1}+P_k\le F_{k+2}+F_{k+1}=F_{k+3}.$$

这个式子在说：两条已知上界沿着同一递推结构向前传递；基础情形和推进步骤合起来，才得到对所有非负整数成立的结论。

精确计数与上界证明的区别

精确计数与上界证明的区别决定了算法选择。完整列举回答“$P_{15}$ 到底是多少”，斐波那契上界回答“证明 $P_{15}<1000$ 是否需要知道全部分拆”；后者只要 987 已落在阈值下方就完成任务。

精确值通常更有信息，但需要管理更多对象；粗上界更快，却可能远离真实值。比较它们时要写清目标、允许的误差和所需证明强度，不要把“更紧”误当成“唯一正确”。

生成函数的系数上界

生成函数的系数上界利用正系数。对 $0\lt x\lt1$，因为每一项都非负，单独的 $P_nx^n$ 不超过整个生成函数；截断到前 $n$ 个面值也仍给出合法上界：

$$P_nx^n\le P(x),\qquad P_n\le x^{-n}\prod_{k=1}^{n}\frac1{1-x^k}.$$

这个式子在说：任意一个允许的 $x$ 都能制造一个 $P_n$ 的上界，接下来可以自由选择参数，让右侧尽量小。参数不是答案，而是证明工具。

取对数把积变为和

取对数把积变为和是估计的转折点。由于所有因子为正且对数单调递增，得到

$$\log P_n\le-n\log x-\sum_{k=1}^{n}\log(1-x^k).$$

这个式子在说：原本难处理的乘积被拆成两个同一参数 $x$ 控制的部分。第一部分是 $x$ 太小时变大的代价，第二部分是 $x$ 太接近 1 时变大的代价，最优点正是两种代价平衡的位置。

负对数的泰勒展开

负对数的泰勒展开对 $0\le u\lt1$ 为

$$-\log(1-u)=\sum_{m=1}^{\infty}\frac{u^m}{m}.$$

这个式子在说：一个难估计的对数可以拆成非负项之和；非负性允许我们放宽求和范围而不改变不等式方向。令 $u=x^k$，交换非负双重和：

$$-\sum_{k=1}^{n}\log(1-x^k) =\sum_{m=1}^{\infty}\frac1m\sum_{k=1}^{n}x^{km} \lt\sum_{m=1}^{\infty}\frac1m\frac{x^m}{1-x^m}.$$

这个式子在说：有限几何和被无限几何和替代，右侧变大却更容易统一估计。

巴塞尔和控制东边森林

巴塞尔和控制东边森林时，先用

$$1-x^m=(1-x)(1+x+\cdots+x^{m-1})\ge(1-x)mx^{m-1}$$

得到 $x^m/(1-x^m)\le x/(m(1-x))$。于是

$$-\sum_{k=1}^{n}\log(1-x^k) \lt\frac{x}{1-x}\sum_{m=1}^{\infty}\frac1{m^2} =\frac{\pi^2}{6}\frac{x}{1-x}.$$

这个式子在说：上一章的巴塞尔和 $\sum 1/m^2=\pi^2/6$ 正好控制展开后所有森林般的非负项；复杂乘积被压成一个线性参数。

令 $t=x/(1-x)>0$，则东侧变成 $\pi^2t/6$。同一换元还把西侧写成 $n\log(1+1/t)$，并由 $\log(1+u)\lt u$ 得到 $n/t$。

辅助参数最优化与指数平方根上界

辅助参数最优化与指数平方根上界把两路合并为

$$\log P_n\lt g(t),\qquad g(t)=\frac nt+\frac{\pi^2}{6}t.$$

这个式子在说：对每个 $t>0$ 都有安全界，现在只需找到右侧最小的参数。求导得到

$$g'(t)=-\frac n{t^2}+\frac{\pi^2}{6},\qquad t_* = \frac{\sqrt{6n}}{\pi}.$$

这个式子在说：最优点让递减项和递增项的边际变化相互抵消；函数在它之前下降、之后上升，因此是全局最小值。代回并取指数：

$$g(t_*)=\pi\sqrt{\frac{2n}{3}},\qquad P_n\lt\exp\left(\pi\sqrt{\frac{2n}{3}}\right).$$

这个式子在说：上界的指数只按 $\sqrt n$ 增长，比斐波那契式的指数线性增长更适合描述大规模趋势；它仍然不是每个 $P_n$ 的精确公式。

分步实验：从对象走到上界

⚡分步1 / 4

1. 1
2. 2
3. 3
4. 4

重置

1. 计数：切换 n，检查对象边界

调整 n，观察分拆列表如何增长；说明为什么交换加数顺序不新增行，以及为什么空分拆让 P₀=1。

n − 1n + 1重置当前 n = 5

上一步播放下一步

小结：三种证据链

• 分拆数把无序加法与硬币支付对应起来，$P_0=1$ 是空分拆边界。
• 重数编码与生成函数把每种选择变成幂的系数。
• 单射和归纳给出便宜上界，取对数与参数优化给出更紧的增长界。
• 精确值、阈值证明和渐近估计是不同任务，不能互相冒充。

练习与答案

练习

1. 问题 1：对象与生成函数

解释“分拆数与硬币支付”“P0等于1与小规模枚举”“整数分拆的乘法重数表示”“有限硬币模型与系数计数”“无限项和的无限项积”和“分拆数的生成函数”之间的关系，并计算 $P_5$。

查看答案

无序分拆等价于硬币面值的重数向量；空分拆使 $P_0=1$。5 的七种分拆给出 $P_5=7$。每种面值的任意使用次数形成一个等比因子，所有因子相乘后，$x^5$ 的系数正好统计这七种重数选择。

2. 问题 2：从单射到上界

用“斐波那契上界”“按最小部件分组的单射”“数学归纳法完成全称证明”“精确计数与上界证明的区别”解释为什么可以证明 $P_{15}\lt1000$，却不必先列出全部分拆。

查看答案

单射给出 $P_{k+2}\le P_{k+1}+P_k$，结合 $P_0\le F_1$、$P_1\le F_2$ 和归纳法得到 $P_n\le F_{n+1}$。所以 $P_{15}\le F_{16}=987\lt1000$；这完成阈值证明，但不提供精确值，后者是另一项计数任务。

3. 问题 3：估计链

围绕“生成函数的系数上界”“取对数把积变为和”“负对数的泰勒展开”“巴塞尔和控制东边森林”“辅助参数最优化与指数平方根上界”，写出从 $P_nx^n\le P(x)$ 到最终指数界的关键换元。

查看答案

取对数拆出乘积，使用负对数泰勒展开和几何级数估计，再用巴塞尔和把森林项控制为 $\pi^2x/(6(1-x))$。令 $t=x/(1-x)$，另一侧由 $\log(1+1/t)\lt1/t$ 控制，得到 $g(t)=n/t+\pi^2t/6$；在 $t=\sqrt{6n}/\pi$ 处最小，最终 $P_n\lt\exp(\pi\sqrt{2n/3})$。

4. 问题 4：改 Demo 代码

在计数 Demo 中加入“只允许面值不超过 k”的筛选，输出 q(n,k)，并让重置回到 n=5,k=5。你要怎样检查“生成函数的系数上界”与代码的“精确计数”没有被误标成同一种证据？

查看答案

可以在动态规划中增加 coin 上限，并将 dp[n] 标为精确计数；上界模块只报告一个满足不等式的数值，不能把它写成等号。重置固定到 n=5,k=5，同时在界面上标出“exact count”和“safe upper bound”两个标签。

名词解释

本章出现的专业名词，用大白话再讲一遍。

分拆数

把整数写成无序正整数之和后得到的计数对象。

生成函数

用幂的系数装载一列计数，让组合问题变成取系数问题。

形式幂级数

按系数逐次运算的幂级数，不先把变量当成具体实数。

上界

一个已证明不会小于目标量的安全数字，用于完成阈值判断。

单射

不会把两个不同输入送到同一个输出的映射。

巴塞尔和

经典级数 $1+1/2^2+1/3^2+\cdots=\pi^2/6$。