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

2.1　多重集与有序分拆Multisets and compositions

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

在本节中，我们将证明一些公式，用来计数：一个正整数能用多少种方式写成若干非负整数（或正整数）之和。这里求和项的次序是重要的。

本节目标把同一个计数问题用三种等价的语言讲清楚：①从集合 \(S\) 中可重复取、不计次序地取出 \(n\) 个元素（多重集）；②把整数 \(n\) 写成 \(k\) 个非负整数有序之和（弱有序分拆）；③把 \(n\) 个相同的球放进 \(k\) 个编号盒子。最终用一个二项式系数 \(\binom{n+k-1}{k-1}\) 把它们一次性数清楚。

2.1.1　弱有序分拆

一个四口之家——安妮（Anne）、本尼（Benny）、查尔斯（Charles）和丹妮丝（Denise）——坐在客厅里看电影。无巧不成书，电影放映期间家里的电话响了 10 次。更糟的是，电话答录机坏了，而这家人正在等一个重要的来电，于是每次电话响他们都去接。为了给自己打气，全家约定：电影结束时，每个人按自己接电话的次数，每接一次就得到一勺冰淇淋。这 10 勺冰淇淋当然会在电影一结束就被吃掉，但这 10 勺冰淇淋一共有多少种分配方式呢？

让我们先做两点观察。第一，四个人接电话的先后次序无关紧要，真正起作用的只是每个人各接了多少次电话。这听上去像是一个子集（subset）问题。然而——这是我们的第二点观察——集合 \(\{A,B,C,D\}\) 没有任何子集含有 \(10\) 个元素，所以我们必须使用一个不同的模型。我们要找的是由字母 \(A,B,C,D\) 组成、总共含 \(10\) 个字母的“收集物”，例如 \(ABABBBCCDD\)。

定义（多重集）这样一种收集物——即一种收集物，其中每个元素都必须来自一个指定的集合 \(S\)，允许元素重复，并且元素的次序无关紧要——称为集合 \(S\) 上的一个多重集（multiset）。
例取 \(S=\{A,B,C,D\}\)。字符串 \(ABABBBCCDD\) 表示的多重集，按字母统计重数（multiplicity）：\(A\) 出现 \(2\) 次，\(B\) 出现 \(4\) 次，\(C\) 出现 \(2\) 次，\(D\) 出现 \(2\) 次，合计 \(2+4+2+2=10\) 个字母。因为不计次序，\(ABABBBCCDD\) 与 \(AABBBBCCDD\) 表示的是同一个多重集。

用这套术语，我们的任务就是计数四元素集合 \(S=\{A,B,C,D\}\) 上所有的 \(10\) 元素多重集。为了让任务更简单，请注意：这些多重集完全由四个元素各自出现的重数所决定。也就是说，如果我们知道某个多重集含有两个 \(A\)、一个 \(B\)、三个 \(C\)、四个 \(D\)，那么我们就掌握了关于这个多重集的全部信息。确实，没有别的东西需要知道了，因为元素的次序无关紧要。

多重集：两个 A、一个 B、三个 C、四个 D（共 10 个） AA B CCC DDDD 等价于解 \( a+b+c+d=10 \) 的一组取值 \((a,b,c,d)=(2,1,3,4)\) 重数 = 各元素出现的次数；重数定下来，多重集就定下来了
多重集由“每个元素的重数”唯一确定，于是“数多重集”变成了“数一组重数”。

这就把我们的任务化简为：仅仅求出整数 \(10\) 能用多少种方式写成四个非负整数之和（这四个数就是 \(A,B,C,D\) 的重数）。换句话说，我们要求方程

\[a+b+c+d=10\]

的非负整数解的个数。请注意，在这种语言下，求和项的次序是重要的。确实，解 \(2+3+1+4=10\) 对应的多重集含有两个 \(A\)，而解 \(1+2+4+3=10\) 对应的多重集只含有一个 \(A\)——两者是不同的解，对应不同的多重集。

把“\(k\) 元素集合上的 \(n\) 元素多重集”与“将 \(n\) 表示成 \(k\) 个非负整数之和”相互对应起来，这一思想引出了一个重要的、有专门名称的概念。

定义 2.1（弱有序分拆）设 \(a_1,a_2,\dots,a_k\) 是非负整数，满足 \[\sum_{i=1}^{k}a_i=n.\] 则这个有序的 \(k\) 元组 \((a_1,a_2,\dots,a_k)\) 称为 \(n\) 的一个分成 \(k\) 部分的弱有序分拆（weak composition of \(n\) into \(k\) parts）。
例取 \(n=3\)、\(k=2\)，即数 \(a_1+a_2=3\) 的非负整数解。它们是 \[(3,0),\;(2,1),\;(1,2),\;(0,3),\] 共 \(4\) 个。注意 \((2,1)\) 与 \((1,2)\) 算作不同的弱有序分拆（次序重要），而且允许某部分取 \(0\)（这正是“弱”字的含义）。

上面的讨论说明：从“\(n\) 分成 \(k\) 部分的弱有序分拆”的集合，到“\(k\) 元素集合上的 \(n\) 元素多重集”的集合，存在一个自然的双射（bijection）。因此，我们不妨改去求 \(n\) 分成 \(k\) 部分的弱有序分拆的个数，而不必直接求 \(k\) 元素集合上 \(n\) 元素多重集的个数——两者个数相同。

什么叫“双射”，为什么它能换着数双射就是两个集合之间一一对应、不重不漏的配对。一旦建立了双射，两个集合的元素个数必然相等，于是数其中较容易的一个即可。这里的配对规则是：多重集 \(\longleftrightarrow\) 各元素重数排成的有序组 \((a_1,\dots,a_k)\)。每个多重集对应唯一一组重数，每组重数也还原出唯一一个多重集，所以是双射。

这些对象（弱有序分拆）比 \([n]\) 的 \(k\) 元素子集要稍难计数一些，但枚举它们的公式同样是一个二项式系数（binomial coefficient）。

定理 2.2 \(n\) 分成 \(k\) 部分的弱有序分拆的个数为 \[\binom{n+k-1}{n}=\binom{n+k-1}{k-1}.\]
证明. 考虑 \(n\) 个完全相同的球，要把它们放进编号为 \(1\) 到 \(k\) 的 \(k\) 个盒子里。每一种这样的放法都等价于 \(n\) 分成 \(k\) 部分的一个弱有序分拆：第 \(i\) 个盒子里球的个数就是第 \(i\) 部分 \(a_i\)。
现在，我们按下面的办法来计数把 \(n\) 个球放入 \(k\) 个盒子的方式：把这 \(k\) 个盒子排成一行，使盒子上的编号从小到大排列，相邻的第 \(i\) 个与第 \(i+1\) 个盒子之间用一堵隔墙（wall）分开（见图 2.1）。
盒子 1 盒子 2 ······ 盒子 k 隔墙 图 2.1　把盒子排成一行（共 k 个盒子，盒与盒之间共需 k−1 堵隔墙）
图 2.1　Lining up our boxes（把盒子排成一行）。\(k\) 个盒子排好后，内部一共有 \(k-1\) 处分隔，用 \(k-1\) 堵隔墙标出。

（说明：原文 PDF 在此处截断于图 2.1。以下为这一证明的自然续完，思想就是上面排好的“球与隔墙”——即组合学中著名的“隔板法 / 星与隔板”。）

证明（续）. 既然 \(k\) 个盒子排成一行后，内部共有 \(k-1\) 处缝隙，我们就放入 \(k-1\) 堵隔墙。于是问题变成：把 \(n\) 个相同的球和 \(k-1\) 堵相同的隔墙排成一行——隔墙把这一行切成 \(k\) 段，从左到右第 \(i\) 段中球的个数就是 \(a_i\)。这样，每一种球与隔墙的排列都恰好对应一个弱有序分拆，反之亦然，故二者一一对应。
这一行里总共有 \(n+(k-1)=n+k-1\) 个位置。一旦决定了哪 \(n\) 个位置放球（其余位置自动放隔墙），整个排列就定下来了；等价地，决定哪 \(k-1\) 个位置放隔墙也一样。因此排列的总数为 \[\binom{n+k-1}{n}=\binom{n+k-1}{k-1}.\] （两个二项式系数相等，是因为 \(\binom{m}{r}=\binom{m}{m-r}\)，这里 \(m=n+k-1\)、\(m-n=k-1\)。）证毕。♦

把这条证明拆成最小的步子，便于看清它“为什么对”：

  1. 建模。把“给 \(A,B,C,D\) 各分多少”改述成“把 \(n\) 个相同的球放进 \(k\) 个编号盒子”——盒子 \(i\) 里的球数就是第 \(i\) 部分，这一步把抽象的分拆变成可以画出来的东西。
  2. 排成一行。把 \(k\) 个盒子按编号排成一行，盒与盒之间共有 \(k-1\) 道缝，于是用 \(k-1\) 堵隔墙把它们隔开。
  3. 去掉盒壁，只看球和墙。既然盒子已按固定次序排好，盒子本身就不必画了，只保留 \(n\) 个球和 \(k-1\) 堵隔墙排成一行；从左数，两堵相邻隔墙之间的球数就是一部分。
  4. 转成“选位置”。这一行共 \(n+k-1\) 个位置，从中选出 \(n\) 个位置放球（剩下的放隔墙）即完全确定一种排法，故个数为 \(\binom{n+k-1}{n}\)。
  5. 对称改写。由 \(\binom{m}{r}=\binom{m}{m-r}\) 得 \(\binom{n+k-1}{n}=\binom{n+k-1}{k-1}\)，即“选隔墙位置”得到同一答案。
n=10 个球 ＋ k−1=3 堵隔墙 ＝ 13 个位置 a=2 b=1 c=3 d=4 这一排 ↔ 弱有序分拆 (2,1,3,4)；方式数 \( \binom{10+3}{3}=\binom{13}{3}=286 \)
以 \(n=10,k=4\) 为例：每一种“球与隔墙”的排列恰好对应一个弱有序分拆。隔墙挨着隔墙就表示中间那部分取 \(0\)。
例（回到冰淇淋问题）四口之家接电话共 \(10\) 次，即求 \(a+b+c+d=10\) 的非负整数解个数，也就是 \(n=10\) 分成 \(k=4\) 部分的弱有序分拆个数。代入定理 2.2： \[\binom{10+4-1}{4-1}=\binom{13}{3}=\frac{13\cdot12\cdot11}{3\cdot2\cdot1}=286.\] 所以这 \(10\) 勺冰淇淋共有 \(286\) 种分配方式。
小例验证（手数对照公式）取 \(n=3,k=2\)。公式给出 \(\binom{3+2-1}{2-1}=\binom{4}{1}=4\)。前面我们手数出 \((3,0),(2,1),(1,2),(0,3)\) 恰好 \(4\) 个，吻合。再取 \(n=2,k=3\)：公式给 \(\binom{2+3-1}{3-1}=\binom{4}{2}=6\)，对应 \((2,0,0),(0,2,0),(0,0,2),(1,1,0),(1,0,1),(0,1,1)\)，也正好 \(6\) 个。
即时自测
  1. 方程 \(x_1+x_2+x_3+x_4+x_5=8\) 有多少组非负整数解？
  2. \(\{A,B,C\}\) 上共有多少个 \(6\) 元素多重集？请同时用“多重集”和“弱有序分拆”两种语言解释你的答案。
  3. 把 \(7\) 个相同的球放进 \(3\) 个编号盒子，允许有盒子为空，共有多少种放法？若进一步要求每个盒子至少放一个球（即各部分均为正整数），又有多少种？（提示：先给每盒预放一个球。）

返回 全书目录