partition · p(n) 与共轭

整数分拆与 Ferrers 图

把正整数 $n$ 写成若干正整数之和，且不计各加项的先后，每一种写法是 $n$ 的一个分拆（partition），加项称部分（part），分拆的个数记 $p(n)$ 。 $p(4) = 5$ ，五种写法是 $4$ 、 $3+1$ 、 $2+2$ 、 $2+1+1$ 、 $1+1+1+1$ 。同样叫「拆」，枚举全部划分拆的是一个由可辨元素组成的集合，块与块之间彼此不同；本页拆的是一个整数，元素不可辨，只有各部分的大小算数。两种口径的计数分别落在 Stirling 数与分拆数上，对照见Stirling 数。

1 · 有序和式与无序和式

partition · p(n) 无闭式 / composition · 2ⁿ⁻¹

若把次序也算进去， $3 = 2+1$ 与 $3 = 1+2$ 记作两种，这样的有序和式称 composition。它的个数有闭式：把 $n$ 摊成一排 $n$ 个单位，相邻单位之间共 $n-1$ 个空隙，每个空隙独立地断或不断，断点把这排单位切成若干段，段长依次就是各加项。空隙的断法与 composition 一一对应，故其数为 $2^{n-1}$ 。这与可重复选取的隔板法是同一套构造，区别在于隔板法允许两根隔板重合而本节的断点两两不同，双射的一般写法见双射与双计数。

不计次序，就是把这 $2^{n-1}$ 个 composition 按「排序后相同」归并成若干类，类数即 $p(n)$ 。 $n = 6$ 时 $2^5 = 32$ 归并成 $p(6) = 11$ 类； $n = 12$ 时 $2048$ 归并成 $77$ 类，比值随 $n$ 迅速拉开。

2 · Ferrers 图与共轭分拆

conjugate · 行列互换的对合双射

把一个分拆画成点阵：一行一个部分，行内点数即该部分的大小，各行左对齐，自上而下行长非增。这张点阵称 Ferrers 图。沿主对角线转置，即把行读成列，得到的仍是一个行长非增的点阵，它所对应的分拆称共轭分拆。

定理 2.1 转置是 $n$ 的分拆集合上的一个对合双射；恰有 $k$ 个部分的分拆数，等于最大部分为 $k$ 的分拆数。

证明转置后第 $j$ 行的点数，是原图中长度不小于 $j$ 的行数，这个量随 $j$ 非增，且总点数不变，故转置把 $n$ 的分拆映到 $n$ 的分拆。逐点看，转置两次每个点回到原位，所以转置是自身的逆映射，为对合，从而是双射。原图的行数在转置后成为第一行的长度，原图第一行的长度成为行数：部分数与最大部分互换。把这个双射限制在「恰有 $k$ 个部分」的分拆上，像集恰是「最大部分为 $k$ 」的分拆，两者等势。∎

图 2-1 · 分拆的 Ferrers 点阵与它的转置。可拖动

n

选取任一分拆，开启转置看点阵沿主对角线翻折，右侧计数表按部分数与最大部分分列，两列逐行相等。

本页 conjugate 按列计数实现：结果的第 $j$ 项取原分拆中大于 $j$ 的部分个数。这个写法对输入是否已排序并不敏感，conjugate([1, 3]) 与 conjugate([3, 1]) 同样给出 $2+1+1$ ；代价是对合性只在非增输入上成立，把乱序的 [1, 3] 转置两次得到的是 $3+1$ 而非原序列。测试里为这条行为单列了一项断言，免得后来者把它当缺陷「修好」。

3 · 分拆数的递推

p(n, m) = p(n−m, m) + p(n, m−1)

$p(n)$ 没有初等闭式。实用算法给最大部分设一个上限：记 $p(n, m)$ 为最大部分不超过 $m$ 的分拆数，按「有没有用到大小为 $m$ 的部分」分类，用到则去掉一个仍留在同一上限下，没用到则上限降为 $m-1$ ：

p(n,\, m) = p(n-m,\, m) + p(n,\, m-1)

边界是 $p(0, m) = 1$ 与 $p(n, 0) = 0\ (n > 0)$ ，答案取 $p(n, n)$ 。滚动成一维后，外层枚举部分大小、内层正序枚举剩余量，与完全背包的一维递推逐字相同：一件物品可取任意多件，对应一种大小可以重复使用。生成函数的写法是 $\prod_{i \ge 1} (1 - x^i)^{-1}$ ，其中 $x^n$ 的系数即 $p(n)$ ，展开见生成函数。增长上，Hardy–Ramanujan 渐近式给出 $p(n) \sim \frac{1}{4n\sqrt{3}} \exp\left(\pi \sqrt{2n/3}\right)$ ，是次指数的。

警示 · 一维 DP 若用 number 累加，第一处失真出现在 $n = 300$ ：精确值 $p(300) = 9253082936723602$ 是首个越过 Number.MAX_SAFE_INTEGER 的分拆数，浮点累加给出 $9253082936723596$ ，小 $6$ ，而 $p(299)$ 仍逐位精确。枚举失效得更早：本页 partitions 列出 $p(50) = 204226$ 条约 56 ms、 $p(70) = 4087968$ 条约 1.2 s， $p(100) = 190569292$ 是 $p(50)$ 的九百三十三倍，只能计数不能列举。图 2-1 据此把 $n$ 限在 $16$ ，并只渲染前 $200$ 条。

4 · 参考文献

Partition (number theory). Wikipedia. 分拆数 $p(n)$ 、Ferrers 图与共轭分拆的基本性质。https://en.wikipedia.org/wiki/Partition_(number_theory)
Composition (combinatorics). Wikipedia. 有序和式及其 $2^{n-1}$ 的计数。https://en.wikipedia.org/wiki/Composition_(combinatorics)
Pentagonal number theorem. Wikipedia. 欧拉五边形数定理给出的 $p(n)$ 快速递推。https://en.wikipedia.org/wiki/Pentagonal_number_theorem