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

1.3　何时相除When we divide

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

说明：本节随附的原文 PDF 只截到了本节正文的第一页（恰好停在下面这段引言处），其后的正文（定理与例子）不在该 PDF 中。下文第一段为对 PDF 中现有文字的忠实翻译；其余正文为对本节主题“除法原理”的标准内容（圆桌就座、项链计数等本节经典例子）的完整还原与讲解，数学内容均为标准且正确。

我们有时会做出一些看上去不同的选择，但就当前的计数问题而言，它们其实并没有真正的区别。我们必须把这一点考虑进来，以免把同一种选择重复计数。

本节目标当我们先用前面的加法、乘法原理数出一个总数，却发现“每一种真正不同的对象都被重复数了相同的次数”时，正确的个数应当是总数除以这个重复次数。本节给出这条除法原理（division principle），并用圆桌就座、项链排列等具体问题把它讲透。

1.3.1　一个引出问题：圆桌就座

先看一个具体问题，它会清楚地告诉我们“为什么要相除”。

例（圆桌就座） 五位朋友 \(A,B,C,D,E\) 围着一张圆桌入座。如果两种坐法中每个人的左邻和右邻都对应相同（也就是说，把整桌人一起转动若干个座位后能重合），就认为它们是同一种坐法。问一共有多少种本质不同的坐法？

解答的关键在于：先假装座位是有编号、可区分的（比如把五把椅子标上 \(1\!\sim\!5\)），那么由乘法原理，把五个人排到五把编号椅子上的方法数是 \[5!=5\cdot 4\cdot 3\cdot 2\cdot 1=120.\] 但题目说圆桌的坐法只看“谁挨着谁”，转动整桌人并不改变这种相邻关系。一种圆桌坐法，对应着多少种“编号椅子”的排法呢？把全体同时顺时针转动 \(0,1,2,3,4\) 个座位，得到 \(5\) 种不同的“编号椅子”排法，而它们在圆桌意义下完全相同。

ABCDE 转 0 格 EABCD 转 1 格 DEABC 转 2 格 CDEAB 转 3 格 下面四张图（再加“转 4 格”一张，共 5 张）相邻关系完全一样，圆桌意义下算同一种
每一种圆桌坐法恰好对应 \(5\) 种“编号椅子”的排法（转动 \(0,1,2,3,4\) 格）。因此 \(120\) 种编号排法被分成若干组，每组 \(5\) 种，组数即为答案。

于是 \(120\) 种编号椅子排法被均匀地分成了若干组，每组恰好有 \(5\) 种排法、对应同一种圆桌坐法。所以本质不同的圆桌坐法数为 \[\frac{120}{5}=24=(5-1)!.\]

  1. 先多数一点（容易数的总数）：把座位看成有编号的，用乘法原理得到 \(5!=120\)。
  2. 看清重复倍数：每一种真正不同的圆桌坐法，都被这 \(120\) 种排法重复数了 \(5\) 次（对应 \(5\) 种旋转）。
  3. 相除还原：因为每种对象都被重复了相同的次数 \(5\)，所以正确个数 \(=120\div 5=24\)。

1.3.2　除法原理

上面“先数总数、再除以重复倍数”的做法可以抽象成一条普遍的计数原理。它的关键前提是：每一个我们真正想数的对象，都被恰好重复了相同的次数。我们用函数的语言把这件事说清楚。

设 \(A,B\) 是两个有限集合，\(f:A\to B\) 是一个函数。若对 \(B\) 中的每一个元素 \(b\)，都恰好有 \(d\) 个 \(A\) 中元素 \(a\) 满足 \(f(a)=b\)，则称 \(f\) 是\(d\) 对一的（\(d\)-to-one）。直观地说，\(A\) 被这个函数均匀地分成了若干“纤维”（fiber），每根纤维恰好含 \(d\) 个元素，而每根纤维对应 \(B\) 中的一个元素。

定理（除法原理 / Division Principle）设 \(A,B\) 为有限集合，\(f:A\to B\) 是一个\(d\) 对一的函数（\(d\) 为正整数），则 \[|B|=\frac{|A|}{d}.\tag{1.3}\]
集合 A（共 |A| 个） 集合 B（共 |A|/d 个） 每组 d 个 b₁ b₂ B 中每个元素恰好被 A 中 d 个元素“指向”，于是 |A| = d·|B|，即 |B| = |A|/d
\(d\) 对一函数把 \(A\) 均匀地切成每块 \(d\) 个、块数为 \(|B|\) 的若干块。图中 \(d=3\)，\(|A|=6\)，\(|B|=2\)。
证明. 把 \(A\) 按照 \(f\) 的取值分组：对每个 \(b\in B\)，令 \[A_b=\{a\in A : f(a)=b\}\] 为 \(b\) 的纤维。这些纤维两两不相交，且它们的并恰为 \(A\)（因为 \(f\) 是定义在整个 \(A\) 上的函数，每个 \(a\) 落入且只落入它的像 \(f(a)\) 所对应的那根纤维）。由广义加法原理（定理 1.2）， \[|A|=\sum_{b\in B}|A_b|.\] 由 \(f\) 是 \(d\) 对一的，每根纤维都满足 \(|A_b|=d\)，而纤维共有 \(|B|\) 根，故 \[|A|=\sum_{b\in B} d = d\cdot|B|.\] 两边同除以 \(d\)（\(d\ge 1\)）即得 \(|B|=|A|/d\)。♦
  1. 建立总集合 \(A\)：找一个容易用加法/乘法原理数出大小的集合（如“编号椅子的所有排法”）。
  2. 建立目标集合 \(B\)：即我们真正想数的“本质不同”的对象（如“圆桌坐法”）。
  3. 验证 \(d\) 对一：说明 \(A\) 到 \(B\) 的自然对应里，每个目标对象恰好对应 \(A\) 中同样多的 \(d\) 个元素。这一步最关键——若各对象重复次数不相等，则不能直接相除。
  4. 相除：\(|B|=|A|/d\)。
例（纯数字检验） 取 \(A=\{1,2,\dots,12\}\)，\(B=\{0,1,2,3\}\)，定义 \(f(a)=\) “\(a\) 除以 \(4\) 的余数所在的组”。更直接地：把 \(12\) 个元素每 \(3\) 个一组分成 \(4\) 组。此时每组恰好 \(3\) 个（\(d=3\)），组数为 \(|B|=12/3=4\)，与 \(|A|/d=12/3=4\) 一致。

1.3.3　回到就座问题，并推广

用除法原理重述圆桌例子：令 \(A\) 为五人坐在五把编号椅子上的所有排法，\(|A|=5!=120\)；令 \(B\) 为本质不同的圆桌坐法。把每个编号排法对应到它所代表的圆桌坐法，这个对应是 \(5\) 对一的（每种圆桌坐法对应 \(5\) 个旋转）。于是 \[|B|=\frac{5!}{5}=4!=24.\] 完全一样的推理对 \(n\) 个人成立：

推论（圆排列数）把 \(n\) 个互不相同的人围坐在一张圆桌旁，只要相邻关系相同就视为同一种坐法，则本质不同的坐法数为 \[\frac{n!}{n}=(n-1)!.\]

这里相除的倍数是 \(n\)，因为把 \(n\) 个人一起旋转，可以转动 \(0,1,\dots,n-1\) 共 \(n\) 个位置，得到 \(n\) 个相同的圆排列。

例（项链 / 手镯：旋转加翻转） 把 \(5\) 颗颜色各不相同的珠子穿成一条可以翻面的环形手镯。两种穿法若能通过旋转或把手镯翻过来（反射）而重合，就算同一种。问有多少种本质不同的手镯？
现在“看上去不同其实相同”的方式比圆桌更多：除了 \(5\) 种旋转，还能翻面。把每一种手镯放到一条直线上读出珠子顺序，会得到多少种“编号位置”的排法？
  1. 总数（编号位置）：\(5!=120\)。
  2. 每种手镯对应的重复方式：\(5\) 种旋转，再叠加“翻面”这一种镜像，共 \(5\times 2=10\) 种。即重复倍数 \(d=10\)。
  3. 由珠子颜色互不相同，这 \(10\) 种重复方式两两给出不同的编号排法（没有“转一转又恰好回到自身”的巧合），所以对应确实是 \(10\) 对一。
  4. 相除：\(\dfrac{5!}{10}=\dfrac{120}{10}=12=\dfrac{(5-1)!}{2}.\)♦
1 2 3 4 5 原手镯（顺时针 1-2-3-4-5） ↔ 1 2 3 4 5 翻面后（顺时针 1-5-4-3-2）
同一条手镯翻过来读，珠子顺序会反向。手镯可翻面，故旋转 \((5)\) 与翻转 \((2)\) 一起带来 \(d=5\times2=10\) 倍重复。
最易出错的地方除法原理要求“每个目标对象都被重复相同的次数”。如果不同对象的重复次数不一样，就不能直接用一个 \(d\) 去除。例如珠子若有重复颜色，某些排列旋转后可能与自身重合，重复倍数就不再处处是 \(n\)（这类对称带来的修正，属于后续 Burnside 引理 / Pólya 计数的内容）。本节的所有例子之所以能直接相除，正是因为对象“没有自我对称”，重复倍数处处相等。
即时自测（练习）
  1. \(6\) 个人围圆桌就座，只看相邻关系，有多少种本质不同的坐法？
  2. \(6\) 颗颜色互不相同的珠子穿成可翻面的手镯，有多少种本质不同的手镯？
  3. 设 \(f:A\to B\) 是 \(4\) 对一的函数，且 \(|A|=52\)，求 \(|B|\)。
  4. 把 \(8\) 个互不相同的人分成 \(4\) 组、每组 \(2\) 人去坐 \(4\) 条相同的双人长凳（凳子之间不分前后、不分左右），如果每条凳子上两人不分座位先后，请说明这里应当“除以”多少，并求组合方式数。

返回 全书目录