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

2.5　十二重计数法The twelvefold way

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

在本节中，我们将回顾前两章学到的计数技巧如何给出 12 个计数问题的解。这 12 个问题表述起来彼此相似、都很容易描述。在每一个问题中，我们都是把 \(n\) 个球放进 \(k\) 个盒子。使这些问题互不相同的，是以下几点：球是否全都相同、还是全都可区分（例如用不同的数字标号）；盒子是否全都相同、还是全都可区分；以及对放球方式的限制条件——这些条件有时要求每个盒子里至多放一个球，有时要求至少放一个球。

Gian-Carlo Rota 把这一组问题命名为十二重计数法（the twelvefold way）。在下文中，我们将逐一讨论这 12 个问题。到此为止，读者已经掌握了解决这些问题所需的全部工具，因此读者完全可以在阅读我们的论证之前，先尝试自己给出一个解答。

本节目标把“把 \(n\) 个球放进 \(k\) 个盒子”这一件事，按三个开关拆成 \(2\times2\times3=12\) 种情形，并给出每一种的计数公式：
① 球是否可区分（identical / distinguishable）；
② 盒子是否可区分；
③ 放法限制：无限制 / 每盒至少 \(1\) 个 / 每盒至多 \(1\) 个。
解决这 12 个问题，就把前面学过的整数拆分、集合拆分、组合、弱合成、第二类 Stirling 数等工具全部串了起来。
开关 ① 球：相同 / 可区分 ●●● 还是 ①②③ 开关 ② 盒子：相同 / 可区分 开关 ③ 限制条件 无限制 每盒 ≥ 1（满射） 每盒 ≤ 1（单射）
三个开关组合出 \(2\times2\times3=12\) 个问题；本节正是 Rota 所说的“十二重计数法”。

第一组：球相同、盒子相同

在前三个问题中，我们假设 \(n\) 个球全都相同，且 \(k\) 个盒子也全都相同。

问题 2.50
  1. 把 \(n\) 个相同的球放进 \(k\) 个相同的盒子，有多少种方法？
  2. 若要求每个盒子至少得到一个球，又有多少种方法？
  3. 若要求每个盒子至多得到一个球，又有多少种方法？
解.

(a) 由于盒子和球都相同，唯一要紧的就是各个盒子里分别放了多少个球。换言之，我们在这里处理的是整数 \(n\) 的拆分（partition）。既然盒子都相同，我们不妨按盒子所含球数不增的顺序排列它们。因此，所有可能性的个数为 \(p_k(n)\)，因为实际装有球的盒子至多有 \(k\) 个。

(b) 因为不允许出现非空盒子少于 \(k\) 个的分配，所以可能性的个数为 \(p_k(n)-p_{k-1}(n)\)。当 \(n

(c) 当 \(n>k\) 时这个数为 \(0\)，当 \(n\le k\) 时为 \(1\)，因为每个盒子得到 \(0\) 个或 \(1\) 个球。由于盒子都相同，哪些盒子得到 \(0\)、哪些得到 \(1\) 并无区别。♦

符号约定\(p_k(n)\) 表示把整数 \(n\) 拆成至多 \(k\) 个正整数部分（每部分顺序不计）的方法数；它等价于 \(n\) 拆成最大部分不超过 \(k\) 的拆分数。后面会反复用到 \(p_k(n)\) 与“恰好 \(k\) 个部分”的差。
例：\(n=5,\ k=3\) 的 (a) 把 \(5\) 个相同球放进 \(3\) 个相同盒子（无限制），即数 \(5\) 拆成至多 \(3\) 个部分的拆分 \(p_3(5)\)： \[5,\quad 4{+}1,\quad 3{+}2,\quad 3{+}1{+}1,\quad 2{+}2{+}1.\] 共 \(p_3(5)=5\) 种。
5 4+1 3+2 3+1+1 2+2+1
\(5\) 的全部至多 \(3\) 行的 Ferrers 图：每行就是一个非空盒子里的球数，行数 \(\le 3\)。共 \(5\) 个，故 \(p_3(5)=5\)。
例：同一组数据的 (b)(c) 仍取 \(n=5,\ k=3\)。
  1. (b) 每盒至少 1 个：要求恰好用满 \(3\) 个非空盒子，即 \(5\) 拆成恰好 \(3\) 个正部分。从 (a) 的清单里只保留有 \(3\) 行的：\(3{+}1{+}1\) 与 \(2{+}2{+}1\)，共 \(2\) 个。用公式 \(p_3(5)-p_2(5)=5-3=2\)（\(p_2(5)\) 计 \(5,4{+}1,3{+}2\) 共 \(3\) 个），一致。
  2. (c) 每盒至多 1 个：因为 \(n=5>k=3\)，五个球无法在“每盒最多 1 个”下放进 3 个盒子，故答案为 \(0\)。

第二组：球可区分、盒子相同

在接下来的三个问题中，盒子仍然相同，但球变为可区分。

问题 2.51
  1. 把 \(n\) 个可区分的球放进 \(k\) 个相同的盒子，有多少种方法？
  2. 若要求每个盒子至少得到一个球，有多少种方法？
  3. 若要求每个盒子至多得到一个球，有多少种方法？
解.

(a) 既然球各不相同，我们可以用 \([n]\) 的元素给它们标号。于是这些球被放进相同的盒子里，我们处理的便是集合 \([n]\) 的拆分（set partition）。如果没有其他限制，我们可以使用不超过 \(k\) 个的任意数目的盒子，因此由加法原理，答案为 \(\sum_{i=1}^{k}S(n,i)\)。

(b) 这种情形必须恰好使用 \(k\) 个盒子，所以答案为 \(S(n,k)\)。

(c) 若 \(n>k\)，答案为 \(0\)。否则答案为 \(1\)，因为每个非空盒子里恰好放一个球，而由于盒子都相同，哪个盒子装哪个球并无区别。请注意它与上一问题 (c) 的相似之处。♦

符号约定\(S(n,k)\) 是第二类 Stirling 数（Stirling number of the second kind），表示把 \(n\) 元集合 \([n]=\{1,2,\dots,n\}\) 拆成恰好 \(k\) 个非空、无序的块（block）的方法数。这里盒子相同 = 块无序。
例：\(n=3,\ k=2\) 把可区分的三个球 \(\{1,2,3\}\) 放进 2 个相同盒子。
  1. (b) 恰好用满 2 个非空盒子：即 \(S(3,2)\)。把 \(\{1,2,3\}\) 分成 2 个非空无序块：\(\{1\}\{2,3\}\)、\(\{2\}\{1,3\}\)、\(\{3\}\{1,2\}\)，共 \(S(3,2)=3\) 种。
  2. (a) 无限制（最多用 2 个盒子）：\(\sum_{i=1}^{2}S(3,i)=S(3,1)+S(3,2)=1+3=4\)。其中 \(S(3,1)=1\) 是“三球全进一个盒子”。
  3. (c) 每盒至多 1 个：\(n=3>k=2\)，放不下，答案 \(0\)。
{1} {2,3} {2} {1,3} {3} {1,2} ⇒ \(S(3,2)=3\)
盒子相同，所以 \(\{1\}\{2,3\}\) 与 \(\{2,3\}\{1\}\) 算同一种；恰好用 2 个非空块共 3 种。

第三组：球相同、盒子可区分

在接下来的三个问题中，我们把条件反过来：盒子可区分，但球相同。

问题 2.52
  1. 把 \(n\) 个相同的球放进 \(k\) 个可区分的盒子，有多少种方法？
  2. 若要求每个盒子至少得到一个球，有多少种方法？
  3. 若要求每个盒子至多得到一个球，有多少种方法？
解.

(a) 由于球都相同，唯一要紧的是每个盒子里放了多少个球。然而盒子可区分，所以它们的顺序是有意义的。换言之，我们处理的是把 \(n\) 写成 \(k\) 个部分的弱合成（weak composition）。因此答案为 \(\binom{n+k-1}{k-1}\)。

(b) 因为没有盒子能为空，所以我们处理的是把 \(n\) 写成 \(k\) 个部分的合成（composition），故答案为 \(\binom{n-1}{k-1}\)。

(c) 若 \(n>k\)，答案为 \(0\)。否则，我们只需选出那 \(n\) 个各装一个球的盒子，这可以用 \(\binom{k}{n}\) 种方法完成。♦

弱合成 vs 合成把 \(n\) 写成有序的 \(k\) 个部分 \(n=a_1+a_2+\dots+a_k\)：若允许 \(a_i=0\)，称为弱合成（盒子可空）；若要求每个 \(a_i\ge1\)，称为合成（盒子非空）。“有序”正对应盒子可区分。
例：\(n=4,\ k=3\) 的 (a)，隔板法 把 \(4\) 个相同球放进 \(3\) 个可区分盒子（可空）。用隔板法（stars and bars）：把 \(4\) 个球（★）排成一行，再插入 \(k-1=2\) 块隔板（｜）把它们隔成 \(3\) 段，每段的球数就是对应盒子的球数。
  1. 一共有 \(4+2=6\) 个位置，球和隔板共 \(6\) 个符号。
  2. 只需在 \(6\) 个位置里挑出 \(2\) 个放隔板，其余放球：\(\binom{6}{2}=\binom{4+3-1}{3-1}=15\) 种。
  3. 例如 \(\bigstar\bigstar\,|\,\bigstar\,|\,\bigstar\) 表示 \((2,1,1)\)；\(|\,\bigstar\bigstar\bigstar\bigstar\,|\) 表示 \((0,4,0)\)。
故答案 \(\binom{6}{2}=15\)，与 \(\binom{n+k-1}{k-1}\) 一致。
★ ★ | ★ | ★ 盒1 = 2 盒2 = 1 盒3 = 1 4 个 ★ 与 2 个 ｜ 排队：\(\binom{6}{2}=15\)
“星与隔板”：相同的球（★）之间放 \(k-1\) 块隔板（｜），隔板位置一定，分配就唯一确定。
例：同数据的 (b)(c)
  1. (b) 每盒至少 1 个，\(n=4,k=3\)：先给每盒各放 1 个，剩 \(4-3=1\) 个球再自由分给 3 个盒子；或直接用公式 \(\binom{n-1}{k-1}=\binom{3}{2}=3\)。具体为 \((2,1,1),(1,2,1),(1,1,2)\)。
  2. (c) 每盒至多 1 个，\(n=4,k=3\)：因 \(n=4>k=3\)，答案 \(0\)。若改成 \(n=2,k=3\)：在 3 个可区分盒子中选 2 个各放 1 球，\(\binom{3}{2}=3\) 种。

第四组：球可区分、盒子可区分

在最后三个问题中，盒子和球都可区分。

问题 2.53
  1. 把 \(n\) 个可区分的球放进 \(k\) 个可区分的盒子，有多少种方法？
  2. 若要求每个盒子至少得到一个球，有多少种方法？
  3. 若要求每个盒子至多得到一个球，有多少种方法？
解.

(a) 由于任何一个球都可以放进任何一个盒子，可能性的个数为 \(k^n\)。

(b) 这类似于把 \([n]\) 拆成 \(k\) 个块，但现在块的顺序是有意义的，所以答案为 \(S(n,k)\,k!\)。

(c) 同样地，若 \(n>k\)，答案为 \(0\)。否则，第一个球有 \(k\) 种选择，第二个球有 \(k-1\) 种选择，依此类推，所以答案为 \((k)_n\)。♦

下降阶乘\((k)_n=k(k-1)(k-2)\cdots(k-n+1)\) 是 \(n\) 个因子的下降阶乘（falling factorial）。它正是“从 \(k\) 个可区分盒子中，为 \(n\) 个可区分球依次选一个互不相同的盒子”的乘法计数。
例：\(n=3,\ k=2\)（盒子、球都可区分）
  1. (a) 无限制：每个球独立选 2 个盒子之一，\(2^3=8\) 种。
  2. (b) 每盒至少 1 个：\(S(3,2)\cdot 2!=3\times2=6\)。直观上：先把 3 个球分成 2 个非空无序块（\(S(3,2)=3\) 种），再把这 2 个块按顺序塞进 2 个可区分盒子（\(2!=2\) 种）。也等于 \(2^3-2=6\)（减去“全进盒1”和“全进盒2”这两种使某盒为空的放法）。
  3. (c) 每盒至多 1 个：\(n=3>k=2\)，答案 \(0\)。若改成 \(n=2,k=3\)：\((3)_2=3\times2=6\)。
盒 A 盒 B 1 2 3 每个球连一根线到某盒：共 \(2^3=8\) 种映射 两盒都非空（满射）的有 \(S(3,2)\cdot2!=6\) 种
“可区分球→可区分盒子”就是从 \([n]\) 到 \([k]\) 的函数；无限制 = 全部函数 \(k^n\)，每盒至少 1 个 = 满射 \(S(n,k)\,k!\)，每盒至多 1 个 = 单射 \((k)_n\)。

十二个答案汇总

一张表收齐十二重行：球是否相同 × 盒子是否相同；列：三种限制。其中 \([n\le k]\) 表示当 \(n\le k\) 时取 \(1\)、否则取 \(0\)。
球 \ 盒 无限制 (a) 每盒 ≥ 1 (b) 每盒 ≤ 1 (c)
相同球 / 相同盒 \(p_k(n)\) \(p_k(n)-p_{k-1}(n)\) \([n\le k]\)
可区分球 / 相同盒 \(\sum_{i=1}^{k}S(n,i)\) \(S(n,k)\) \([n\le k]\)
相同球 / 可区分盒 \(\binom{n+k-1}{k-1}\) \(\binom{n-1}{k-1}\) \(\binom{k}{n}\)
可区分球 / 可区分盒 \(k^{n}\) \(S(n,k)\,k!\) \((k)_{n}\)
（“每盒 ≤ 1”那一列在前两行都是 \([n\le k]\)：球能不能放下只看个数，盒子相同时放法唯一。）

如果读者把这 12 个问题全都做了一遍，那么在尝试解决一个枚举问题时，她将会有几个有用的问题可问：我们所计数的对象是否互不相同？它们的顺序是否要紧？是否允许重复？这些问题恰好对应着上面三个开关——它们能帮助我们迅速判断手头的计数问题落在十二重计数法的哪一格。

即时自测
  1. 用十二重计数法判断：把 \(4\) 个相同的球放进 \(3\) 个可区分盒子且允许空盒，有几种？（提示：用 \(\binom{n+k-1}{k-1}\)。）
  2. 把 \(4\) 个可区分球放进 \(2\) 个可区分盒子，要求每盒至少 1 个，有几种？分别用 \(2^4-2\) 和 \(S(4,2)\cdot2!\) 验证。
  3. 把 \(4\) 个可区分球放进 \(4\) 个相同盒子，每盒至多 1 个，有几种？把它与“\(4\) 个可区分球放进 \(4\) 个可区分盒子、每盒至多 1 个”的答案 \((4)_4=24\) 作对比，解释差别为何是 \(4!\) 倍。

返回 全书目录