Bóna · 枚举与解析组合学导论 · 第 2 章 基本方法的应用

2.3　整数的分拆Partitions of integers

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

在本节中，我们重新研究“把一个正整数写成若干正整数之和”有多少种方式这个问题。不过，这一次各个加项（part，又称“部分”）必须按不增（nonincreasing）的顺序排列。

本节目标上一节我们数过合成（composition）——把整数写成有序的正整数之和。本节要数的是分拆（partition）——把整数写成正整数之和，但不计顺序（约定按从大到小排列）。我们要弄清：什么叫整数的分拆？分拆数 \(p(n)\) 怎么记、前几项是多少？为什么它比之前学的计数对象都难求？它增长得有多快？

2.3.1　由正整数组成的不增有限数列

史密斯女士上次搬家时，要从一辆卡车上卸下 \(20\) 个一模一样的中号箱子，搬进她的新房子。她想尽快搬完，于是试着一次同时搬好几个箱子。然而随着时间推移，她越来越累，所以只要这一趟从卡车搬到房子里所搬的箱子数不超过上一趟，她就很满意了。她甚至完全不会去想在某一趟增加搬运的箱子数。请问她把这 \(20\) 个箱子搬进新房子，一共有多少种不同的方式？

这个问题可能让读者想起合成。的确，由于这些箱子完全相同，我们只关心它们的数目。也就是说，我们想把 \(20\) 分解成若干正整数之和。然而，与合成不同的是，各加项的顺序必须是不增的。所以 \(12+8\) 是允许的，而 \(3+4+1+10\) 是不允许的。这表明我们面对的是一个与上一节不同（而且我们将看到，要难得多）的问题。下面的定义开始为处理这种新的枚举问题搭建框架。

合法（不增）： 12 8 12 ≥ 8 ✓ 非法（顺序乱）： 3 4 1 10 3 < 4，违反不增 和都是 20，但分拆只承认按从大到小排好的那一种写法。
同样和为 \(20\)：\(12+8\) 是一个分拆；\(3+4+1+10\) 不是合法写法（它对应的分拆是把它重排成 \(10+4+3+1\)）。
定义 2.19 若由正整数组成的有限数列 \((a_1,a_2,\dots,a_k)\) 满足 \[a_1\ge a_2\ge\dots\ge a_k\quad\text{且}\quad a_1+a_2+\dots+a_k=n,\] 则称该数列为整数 \(n\) 的一个分拆（partition）。

请注意，多少有些遗憾的是，“partition（分拆 / 划分）”这个词既用于整数 \(n\) 的分拆，也用于集合 \([n]\) 的划分，而这两者当然是非常不同的概念。某些其他语言通过给这两个概念用不同的词来解决这一困扰。读者在阅读英文时应当小心，不要把这两个概念混淆。我们尽力帮助读者区分：请记住 \(n\) 是一个整数，而 \([n]\) 是一个集合。

整数 \(n\) 的分拆个数记作 \(p(n)\)。

例 2.20 正整数 \(4\) 有五个分拆，即 \((4),\ (3,1),\ (2,2),\ (2,1,1),\ (1,1,1,1)\)。因此 \(p(4)=5\)。
  1. 只用一个加项：\(4\) 本身，即 \((4)\)。
  2. 用两个加项（前项 ≥ 后项）：\(3+1\) 与 \(2+2\)，即 \((3,1),(2,2)\)。注意 \(1+3\) 不另算——它和 \(3+1\) 是同一个分拆。
  3. 用三个加项：\(2+1+1\)，即 \((2,1,1)\)。
  4. 用四个加项：\(1+1+1+1\)，即 \((1,1,1,1)\)。
  5. 合计 \(1+2+1+1=5\) 个，所以 \(p(4)=5\)。
对比：合成与分拆的区别 上一节中 \(4\) 的合成（有序）共有 \(2^{4-1}=8\) 个：\(4,\ 3{+}1,\ 1{+}3,\ 2{+}2,\ 2{+}1{+}1,\ 1{+}2{+}1,\ 1{+}1{+}2,\ 1{+}1{+}1{+}1\)。而分拆不计顺序，把其中只是次序不同的写法（如 \(3{+}1\) 与 \(1{+}3\)）视为同一个，于是只剩 \(5\) 个。这正说明 \(p(4)=5<8\)。

关于 \(p(n)\) 前几个值，见图 2.4。

n p(n) 11 22 33 45 57 611 715 822
图 2.4　\(n\le 8\) 时 \(p(n)\) 的取值。可以看出它增长得相当快，却没有明显的简单规律。

此刻读者大概迫不及待地想让我们证明一个关于 \(p(n)\) 的优美公式。\(p(n)\) 的精确公式确实存在，但客气地说，它绝不简单。它涉及一个无穷和、复数、函数 \(\sinh\)，以及许多其他东西。这个公式由哈代（Hardy）、拉马努金（Ramanujan）和拉德马赫（Rademacher）以各种形式得到。感兴趣的读者可以参阅 George Andrews 的著作《Theory of Partitions》[6] 第 5 章，或 George Andrews 与 Kimmo Eriksson 合著的《Integer Partitions》[7]，以了解细节。

对 \(p(n)\) 这个公式的详细讨论远超出本书的范围，但我们至少要提一个原因，说明为什么这个枚举问题比之前的问题更难。在之前讨论的问题中，我们证明的枚举公式要么是关于变量 \(n\) 的指数级（甚至更大）的，例如 \(2^{n-1}\)、\(n!\)、\(k^n\) 或 \(\binom{2n}{n}\)；要么是多项式级的，例如 \((n)_k\) 或 \(\binom{n}{k}\)。然而，我们将在习题 19 和 20 中说明：\(p(n)\) 增长得比任何多项式函数 \(q(n)\) 都快。另一方面，要证明 \(p(n)\) 增长得比任何指数函数 \(a^n\)（\(a>1\)）都慢，会稍微麻烦一些，但仍不算太难。（\(n\) 的全部合成的数目，就给出了 \(p(n)\) 的一个粗略上界。）因此，\(p(n)\) 既不是指数级的，也不是多项式级的，这意味着它必定是一个更“奇异（exotic）”、更不为人熟知的函数。

怎么理解“既非多项式、也非指数”把三类增长速度排个序：多项式（如 \(n^2\)）< \(p(n)\) < 指数（如 \(2^n\)）。也就是说 \(p(n)\) 比所有多项式都快、又比所有指数都慢，夹在两类之间。粗略上界来自合成：\(n\) 的合成共 \(2^{n-1}\) 个，而每个分拆至少对应一个合成，所以 \(p(n)\le 2^{n-1}\)，这就是“比指数慢”的一个直观来源。

下面这条我们不予证明的定理，告诉我们关于 \(p(n)\) 增长率的更多信息。回忆记号 \(\sim\)，它是在公式 (1.12) 之后紧接着引入的。

定理 2.21 当 \(n\to\infty\) 时，函数 \(p(n)\) 满足 \[p(n)\sim\frac{1}{4n\sqrt{3}}\,\exp\!\left(\pi\sqrt{\frac{2n}{3}}\,\right).\tag{2.1}\]

此时读者可能会说：这个公式里明明含有一个指数表达式，可我们之前不是承诺过 \(p(n)\) 会比所有指数函数都小吗？请注意，上式右边是 \(\sqrt{n}\) 的指数函数，而不是 \(n\) 的指数函数。无论常数 \(a\) 取得多么小，函数 \(e^{an}\) 总会比上式右边增长得更快，因而也比 \(p(n)\) 增长得更快。

为什么 \(\exp(\pi\sqrt{2n/3})\) 仍比 \(e^{an}\) 慢
  1. 关键在指数里的变量：右边指数是 \(\pi\sqrt{2n/3}\)，正比于 \(\sqrt{n}\)；而 \(e^{an}\) 的指数 \(an\) 正比于 \(n\)。
  2. 当 \(n\) 很大时，\(n\) 远远大于 \(\sqrt{n}\)（例如 \(n=10^6\) 时 \(\sqrt{n}=10^3\)）。
  3. 所以无论 \(a\) 多小，\(an\) 终将超过 \(\pi\sqrt{2n/3}\)，于是 \(e^{an}\) 终将甩开 \(p(n)\)。这与“\(p(n)\) 比所有指数函数都慢”并不矛盾。

文献 [6] 的第 5 章解释了如何从前面提到的那个复杂精确公式推出这个渐近公式。

到这里，读者可能会说：也许一上来就追求 \(p(n)\)（即 \(n\) 的全部分拆数）的公式过于雄心勃勃了，不如先攻克“把 \(n\) 分拆成给定个数的加项”的计数问题。这本质上等价于“把 \(n\) 分拆成至多 \(k\) 个加项”的计数问题。设这样的分拆数为 \(p_k(n)\)。那么习题 19 和 20 表明：对任意固定的 \(k\)，函数 \(p_k(n)\) 是一个非常接近多项式的函数。我们邀请读者去解那些习题，以便把这一陈述说得更精确。在本节剩下的部分，我们将专注于一种适用于整数分拆的、引人入胜的证明技巧，即费勒斯图形（Ferrers shapes）。

什么是费勒斯图形（提前认识）费勒斯图形是把一个分拆画成“点阵（或方块阵）”的工具：分拆 \((a_1,a_2,\dots,a_k)\) 的第 \(i\) 行从左对齐摆 \(a_i\) 个方块。由于 \(a_1\ge a_2\ge\dots\ge a_k\)，各行长度自上而下不增，呈“左对齐的阶梯”。把这张图沿主对角线翻转（行列互换），就得到另一个分拆，称为共轭分拆（conjugate）——这正是许多分拆恒等式的证明利器。下面以 \(8=4+3+1\) 为例。
分拆 (4,3,1) →翻转→ 共轭 (3,2,2,1) 行长 4,3,1（共 8 格） 行长 3,2,2,1（仍 8 格）
把 \((4,3,1)\) 摆成左对齐方块阵（行长不增），沿对角线翻转后按列读数得到 \((3,2,2,1)\)，它是 \(8\) 的另一个分拆。两者的方块总数都是 \(8\)。这就是费勒斯图形与共轭分拆的基本想法，下文将用它建立分拆之间的双射。

返回 全书目录