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

2.2　集合的划分Set partitions

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

现在我们要考虑一个更困难的计数问题。与之相应，我们得到的计数公式也会更复杂。

本节目标把一个有限集合 \([n]=\{1,2,\dots,n\}\) 不重不漏地拆成若干个非空的“小堆”（称为块），数一数：恰好拆成 \(k\) 个块时，有多少种不同的拆法。这个个数就是第二类斯特林数（Stirling number of the second kind）。

2.2.1　第二类斯特林数

在某个我们觉得格外勇敢的日子，我们邀请了孩子们的一些朋友到家里来玩。算上所有人，一共有五个孩子在场。很快就发现，没有哪一个房间大得能容下全部五人，于是他们分散到三个可用的房间里，并且三个房间都用上了。这些孩子有多少种不同的分法呢？

如果你试着回答这个问题，很快就会意识到：它问得并不精确。缺少的是对“不同”的定义。也就是说，下面这两种安排算不算“不同”：一种是 \(A\) 与 \(B\) 在某个房间里玩、\(C\) 与 \(D\) 在另一个房间、\(E\) 在剩下的房间；另一种是 \(E\) 在第一个房间、\(A\) 与 \(B\) 在第二个房间、\(C\) 与 \(D\) 在最后一个房间？

对这个问题没有对错之分；两种理解都引出有效而有趣的组合问题。然而，这两个问题彼此联系得非常紧密。事实上，容易看出：如果我们把三个房间看作互不相同，那么答案恰好是把房间看作完全相同时的 \(3!=6\) 倍。这是因为我们可以用 \(3!\) 种方式去置换这些房间。

房间看作「不同」 房间看作「相同」 房1AB 房2CD 房3E 房1E 房2AB 房3CD 这两种算「不同」 AB CD E 只看谁和谁在一起 → 两种算「相同」（同一个划分）
房间有别时，给同一组“谁和谁一起”的搭配再贴上房间标签，共有 \(3!=6\) 种贴法；房间无别时它们合并成同一个划分。所以“有别”的答案 = “无别”的答案 \(\times\,3!\)。

正因为这两个问题之间存在如此紧密的联系，我们只需解决“房间被看作相同”的那一个就够了。也就是说，真正起作用的只有“玩伴关系”。换句话说，两种玩耍安排被视为不同，当且仅当存在至少一个孩子，他在两种安排中的玩伴并不相同。这种情形在数学中出现得如此频繁，以至于它有了自己的名字。

定义 2.6 设 \(n\) 为正整数，\(k\le n\) 也是正整数。设 \(\mathcal{B}=\{B_1,B_2,\cdots,B_k\}\)，其中对所有 \(i\in[k]\) 都有 \(B_i\subseteq[n]\)，各 \(B_i\) 非空且两两不相交，并且 \(\bigcup_{i=1}^{k}B_i=[n]\)。那么我们称 \(\mathcal{B}\) 是 \([n]\) 的一个划分（partition），它有 \(k\) 个块（block）。
把定义拆开看“\([n]\) 划分成 \(k\) 个块”同时要满足三件事，缺一不可：
① 每个块 \(B_i\) 都非空（不能有空房间）；
② 任意两个块不相交，\(B_i\cap B_j=\varnothing\)（每个元素只能进一个块）；
③ 所有块的并恰好是整个 \([n]\)（没有元素被漏掉）。
合在一起就是：把 \(\{1,2,\dots,n\}\) 里的每个数恰好分进一个非空小堆里。
[6] = {1,2,3,4,5,6} 135 26 4 B₁={1,3,5} B₂={2,6} B₃={4}
\([6]\) 的一个划分（3 个块）：每个数字落在恰好一个块里，块都非空，三块并起来正好是 \([6]\)。
例 2.7 把 \([4]\) 划分成三个块，一共有六种，即：

注意，块本身是集合，所以每个块内部元素的顺序无关紧要。还要注意，在定义 2.6 中，\(\mathcal{B}\) 本身也是一个集合，所以块与块之间的顺序同样无关紧要。因此，\([4]\) 划分成三个块恰有六种，这并不令人意外。事实上，所有这样的划分都将由一个双元素块和两个单元素块组成，所以一旦我们知道哪些元素落在那个双元素块里，整个划分就被确定了。由于选出这个双元素块共有 \(\binom{4}{2}=6\) 种方式，结论得证。

为什么是“一双 + 两单”把 4 个元素分成 3 个非空块，各块大小之和为 4 且每块至少 1。满足“三个正整数相加为 4”的只有 \(2+1+1\) 这一种（不计顺序）。所以每个划分必然是“一个含 2 个元素的块 + 两个含 1 个元素的块”。确定划分只需确定那个 2 元素块，而它有 \(\binom{4}{2}=6\) 种选法。
{1,2} {3} {4} {1,3} {2} {4} {1,4} {2} {3} {2,3} {1} {4} {2,4} {1} {3} {3,4} {1} {2} 红色为双元素块；选定它（共 \(\binom{4}{2}=6\) 种）划分即定
\([4]\) 划分成三块的全部六种，每张卡片由一个双元素块（红）和两个单元素块（蓝）组成。

让我们通过回答最初的那个问题来练习这类计数。

例 2.8 把 \([5]\) 划分成三个块的方法数是 \(25\)。
把 25 算出来原文只给出了答案 \(25\)，下面我们按照例 2.7 的同一思路把它推演一遍。把 5 个元素分进 3 个非空块，各块大小之和为 \(5\) 且每块至少为 \(1\)。满足“三个正整数相加为 5”的（不计顺序）只有两种大小型：\(3+1+1\) 与 \(2+2+1\)。我们分别数，再相加。
  1. 型 \((3,1,1)\)：一个三元素块 + 两个单元素块。只要选出那 3 个进大块的元素，划分就定了，共 \(\binom{5}{3}=10\) 种。
  2. 型 \((2,2,1)\)：两个双元素块 + 一个单元素块。先选出那个单独的元素，有 \(5\) 种；剩下 4 个元素要分成两个大小为 2 的块。
  3. 把这 4 个元素分成两个 2 元素块：先给其中一个块选 2 个元素，是 \(\binom{4}{2}=6\) 种，但两个块没有先后之分（块之间无序），每种分法被数了 2 次，故实际为 \(\binom{4}{2}/2=3\) 种。于是型 \((2,2,1)\) 共 \(5\times 3=15\) 种。
  4. 两种大小型互不相交，由加法原理相加：\(\;10+15=25\)。♦
型 (3,1,1)：共 10 种 型 (2,2,1)：共 15 种 3 个 1 1 \(\binom{5}{3}=10\) 2 个 2 个 1 \(5\times\binom{4}{2}/2=15\)
把 \([5]\) 拆成三个非空块，只可能是 \((3,1,1)\) 或 \((2,2,1)\) 两种大小型；两类数目相加得 \(10+15=25\)。
回到房间问题因此，五个孩子把无区别的三个房间都用上、不同分法共有 \(25\) 种。如果三个房间被看作互不相同，则要再乘 \(3!=6\)，即 \(25\times 6=150\) 种。这正好呼应了本节开头所说的 \(3!\) 倍关系。

返回 全书目录