计数原理

{/* label: chap:ch09 */}

{/* latex-label: fig:lottery-example */} \begin{figure}[htbp]

TikZ 图 114

\end{figure} 图：彩票抽奖示意图：从33个红球中选6个，从16个蓝球中选1个

中头奖究竟有多难？

知乎上有这么个有趣的问题："给你选的话，你想选几百万资产，还是上清华北大？"\footnote{免责声明：给一些没有幽默感的人说句话，如果你不知道的话，这是一个笑话，可能并不好笑，如果你不经常上知乎这个软件平台，自然是不知道的.}我相信每个人的答案不同，但是许多人也为这百万现金有过追求，正如每周开奖的彩票吸引着无数人，每个人都梦想着能选中那组独一无二的幸运号码. 但这种"幸运"究竟有多么渺茫？要精确计算中得头奖的概率，我们必须先回答一个根本问题：从所有可能的号码组合中，到底有多少种不同的组合？

以一种常见的彩票游戏为例：我们需要从33个红色球中选出6个，再从16个蓝色球中选出1个. 这项任务可以分为两步：(1) 挑选红球；(2) 挑选蓝球. 挑选蓝球很简单，有16种选择. 但真正的挑战在于第一步： 从33个红球中不重复地选出6个，一共有多少种选法？ 我们可以尝试去列举吗？(1,2,3,4,5,6), (1,2,3,4,5,7), ... 很快我们就会发现，这是一个不可能完成的任务，其总数将是一个天文数字. 更重要的是，我们只关心选出了哪些号码，而不在乎它们被摇出的先后顺序. 选出 05, 08, 13, 21, 27, 32 和选出 32, 21, 13, 08, 27, 05 是完全一样的结果.

这种"只选不排"的问题，向我们提出了对一种全新数学工具的需求. 我们需要发展出一套强大的理论，能够系统地、精确地计算出在各种限制条件下"有多少种方法"，无论是需要考虑顺序的排列问题，还是不需要考虑顺序的组合问题. 这就是本章将要探索的计数原理.

加法原理与乘法原理

{/* label: sec:ch09-s01 */}

要解开彩票组合的谜题，乃至处理更复杂的计数问题，我们必须从两个最基本、最核心的原理出发：加法原理 与 乘法原理. 这两个原理就像是计数世界的公理，它们听起来可能像是小学生都会的样子，但其力量在于它们能够被灵活地组合运用，以解决看似极其复杂的问题.

加法原理

想象一下，你从北京要去上海，可以选择乘坐高铁（有3个不同的车次），也可以选择乘坐飞机（有5个不同的航班）. 那么，你一共有多少种选择？

这个问题非常直观. 乘坐高铁和乘坐飞机是两种截然不同的选择，它们是互斥的. 你选择了高铁的某个车次，就不可能再选择任何一个飞机航班. 因此，你的总选择数就是把这两类选择简单相加. 这就是加法原理的精髓.

加法原理

如果完成一件事有 $k$ 类方法, 这些方法是相互独立的, 且任何一类方法中的任何一种方法都能独立地完成任务. 在第一类方法中有 $m_1$ 种不同的途径, 在第二类方法中有 $m_2$ 种不同的途径, ..., 在第 $k$ 类方法中有 $m_k$ 种不同的途径，那么完成这件事共有 <MathBlock raw={"N = m_1 + m_2 + ... + m_k"} /> 种不同的方法.

加法原理的核心在于**“分类”**. 当一个问题可以被分解为几个互不相干、彼此独立的情况时，总数就是各种情况之和. 在上面的例子中，“乘坐高铁”是一类，“乘坐飞机”是另一类. 总的选择数就是 $3+5=8$ 种.

从集合论的观点看，如果 $A_i$ 代表第 $i$ 类方法的集合, 那么这些集合两两不交, 即 $A_i \cap A_j = \emptyset$ for $i \neq j$. 完成任务的总方法数就是这些集合的并集的大小： <MathBlock raw={"|A_1 \cup A_2 \cup ... \cup A_k| = |A_1| + |A_2| + ... + |A_k|"} />

现在我们看一些加法原理的有趣应用：

例

某大学的课程目录中，数学系开设了5门不同的选修课，计算机系开设了3门不同的选修课.一名学生希望从中选择一门课来学习，他有多少种不同的选择？

解

这个问题是加法原理最直接的应用.学生的目标是“选择一门课”. 我们可以将所有可选的课程分为两类： 第一类：选择数学系的课程，有 $5$ 种方法. 第二类：选择计算机系的课程，有 $3$ 种方法.

由于一个学生不能同时选择数学课和计算机课来满足“选择一门课”这个目标（即这两类选择是互斥的），因此总的选择数是两类方法数之和. <MathBlock raw={"N = 5 + 3 = 8"} /> 所以，该学生共有8种不同的选择.

例

使用字母 $\{A, B, C\}$ 和数字 $\{1, 2\}$，可以构成多少个长度为1或长度为2的密码？密码中的字符不能重复.

解

完成“构成一个密码”这件事，可以根据密码的长度分为两种截然不同的情况.

第一类：密码长度为1. 我们可以从5个可用字符 $(\{A, B, C, 1, 2\})$ 中任选一个. 因此，有 $5$ 种方法.

第二类：密码长度为2，且字符不重复. 这是一个分步过程： 第一步：为密码的第一个位置选择一个字符，有 $5$ 种选择. 第二步：为第二个位置选择一个字符，由于不能重复，只剩下 $4$ 种选择. 根据乘法原理，长度为2的密码共有 $5 \times 4 = 20$ 个.

因为一个密码的长度不可能既是1又是2，所以这两类情况是互斥的.根据加法原理，总的密码个数是 <MathBlock raw={"N = 5 + 20 = 25"} /> 所以，总共可以构成25个这样的密码.

斐波那契数列

要登上一个有10级台阶的楼梯，如果每次只能上1级或2级，总共有多少种不同的登法？

解

这是一个经典问题，直接列举所有情况会非常困难.我们不妨用 $f(n)$ 表示登上 $n$ 级台阶的方法数.我们要求的便是 $f(10)$.

考虑我们是如何踏上第 $n$ 级台阶的.这最后的一步，只有两种可能： 第一类：从第 $n-1$ 级台阶一步跨上来.要实现这种情况, 我们必须先到达第 $n-1$ 级, 这有 $f(n-1)$ 种方法. 第二类：从第 $n-2$ 级台阶两步跨上来.要实现这种情况, 我们必须先到达第 $n-2$ 级, 这有 $f(n-2)$ 种方法.

这两种情况是互斥的，因为我们最后一步的出发点（是 $n-1$ 还是 $n-2$）是唯一的.因此，根据加法原理，我们得到了一个递推关系： <MathBlock raw={"f(n) = f(n-1) + f(n-2)"} /> 为了使用这个关系，我们需要初始条件. 对于1级台阶，只有一种方法：$f(1) = 1$. 对于2级台阶，有两种方法（1-1 或 2）：$f(2) = 2$.

现在我们可以依次计算： $f(3) = f(2) + f(1) = 2 + 1 = 3$ $f(4) = f(3) + f(2) = 3 + 2 = 5$ $f(5) = 5 + 3 = 8$ $f(6) = 8 + 5 = 13$ $f(7) = 13 + 8 = 21$ $f(8) = 21 + 13 = 34$ $f(9) = 34 + 21 = 55$ $f(10) = 55 + 34 = 89$

所以，总共有89种不同的登法.

这个例子深刻地揭示了加法原理如何成为构建递归思想的基石.我们将一个大问题分解为几个互斥的、结构相同的子问题，并通过相加它们的解来得到原问题的解.序列 $1, 2, 3, 5, 8, ...$ 是著名的斐波那契数列的一个变体.

例

在一个平面直角坐标系中，一个质点从原点 $(0,0)$ 出发, 每次只能向上（y坐标+1）或向右（x坐标+1）移动一个单位.问该质点到达点 $(3,2)$ 有多少条不同的路径？

解

令 $P(m, n)$ 表示从 $(0,0)$ 到达点 $(m,n)$ 的路径数.我们要计算的是 $P(3,2)$.

与上一个例子类似，我们考虑质点是如何到达终点 $(m,n)$ 的.其最后一步移动必然是以下两种互斥情况之一： 第一类：从点 $(m-1, n)$ 向右移动一步到达.到达 $(m-1, n)$ 的路径数为 $P(m-1, n)$. 第二类：从点 $(m, n-1)$ 向上移动一步到达.到达 $(m, n-1)$ 的路径数为 $P(m, n-1)$.

根据加法原理，我们得到递推关系： <MathBlock raw={"P(m, n) = P(m-1, n) + P(m, n-1)"} /> 边界条件是显而易见的：从 $(0,0)$ 到达x轴上的任意点 $(m,0)$ 只有一条路径（一直向右）, 即 $P(m, 0) = 1$. 同理, 到达y轴上的任意点 $(0,n)$ 也只有一条路径（一直向上）, 即 $P(0, n) = 1$.

我们可以通过构建一个表格或直接计算来求解： $P(1,0) = 1$, $P(0,1) = 1$ $P(1,1) = P(0,1) + P(1,0) = 1 + 1 = 2$ $P(2,0) = 1$, $P(0,2) = 1$ $P(2,1) = P(1,1) + P(2,0) = 2 + 1 = 3$ $P(1,2) = P(0,2) + P(1,1) = 1 + 2 = 3$

最后，我们计算目标点： <MathBlock raw={"P(3,2) = P(2,2) + P(3,1)"} /> 我们需要先计算 $P(2,2)$ 和 $P(3,1)$. $P(2,2) = P(1,2) + P(2,1) = 3 + 3 = 6$ $P(3,1) = P(2,1) + P(3,0) = 3 + 1 = 4$ 所以，$P(3,2) = 6 + 4 = 10$.

因此，共有10条不同的路径.

例

正整数 $N=180$ 的所有正因数中, 有多少个是 $6$ 的倍数或者是 $10$ 的倍数？

解

首先，对 $N$ 进行素数分解：$N = 180 = 18 \times 10 = 2 \times 9 \times 2 \times 5 = 2^2 \cdot 3^2 \cdot 5^1$. $N$ 的任意一个正因数 $d$ 都可以表示为 $d = 2^a \cdot 3^b \cdot 5^c$, 其中 $0 \le a \le 2$, $0 \le b \le 2$, $0 \le c \le 1$.

这个问题看似应该使用容斥原理，因为一个数可能既是6的倍数也是10的倍数.但是，我们可以通过更精细的分类来利用加法原理.我们将目标因数分为两类：

第一类：是 $6$ 的倍数. 一个因数是 $6=2 \cdot 3$ 的倍数, 意味着它的素因子分解中, 2的指数至少为1, 3的指数也至少为1.即 $a \ge 1$ 且 $b \ge 1$. 所以，对于这样的因数 $d = 2^a \cdot 3^b \cdot 5^c$： $a$ 的选择有 $\{1, 2\}$, 共 $2$ 种. $b$ 的选择有 $\{1, 2\}$, 共 $2$ 种. $c$ 的选择有 $\{0, 1\}$, 共 $2$ 种. 根据乘法原理，这类因数共有 $2 \times 2 \times 2 = 8$ 个.

第二类：是 $10$ 的倍数, 但不是 $6$ 的倍数. 一个因数是 $10=2 \cdot 5$ 的倍数, 意味着 $a \ge 1$ 且 $c \ge 1$. 同时，它不是 $6$ 的倍数, 意味着 “$a \ge 1$ 且 $b \ge 1$” 这个条件不成立. 因为我们已经要求 $a \ge 1$, 所以为了使它不是6的倍数, 必须有 $b \< 1$, 即 $b=0$. 所以，对于这类因数 $d = 2^a \cdot 3^b \cdot 5^c$： $a$ 的选择有 $\{1, 2\}$, 共 $2$ 种. $b$ 的选择必须是 $\{0\}$, 共 $1$ 种. $c$ 的选择必须是 $\{1\}$, 共 $1$ 种. 根据乘法原理，这类因数共有 $2 \times 1 \times 1 = 2$ 个.

这两类因数集合的定义是互斥的（一个是6的倍数，另一个不是6的倍数）.因此，根据加法原理，满足条件的因数总数为 <MathBlock raw={"N = 8 + 2 = 10"} /> 所以，共有10个这样的因数.

通过精巧地定义分类标准（$A$ 和 $B \setminus A$），我们将一个潜在的容斥原理问题转化为了纯粹的加法原理问题，这展示了在计数中“如何分类”本身就是一门艺术.

乘法原理

现在考虑一个不同的场景. 假设你正在为一次晚宴搭配服装. 你有3件不同的衬衫和4条不同的裤子. 你有多少种不同的搭配方式？

为了完成“搭配一套服装”这个任务，你必须依次完成两个步骤：第一步，选择一件衬衫；第二步，选择一条裤子. 你在第一步的选择（例如，选择了白色衬衫）并不会影响你在第二步的选择数量（你仍然有4条裤子可选）. 对于你选择的每一件衬衫，都有4条裤子与之搭配. 因为你有3件衬衫，所以总的搭配方式就是将每一步的选择数相乘. 这就是乘法原理.

乘法原理

如果完成一件事需要分成 $k$ 个步骤, 完成第一个步骤有 $m_1$ 种不同的方法, 完成第二个步骤有 $m_2$ 种不同的方法, ..., 完成第 $k$ 个步骤有 $m_k$ 种不同的方法，那么完成这件事共有 <MathBlock raw={"N = m_1 \times m_2 \times ... \times m_k"} /> 种不同的方法.

从集合论的观点看，乘法原理是笛卡尔积的大小 基数的直接体现.为了严谨地理解这一点，我们首先需要引入有序对和笛卡尔积的概念.

一个有序对 $(a, b)$ 是由两个元素组成的集合, 但与普通集合 $\{a, b\}$ 不同, 它规定了元素的次序.也就是说, 除非 $a=b$, 否则 $(a, b) \neq (b, a)$. 这正是“分步”思想的数学抽象：第一步的选择是第一个元素，第二步的选择是第二个元素，其顺序至关重要.

笛卡尔积

设 $A$ 和 $B$ 为两个集合, 它们的笛卡尔积, 记作 $A \times B$ (读作“A cross B”), 是所有可能的有序对 $(a, b)$ 的集合, 其中 $a \in A$ 且 $b \in B$. 用集合符号表示为： <MathBlock raw={"A \times B = \{ (a, b) \mid a \in A, b \in B \}"} /> 这个概念可以推广到任意 $k$ 个集合. 设 $A_1, A_2, ..., A_k$ 为 $k$ 个集合, 它们的笛卡尔积是所有可能的有序 $k$-元组 $(a_1, a_2, ..., a_k)$ 的集合, 其中对任意 $i=1, 2, ..., k$, 都有 $a_i \in A_i$. <MathBlock raw={"A_1 \times A_2 \times ... \times A_k = \{ (a_1, a_2, ..., a_k) \mid a_i \in A_i \text{ 对于 } i=1, ..., k \}"} />

笛卡尔积的大小，即其元素的个数，恰好就是乘法原理给出的结果.如果这些集合都是有限集，那么 <MathBlock raw={"|A_1 \times A_2 \times ... \times A_k| = |A_1| \times |A_2| \times ... \times |A_k| = \prod_{i=1}^{k} |A_i|"} /> 这个定义完美地将“分步完成任务”这一直观操作数学化了.每一个步骤对应于从一个集合中进行一次选择，而整个任务的所有可能结果，则构成了一个笛卡尔积.

让我们回到服装搭配的问题.如果衬衫的集合是 $S=\{s_1, s_2, s_3\}$, 裤子的集合是 $P=\{p_1, p_2, p_3, p_4\}$, 那么一套搭配就是一个有序对 $(s, p)$, 其中 $s \in S, p \in P$. 所有可能的搭配构成了集合 $S \times P$，其大小为 <MathBlock raw={"|S \times P| = |S| \times |P| = 3 \times 4 = 12"} />

尽管我们并不要求你掌握这个概念，不过相应地，我们可以给出一些有趣的应用，让读者看看其用处：

例

一家餐厅的午市套餐允许顾客从2种汤（$T=\{\text{罗宋汤}, \text{奶油蘑菇汤}\}$）中选择一种, 并从3种主菜（$M=\{\text{牛排}, \text{意面}, \text{披萨}\}$）中选择一种.请问共有多少种不同的套餐组合？并写出这个组合集合.

解

每一种套餐组合都可以被视为一个有序对 $(\text{汤}, \text{主菜})$. 所有可能的套餐组合构成的集合，正是汤的集合 $T$ 与主菜的集合 $M$ 的笛卡尔积 $T \times M$.

其大小为： <MathBlock raw={"|T \times M| = |T| \times |M| = 2 \times 3 = 6"} /> 这个集合的具体内容是： <MathBlock raw={"\begin{aligned} T \times M = \{ &(\text{罗宋汤}, \text{牛排}), (\text{罗宋汤}, \text{意面}), (\text{罗宋汤}, \text{披萨}), &(\text{奶油蘑菇汤}, \text{牛排}), (\text{奶油蘑菇汤}, \text{意面}), (\text{奶油蘑菇汤}, \text{披萨}) \} \end{aligned}"} /> 共有6种不同的套餐组合.

例

组装一台电脑，CPU有2种选择（$C=\{\text{Intel}, \text{AMD}\}$）, 内存有3种选择（$R=\{\text{8GB}, \text{16GB}, \text{32GB}\}$）, 硬盘有2种选择（$H=\{\text{1TB SSD}, \text{2TB SSD}\}$）, 并且显卡也有3种选择（$G=\{\text{GPU-A}, \text{GPU-B}, \text{GPU-C}\}$）.一种完整的配置方案由CPU、内存、硬盘、显卡各选一种构成.请问有多少种不同的配置方案？

解

每一种配置方案都可以被视为一个有序四元组 $(\text{cpu}, \text{ram}, \text{hdd}, \text{gpu})$. 所有可能的配置方案集合是这四个选择集合的笛卡尔积 $C \times R \times H \times G$.

根据笛卡尔积的基数公式，总的方案数是： <MathBlock raw={"|C \times R \times H \times G| = |C| \times |R| \times |H| \times |G| = 2 \times 3 \times 2 \times 3 = 36"} /> 所以，共有36种不同的电脑配置方案.

原理的辨析与应用

区分加法原理和乘法原理是解决计数问题的关键第一步. 一个简单的判断方法是：

• 加法原理关注“分类”：完成任务的各种方式是平行的，选择其中任何一种方式都能完成任务. 关键词是“或者”.
• 乘法原理关注“分步”：完成任务需要经历所有步骤，一步都不能少. 关键词是“并且”.

\begin{table}[htbp]

\caption{加法原理与乘法原理的比较}

\begin{tabularx}{\textwidth}{>{\raggedright\arraybackslash}p{2.5cm} >{\raggedright\arraybackslash}X >{\raggedright\arraybackslash}X}

**比较维度** & **加法原理** & **乘法原理** 
核心思想 & **分类讨论**：完成任务有若干类彼此独立的方法. & **分步完成**：完成任务需要经过若干个连续进行的步骤. 
关键词 & “或者”、“任选其一”、“情况一、情况二...”、“分为几类” & “并且”、“依次”、“接着”、“每一个...都...” 
任务关系 & 各类方法**相互排斥**.选择任何一类中的一种方法，任务即告完成. & 各个步骤**相互依存**.必须完成所有步骤，任务才算完成. 
判断准则 & 完成任务的方式是“**择一即可**”. & 完成任务的步骤是“**缺一不可**”. 
集合模型 & **不交并集**：$|A_1 \cup ... \cup A_k| = \sum_{i=1}^{k} |A_i|$, 其中 $A_i \cap A_j = \emptyset$ 对所有 $i \neq j$. & **笛卡尔积**：$|A_1 \times ... \times A_k| = \prod_{i=1}^{k} |A_i|$. 
经典比喻 & 从北京到上海，可以坐火车**或**飞机. & 搭配一套服装，需要选上衣**和**裤子. 

\end{tabularx} \end{table}

在更复杂的问题中，这两个原理往往需要结合使用. 我们通过一个经典的例子来体会这一点.

例

求在所有三位正整数中，至少含有一个数字“7”的数有多少个？

解

直接去计算“至少含有一个7”的数字个数，情况会比较复杂. 我们需要分类讨论：恰好含有一个“7”、恰好含有两个“7”、恰好含有三个“7”. 这是一个可行的思路，但过程繁琐且容易出错. 让我们换一个角度，这正是组合思维的魅力所在.

我们可以先计算它的反面：一个“7”都没有的三位正整数有多少个.

首先，总的三位正整数的个数是多少？ 这是一个分步过程：确定百位、十位、个位. 百位不能为0，所以有 $9$ 种选择（从1到9）. 十位和个位可以是0到9中的任意数字，各有 $10$ 种选择. 根据乘法原理，总共有 <MathBlock raw={"9 \times 10 \times 10 = 900"} /> 个三位正整数.

现在，我们计算**不含数字“7”**的三位数的个数. 这同样是一个分步过程. 百位不能是0且不能是7，所以有 $8$ 种选择（1,2,3,4,5,6,8,9）. 十位和个位都不能是7，所以各有 $9$ 种选择（0,1,2,3,4,5,6,8,9）. 根据乘法原理，不含数字“7”的三位数共有 <MathBlock raw={"8 \times 9 \times 9 = 648"} /> 个.

我们已经将所有三位数分成了两类：“至少含有一个7”的和“一个7也没有”的. 这两类是互斥的，它们的总和就是全部三位数的个数. 因此，根据加法原理的变形（也称为补集原理或容斥原理的最简单形式），我们得到 <MathBlock raw={"(\text{至少含有一个7的个数}) = (\text{总个数}) - (\text{一个7也没有的个数})"} /> <MathBlock raw={"N = 900 - 648 = 252"} /> 所以，至少含有一个数字“7”的三位正整数共有252个.

通过解决这个问题的“反面”，我们巧妙地避开了复杂的分类讨论，将一个需要同时使用加法和乘法原理的复杂问题，转化为了两次简单的乘法原理应用和一次减法. 这种“正难则反”的策略是组合数学中一个非常强大和常用的思想.

接着我们来看一些关于乘法原理的有趣应用：

例

令集合 $A = \{a_1, a_2, a_3\}$ 且 $B = \{1, 2, 3, 4, 5\}$. 从集合 $A$ 到集合 $B$ 可以定义多少个不同的函数 $f: A \to B$?

解

定义一个函数 $f: A \to B$ 的任务, 是为 $A$ 中的每一个元素, 在 $B$ 中指定唯一一个与之对应的元素（称为它的“像”）. 我们可以将这个任务分解为三个连续的步骤：

第一步：为元素 $a_1$ 选择一个像. $f(a_1)$ 可以是集合 $B$ 中的任意一个元素, 因此有 $5$ 种选择.

第二步：为元素 $a_2$ 选择一个像. 对 $a_2$ 的选择与对 $a_1$ 的选择是相互独立的.$f(a_2)$ 同样可以是 $B$ 中的任意一个元素, 因此也有 $5$ 种选择.

第三步：为元素 $a_3$ 选择一个像. 同理，为 $f(a_3)$ 也有 $5$ 种选择.

根据乘法原理，要完成这全部三个步骤，总的方法数是每一步方法数的乘积. <MathBlock raw={"N = 5 \times 5 \times 5 = 5^3 = 125"} /> 所以，总共可以定义125个不同的函数.

此例揭示了一个普遍结论：从一个包含 $m$ 个元素的集合到一个包含 $n$ 个元素的集合, 可以定义 $n^m$ 个不同的函数.

例

在一场田径比赛的决赛中，共有8名选手.假设没有并列名次，那么总共有多少种可能的最终排名？

解

确定最终排名的任务，等价于为第1名到第8名这8个位置，分别安排一位选手.这是一个典型的分步过程.

第一步：确定第1名. 有 $8$ 位选手都可能获得冠军, 因此有 $8$ 种选择.

第二步：确定第2名. 当第1名确定后，只剩下 $7$ 位选手可以竞争第2名, 因此有 $7$ 种选择.

第三步：确定第3名. 剩下 $6$ 位选手, 有 $6$ 种选择.

...

第八步：确定第8名. 此时只剩下最后一位选手，别无选择，只有 $1$ 种选择.

根据乘法原理，所有可能的排名总数为： <MathBlock raw={"N = 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 40320"} /> 这个连乘积在数学中非常重要，我们用一个专门的符号阶乘 来表示它，记作 $8!$.

将 $n$ 个不同的物体进行全排列, 其方法数恰好是 $n! = n \times (n-1) \times ... \times 1$. 阶乘是乘法原理最直接、最重要的推论之一，也是后续学习排列组合的基石.

例

求正整数 $N=720$ 的所有正因数的个数.

解

直接去寻找并列举720的每一个因数是繁琐且容易遗漏的.我们可以利用算术基本定理，从其素数分解的结构入手. 首先，对 $N=720$ 进行素数分解： <MathBlock raw={"720 = 72 \times 10 = (8 \times 9) \times (2 \times 5) = (2^3 \times 3^2) \times (2 \times 5) = 2^4 \cdot 3^2 \cdot 5^1"} /> 根据算术基本定理，720的任何一个正因数 $d$ 都必须具有 $2^a \cdot 3^b \cdot 5^c$ 的形式. 其中，各素数的指数必须满足限制条件：$0 \le a \le 4$, $0 \le b \le 2$, $0 \le c \le 1$.

因此，构造一个720的正因数，就相当于分三步来确定指数 $a, b, c$ 的值. 第一步：选择指数 $a$ 的值. $a$ 可以是 $0, 1, 2, 3, 4$ 中的任意一个, 共有 $4+1=5$ 种选择.

第二步：选择指数 $b$ 的值. $b$ 可以是 $0, 1, 2$ 中的任意一个, 共有 $2+1=3$ 种选择.

第三步：选择指数 $c$ 的值. $c$ 可以是 $0, 1$ 中的任意一个, 共有 $1+1=2$ 种选择.

根据乘法原理，正因数的总个数为： <MathBlock raw={"\tau(720) = (4+1) \times (2+1) \times (1+1) = 5 \times 3 \times 2 = 30"} /> 所以，720共有30个正因数.

这个方法具有普适性.对于任意正整数 $N = p_1^{a_1} p_2^{a_2} ... p_k^{a_k}$, 其正因数的个数为 $\tau(N) = (a_1+1)(a_2+1)...(a_k+1)$.这是乘法原理在数论中的一个经典且优美的应用.

路径着色

有4个排成一排的方格，现在用5种不同的颜色对其进行染色，要求相邻的方格颜色不能相同.问有多少种不同的染色方法？

解

我们将4个方格从左到右依次编号为1, 2, 3, 4.为它们染色是一个分步决策的过程.

第一步：为第1个方格染色. 没有任何限制，我们可以从5种颜色中任选一种，有 $5$ 种方法.

第二步：为第2个方格染色. 它的颜色必须与第1个方格不同.无论第1个方格选择了哪种颜色，都只排除了1种可能性，因此第2个方格总是有 $5-1=4$ 种颜色可选.

第三步：为第3个方格染色. 它的颜色只需要与第2个方格不同.同样，无论第2个方格选择了什么颜色，第3个方格总是有 $4$ 种选择.

第四步：为第4个方格染色. 它的颜色只需要与第3个方格不同，因此也有 $4$ 种选择.

根据乘法原理，总的染色方法数为： <MathBlock raw={"N = 5 \times 4 \times 4 \times 4 = 5 \times 4^3 = 320"} /> 所以，共有320种不同的染色方法.

这个问题的关键在于，每一步选择的数量是固定的，不受前一步具体选择的影响（例如，无论第1格是红色还是蓝色，第2格都剩下4种选择）.如果问题的限制条件更为复杂，例如“首尾方格颜色不同”，则可能需要更精细的分类讨论，即加法与乘法原理的结合.

集合的子集个数

一个包含 $n$ 个不同元素的有限集合 $S$, 共有多少个不同的子集？（子集包括空集 $\emptyset$ 和集合 $S$ 本身）

解

这个问题有一个非常著名的答案，但其最优雅的证明之一恰恰是基于乘法原理.关键在于转变我们的思考角度.

传统的想法是去“挑选”元素组成子集：挑选0个元素的子集，挑选1个元素的子集，...，然后用加法原理求和.这是一个有效但更复杂的方法，我们将在后面学习组合数时再讨论它.

现在，我们换一个角度：对于集合 $S$ 中的每一个元素，我们来为它做一个决定. 设 $S = \{s_1, s_2, ..., s_n\}$. 为了构造一个子集 $A \subseteq S$, 我们依次对 $S$ 中的每个元素进行决策：

第一步：决策元素 $s_1$. $s_1$ 是否属于子集 $A$？我们有两个选择：“是” 或 “否”.

第二步：决策元素 $s_2$. $s_2$ 是否属于子集 $A$？同样, 我们有两个选择：“是” 或 “否”.这个决策与对 $s_1$ 的决策无关.

...

第 $n$ 步：决策元素 $s_n$. $s_n$ 是否属于子集 $A$？我们仍然有两个选择：“是” 或 “否”.

当我们完成了对所有 $n$ 个元素的决策后, 一个确定的子集就被唯一地构造出来了.例如, 如果对所有元素都选择“否”, 我们就得到了空集 $\emptyset$；如果都选择“是”, 就得到了集合 $S$ 本身.

根据乘法原理，完成这 $n$ 个独立的、各有2种选择的决策，总的方法数为： <MathBlock raw={"N = \underbrace{2 \times 2 \times ... \times 2}_{n \text{次}} = 2^n"} /> 所以，一个包含 $n$ 个元素的集合, 其子集的个数为 $2^n$.

这个证明是组合思想的典范.它通过将“从整体中挑选一部分”的观点，转变为“对每个个体进行独立决策”，从而将一个看似复杂的分类求和问题（加法原理）转化为了一个极其简洁的连续决策问题（乘法原理）.这种思维的跃迁是解决许多高级计数问题的关键.

组合与排列

{/* label: sec:ch09-s02 */}

在上一节中，我们建立了计数理论的两块基石：加法原理与乘法原理.现在，我们将运用这些原理来打造两个功能强大的专用工具：组合 与 排列.这两个概念是解决绝大多数计数问题的核心.

让我们回到本章开头提出的彩票问题： 从33个红球中不重复地选出6个，一共有多少种选法？ 这个问题的本质在于，我们只关心选出了哪些号码，而根本不在乎它们的先后顺序.选出集合 $\{5, 8, 13, 21, 27, 32\}$ 与选出集合 $\{32, 27, 21, 13, 8, 5\}$ 是完全等价的.这种“只选不排”的问题，正是“组合”所要研究的对象.

组合

组合

从 $n$ 个不同的元素中, 不计顺序地选取 $k$ 个元素组成一个子集, 称为一个从 $n$ 个元素中取出 $k$ 个元素的组合.所有不同组合的个数, 称为组合数, 记作 $C(n,k)$ 或更常用的 $\binom{n}{k}$ (读作“从$n$中选$k$个”).

关于组合数的记号

组合数在不同的教材和领域中有多种常见的记法，例如 $C(n,k)$, $C_n^k$, 甚至 $C_k^n$. 它们都表示同一个数学概念.

在本书中，我们主要采用国际通用的二项式系数 记法： <MathBlock raw={"\binom{n}{k}"} /> 这个符号读作““从$n$中选$k$个””，为了确保清晰，请记住它们之间的恒等关系： <MathBlock raw={"\binom{n}{k} \equiv C(n,k) \equiv C_n^k"} />

\textcolor{red}{本书出于方便录入手写数学公式的考虑，将统一使用 $\binom{n}{k}$ 这一表达方式，希望读者能尽快熟悉并掌握它.尽管在考试的时候，我们推荐采用课本上的主流写法.}

我们如何计算 $\binom{n}{k}$ 呢？直接计数非常困难, 但我们可以借助乘法原理, 通过一个巧妙的“思想实验”来推导它.让我们以彩票问题为例, 来计算 $\binom{33}{6}$.

思想实验：如果我们“假装”顺序是重要的，会发生什么？ 想象我们不是从袋子里一次性抓出6个球，而是一个接一个地、按顺序地取出6个球.根据乘法原理，总的“有序”选法有多少种呢？

• 第一个球有 $33$ 种选择；
• 第二个球有 $32$ 种选择；
• ...
• 第六个球有 $33-6+1=28$ 种选择.

所以，有序的选法总数为 $33 \times 32 \times 31 \times 30 \times 29 \times 28$.

现在，让我们回到“顺序不重要”的现实.考虑一个具体的组合，例如集合 $\{1, 2, 3, 4, 5, 6\}$. 在我们刚才的“有序”计数中，这个单一的组合被我们重复计算了多少次？ 它对应于所有这6个数字的全排列：$(1,2,3,4,5,6), (1,2,3,4,6,5), ..., (6,5,4,3,2,1)$. 这6个数字的全排列数，根据乘法原理，是 $6 \times 5 \times 4 \times 3 \times 2 \times 1 = 6!$ (6的阶乘).

这正是问题的关键所在：我们计算出的“有序”选法总数，将每一个我们真正想要的“无序”组合，都重复计数了 $6!$ 次.因此，为了得到正确的组合数，我们必须用有序选法总数除以这个重复的倍数. <MathBlock raw={"\binom{33}{6} = \frac{33 \times 32 \times 31 \times 30 \times 29 \times 28}{6 \times 5 \times 4 \times 3 \times 2 \times 1}"} />

这个逻辑可以推广到一般情况.从 $n$ 个元素中按顺序选出 $k$ 个, 有 $n(n-1)\cdots(n-k+1)$ 种方法.而这 $k$ 个被选出的元素自身的全排列数为 $k!$. 每一个组合都对应着 $k!$ 个有序的选法.因此，我们得到了组合数的计算公式.

组合数公式

从 $n$ 个不同元素中取出 $k$ 个元素的组合数 ($0 \le k \le n$) 为 <MathBlock raw={"\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!} = \frac{n!}{k!(n-k)!}"} /> 其中 $n!$ 表示 $n$ 的阶乘, $n! = n \times (n-1) \times ... \times 1$. 特别地, 我们定义 $0! = 1$.

证明

我们采用一种经典的组合论证方法，即“双重计数”.其思想是：对同一个计数问题，用两种不同的方法进行计算，由于我们计算的是同一个量，因此得到的结果必然相等.通过建立这个等式，我们就能解出未知的量.

我们要计数的对象是：从一个包含 $n$ 个不同元素的集合 $S$ 中, 选出 $k$ 个元素并按一定顺序排列的所有方法的总数, 即排列数 $P(n,k)$.

法一：直接使用乘法原理计算排列数.

我们可以把构造一个 $k$-排列看作是填充 $k$ 个有序的位置.

• 为第一个位置选择一个元素，有 $n$ 种选择.

• 为第二个位置选择一个元素，由于元素不能重复，剩下 $n-1$ 种选择.

• ...

• 为第 $k$ 个位置选择一个元素, 剩下 $n-(k-1) = n-k+1$ 种选择.

  根据乘法原理，总的排列数是这些选择数的乘积： <MathBlock raw={"P(n,k) = n(n-1)\cdots(n-k+1)"} /> 为了将其表达为更紧凑的阶乘形式，我们在分子和分母上同乘以 $(n-k)!$: <MathBlock raw={"P(n,k) = \frac{n(n-1)\cdots(n-k+1) \cdot (n-k)!}{(n-k)!} = \frac{n!}{(n-k)!}"} />

  法二：通过组合数间接计算排列数.

  我们也可以将构造一个 $k$-排列的任务分解为两个连续的步骤：

1. 选择元素 (组合)： 首先，从 $n$ 个元素中不计顺序地选出 $k$ 个元素.根据定义, 完成这一步的方法数正是我们要计算的组合数 $\binom{n}{k}$.
2. 安排顺序 (全排列)： 接着，将这已经选出的 $k$ 个元素进行全排列.这有 $k!$ 种方法.

根据乘法原理，完成这两个步骤的总方法数是 $\binom{n}{k} \times k!$.

由于两种方法计算的是同一个量 $P(n,k)$，因此它们的结果必须相等： <MathBlock raw={"\binom{n}{k} \times k! = P(n,k) = \frac{n!}{(n-k)!}"} /> 现在，我们两边同除以 $k!$ (由于 $k \ge 0$, $k! \ge 1$, 所以可以安全地相除), 即可解出 $\binom{n}{k}$: <MathBlock raw={"\binom{n}{k} = \frac{n!}{k!(n-k)!}"} /> 将 $P(n,k)$ 的另一种形式代入等式 $\binom{n}{k} \times k! = n(n-1)\cdots(n-k+1)$，我们可以得到公式的另一种常用形式： <MathBlock raw={"\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!}"} /> 这就完成了证明.特别地，当 $k=0$ 时, 我们选出空集, 只有一种方法.公式给出 $\binom{n}{0} = \frac{n!}{0!(n-0)!} = \frac{n!}{1 \cdot n!} = 1$, 与事实相符, 这也体现了定义 $0!=1$ 的合理性.

现在，我们可以回答彩票问题了. <MathBlock raw={"\binom{33}{6} = \frac{33 \times 32 \times 31 \times 30 \times 29 \times 28}{6 \times 5 \times 4 \times 3 \times 2 \times 1} = 1,107,568"} /> 挑选红球的方法数超过了一百万种！而这仅仅是中头奖的第一步.

排列

理解了组合之后，排列就变得非常自然.排列不仅关心选出了哪些元素，还关心这些元素被排成的顺序.

排列

从 $n$ 个不同的元素中, 选取 $k$ 个元素并按照一定的顺序排成一列, 称为一个从 $n$ 个元素中取出 $k$ 个元素的排列.所有不同排列的个数, 称为排列数, 记作 $P(n,k)$ 或 $P_n^k$ 或 $A_n^k$.

如何计算排列数 $A(n,k)$ 呢？我们可以把“完成一次排列”这个任务，看作是应用乘法原理的两个步骤：

1. 第一步：选材. 从 $n$ 个元素中, 先“选出”要参与排列的 $k$ 个元素.根据我们刚刚学到的知识, 这一步有 $\binom{n}{k}$ 种方法.
2. 第二步：排序. 将这选出的 $k$ 个元素进行全排列.根据乘法原理, 这一步有 $k!$ 种方法.

因为必须完成所有步骤，任务才算完成，所以根据乘法原理，我们得到排列数与组合数之间的一个至关重要的关系： <MathBlock raw={"A(n,k) = \binom{n}{k} \times k!"} /> 这个关系式深刻地揭示了排列和组合的内在联系：一个排列，本质上就是一个组合再加上对所选元素的排序.

将组合数的公式代入，我们就能得到排列数的计算公式.

排列数公式

从 $n$ 个不同元素中取出 $k$ 个元素的排列数 ($0 \le k \le n$) 为 <MathBlock raw={"A(n,k) = \frac{n!}{k!(n-k)!} \times k! = \frac{n!}{(n-k)!} = n(n-1)\cdots(n-k+1)"} />

证明

我们的目标是计算从 $n$ 个不同元素中, 按顺序取出 $k$ 个元素的所有方法的总数, 即 $A(n,k)$. 我们可以将构造这样一个排列的过程视为一个需要分步完成的任务，从而直接应用乘法原理.

想象我们有 $k$ 个空置的位置, 需要从一个含有 $n$ 个元素的集合 $S$ 中选择元素来填充它们，且每个元素最多只能使用一次.

• 第一步： 填充第一个位置. 我们可以从集合 $S$ 中选择任意一个元素, 因此有 $n$ 种不同的选择.

• 第二步： 填充第二个位置. 由于已经有一个元素被用于填充第一个位置，集合 $S$ 中只剩下 $n-1$ 个元素可用.因此, 有 $n-1$ 种选择.

• 第三步： 填充第三个位置. 已有两个元素被使用，剩下 $n-2$ 个元素可用.因此, 有 $n-2$ 种选择.

• ...

• 第 $k$ 步： 填充第 $k$ 个（也是最后一个）位置. 此时，已有 $k-1$ 个元素被使用, 剩下 $n-(k-1) = n-k+1$ 个元素可用.因此, 有 $n-k+1$ 种选择.

  根据乘法原理，完成所有这 $k$ 个步骤的总方法数是每一步方法数的乘积.因此， <MathBlock raw={"A(n,k) = n \times (n-1) \times (n-2) \times \cdots \times (n-k+1)"} /> 这便证明了公式的第一个等式.

  为了得到阶乘形式的表达式，我们可以对上式进行一个简单的代数变换.通过在分子和分母上同时乘以 $(n-k)!$: <MathBlock raw={"A(n,k) = n(n-1)\cdots(n-k+1) \times \frac{(n-k)(n-k-1)\cdots 1}{(n-k)(n-k-1)\cdots 1}"} /> 分子的部分现在是一个从 $n$ 开始到 $1$ 的完整连乘积, 即 $n!$. 分母部分则是 $(n-k)!$. 所以， <MathBlock raw={"A(n,k) = \frac{n!}{(n-k)!}"} /> 这就证明了公式的第二个等式.

  最后，根据我们在上一节推导出的排列与组合的关系 $A(n,k) = \binom{n}{k} \times k!$，我们可以验证其一致性： <MathBlock raw={"\binom{n}{k} \times k! = \frac{n!}{k!(n-k)!} \times k! = \frac{n!}{(n-k)!} = A(n,k)"} /> 这不仅验证了我们的公式，也再次强调了排列与组合之间的联系，也就是说，一个 $k$-排列可以被看作是先进行一次 $k$-组合，再对选出的元素进行一次全排列.

例

一个班级有10名学生，需要从中选出3人，分别担任班长、学习委员和体育委员.有多少种不同的选举结果？

解

这个问题是典型的排列问题，因为职位不同，所以人选的顺序是至关重要的. (张三任班长, 李四任学委) 与 (李四任班长, 张三任学委) 是两种截然不同的结果.

法一：直接使用排列数公式. 这相当于从10个人中选出3个人进行排列. <MathBlock raw={"P(10,3) = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10 \times 9 \times 8 = 720"} />

法二：利用“先组合，后排序”的思想. 第一步：从10人中选出3个“幸运儿”.这有 $\binom{10}{3}$ 种方法. <MathBlock raw={"\binom{10}{3} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 10 \times 3 \times 4 = 120"} /> 第二步：为这3个选出的人分配3个不同的职位.这有 $3!$ 种方法. <MathBlock raw={"3! = 3 \times 2 \times 1 = 6"} /> 根据乘法原理，总的选举结果为 <MathBlock raw={"N = \binom{10}{3} \times 3! = 120 \times 6 = 720"} /> 两种方法的结果完全一致，这验证了我们对排列与组合关系的理解.

二项式定理

{/* label: sec:ch09-s03 */}

在上一节中，我们引入了组合数 $\binom{n}{k}$, 并将其定义为从 $n$ 个不同元素中选取 $k$ 个的方案数.这个符号也被称为二项式系数.这个名字本身就暗示了它与“二项式”——即形如 $(x+y)$ 的代数表达式——之间存在着深刻的联系.本节的目标就是揭示这一联系，它集中体现在数学中最重要和最美丽的定理之一：二项式定理.

让我们从简单的例子开始，观察其展开式的系数规律： <MathBlock raw={"\begin{aligned} (x+y)^0 &= 1 (x+y)^1 &= 1x + 1y (x+y)^2 &= 1x^2 + 2xy + 1y^2 (x+y)^3 &= 1x^3 + 3x^2y + 3xy^2 + 1y^3 (x+y)^4 &= 1x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + 1y^4 \end{aligned}"} />

我们发现，这些系数似乎与我们之前计算过的某些组合数值相吻合.例如，在 $(x+y)^4$ 的展开式中, 系数 $1, 4, 6, 4, 1$ 恰好就是 $\binom{4}{0}, \binom{4}{1}, \binom{4}{2}, \binom{4}{3}, \binom{4}{4}$ 的值.这难道仅仅是巧合吗？

二项式定理

对于任意变量 $x, y$ 和任意非负整数 $n$，下述展开式成立： <MathBlock raw={"(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k"} /> 展开来看，即： <MathBlock raw={"(x+y)^n = \binom{n}{0}x^n + \binom{n}{1}x^{n-1}y + \binom{n}{2}x^{n-2}y^2 + ... + \binom{n}{n-1}xy^{n-1} + \binom{n}{n}y^n"} />

证明

考虑乘积的完全展开形式： <MathBlock raw={"(x+y)^n = \underbrace{(x+y)(x+y)\cdots(x+y)}_{n \text{个因子}}"} /> 根据乘法分配律，展开后的每一项都是通过从 $n$ 个 $(x+y)$ 因子中, 各自选择 $x$ 或 $y$ 相乘得到的.例如, 要得到 $x^n$ 这一项, 我们必须从每一个因子中都选择 $x$.

现在，我们来思考一个更普遍的项，形如 $x^{n-k}y^k$ 是如何产生的. 为了构成这一项，我们必须从 $n$ 个 $(x+y)$ 因子中：

• 恰好从 $k$ 个因子中选择 $y$.

• 从其余的 $n-k$ 个因子中选择 $x$.

  每一次这样的选择方案，都会贡献一个 $x^{n-k}y^k$ 项.因此, 展开式中 $x^{n-k}y^k$ 的系数，就等于构成该项的不同选择方案的总数.

  这个“选择方案的总数”是一个我们非常熟悉的问题：它等价于“从 $n$ 个不同的因子中, 选出 $k$ 个来提供 $y$ 的方案数”.

  根据组合的定义，这个方案数恰好是 $\binom{n}{k}$.

  因此，$x^{n-k}y^k$ 项的系数必然是 $\binom{n}{k}$.

  由于 $k$ 可以从 $0$ (即一个 $y$ 都不选, 得到 $x^n$) 取到 $n$ (即全部选 $y$, 得到 $y^n$)，我们将所有这些项加起来，就得到了二项式定理的完整形式： <MathBlock raw={"(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k"} />

这个证明完美地解释了为什么组合数会作为系数出现在二项式的展开式中.

杨辉三角

将二项式系数 $\binom{n}{k}$ 排列成一个三角形的阵列，我们就得到了著名的杨辉三角.

\begin{figure}[htbp]

TikZ 图 115

{k} = \binom{n-1}{k-1} + \binom{n-1}{k}}{C(n,k)=C(n-1,k-1)+C(n-1,k)} 的一个例子, \texorpdfstring{\binom{4}{2} = \binom{3}{1} + \binom{3}{2}}{C(4,2)=C(3,1)+C(3,2)}} \end{figure} *图：注意恒等式 \texorpdfstring{\binom{n*

杨辉三角最引人注目的性质是：每个数都等于它肩上两个数之和.例如，在 $n=4$ 行, 6 是由它上一行($n=3$)中的 3 和 3 相加得到的.这个性质在数学上被称为帕斯卡恒等式.

帕斯卡恒等式

对于所有满足 $1 \le k \le n$ 的整数 $n, k$，有 <MathBlock raw={"\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}"} />

虽然这个恒等式可以通过代数方法（将组合数公式代入并通分）来证明，但我们在此给出一个更具启发性的组合学证明.

证明

考虑一个组合问题：从 $n$ 个人的一个班级中选出一个由 $k$ 人组成的班委会.我们知道, 总的方法数是 $\binom{n}{k}$.

但是，我们换一种方式来计数.我们从这个小组中指定一个特殊的人，李华.对于最终选出的委员会，只有两种可能的情况，且这两种情况是互斥的：

情况一：李华在班委中. 如果李华已经被选中，那么我们只需要从剩下 $n-1$ 个人中, 再选出 $k-1$ 个人来填补班委的剩余名额.完成这件事的方法数是 $\binom{n-1}{k-1}$.

情况二：李华不在班委中. 如果李华没有被选中，那么我们必须从剩下 $n-1$ 个人中, 选出全部 $k$ 个班委成员.完成这件事的方法数是 $\binom{n-1}{k}$.

根据加法原理，完成“选班委”这件事的总方法数，等于上述两种互斥情况的方法数之和.因此，我们得到： <MathBlock raw={"\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}"} />

从三项式定理到多项式定理*

{/* label: sec:ch09-s04 */}

一旦我们得出了二项式定理，一个更自然的问题是：是否有类似的三项式定理、四项式定理$\cdots$呢？ 让我们沿用证明二项式定理时的组合思想来分析 $(x+y+z)^n$ 的展开式. <MathBlock raw={"(x+y+z)^n = \underbrace{(x+y+z)(x+y+z)\cdots(x+y+z)}_{n \text{个因子}}"} /> 展开后的任意一项必然具有 $x^{k_1} y^{k_2} z^{k_3}$ 的形式.由于我们是从 $n$ 个因子中各取一个变量相乘, 所以这些变量的指数总和必须等于 $n$，即 <MathBlock raw={"k_1 + k_2 + k_3 = n (\text{其中 } k_1, k_2, k_3 \text{ 为非负整数})"} /> 现在，关键问题是：项 $x^{k_1} y^{k_2} z^{k_3}$ 的系数是多少？ 这个系数等于从 $n$ 个因子中, 选出 $k_1$ 个提供 $x$、选出 $k_2$ 个提供 $y$、再选出 $k_3$ 个提供 $z$ 的总方案数.我们可以通过分步计数来解决这个问题：

1. 第一步：为 $x$ 选择因子. 从 $n$ 个可用的因子中, 选出 $k_1$ 个.这有 $\binom{n}{k_1}$ 种方法.
2. 第二步：为 $y$ 选择因子. 从剩下的 $n-k_1$ 个因子中, 选出 $k_2$ 个.这有 $\binom{n-k_1}{k_2}$ 种方法.
3. 第三步：为 $z$ 选择因子. 最后剩下的 $n-k_1-k_2 = k_3$ 个因子, 全部用于提供 $z$.这只有 $\binom{k_3}{k_3}=1$ 种方法.

根据乘法原理，总的方案数为： <MathBlock raw={"\begin{aligned} \binom{n}{k_1} \binom{n-k_1}{k_2} &= \frac{n!}{k_1!(n-k_1)!} \cdot \frac{(n-k_1)!}{k_2!(n-k_1-k_2)!} &= \frac{n!}{k_1!(n-k_1)!} \cdot \frac{(n-k_1)!}{k_2!k_3!} &= \frac{n!}{k_1!k_2!k_3!} \end{aligned}"} /> 这个结果引出了三项式系数的定义.

三项式系数

对于满足 $k_1+k_2+k_3=n$ 的非负整数 $k_1, k_2, k_3$，三项式系数被定义为 <MathBlock raw={"\binom{n}{k_1, k_2, k_3} = \frac{n!}{k_1!k_2!k_3!}"} />

分组问题

三项式系数 $\binom{n}{k_1, k_2, k_3}$ 有一个非常直观的组合解释：它表示将 $n$ 个不同的物体分成三组, 各组物体的数量分别为 $k_1, k_2, k_3$ 的方法数.这与我们上面的推导过程（将 $n$ 个因子分成三组）是完全一致的.它也等价于对包含 $k_1$ 个 $x$、$k_2$ 个 $y$ 和 $k_3$ 个 $z$ 的多重集进行全排列的数目.

多项式定理

有了三项式系数的定义，我们可以将二项式定理正式推广到三项式.

三项式定理

对于任意变量 $x, y, z$ 和任意非负整数 $n$，下述展开式成立： <MathBlock raw={"(x+y+z)^n = \sum_{k_1+k_2+k_3=n} \binom{n}{k_1, k_2, k_3} x^{k_1} y^{k_2} z^{k_3}"} /> 其中求和遍历所有满足条件的非负整数解 $(k_1, k_2, k_3)$.

在深入证明之前，我们必须首先理解三项式定理中求和符号 $\sum_{k_1+k_2+k_3=n}$ 的确切含义.

这个记号表示，我们需要对所有满足以下两个条件的有序整数三元组 $(k_1, k_2, k_3)$ 进行求和：

1. $k_1, k_2, k_3$ 均为非负整数, 即 $k_1 \ge 0, k_2 \ge 0, k_3 \ge 0$.
2. 它们的和恰好等于 $n$, 即 $k_1+k_2+k_3=n$.

这个过程也被称为“遍历 $n$ 的所有整数分拆到三个部分”.

让我们以一个具体的例子 $n=2$ 来阐明.我们需要找出所有满足 $k_1+k_2+k_3=2$ 的非负整数解 $(k_1, k_2, k_3)$. 我们可以系统地列出它们：

• 如果 $k_1=2$, 那么 $k_2=0, k_3=0$. 得到 $(2,0,0)$.
• 如果 $k_1=1$, 那么 $k_2+k_3=1$. 这有两种可能：$(1,1,0)$ 和 $(1,0,1)$.
• 如果 $k_1=0$, 那么 $k_2+k_3=2$. 这有三种可能：$(0,2,0), (0,1,1), (0,0,2)$.

所以，对于 $n=2$，求和符号意味着将对应于以下6个三元组的项全部加起来： <MathBlock raw={"(2,0,0), (0,2,0), (0,0,2), (1,1,0), (1,0,1), (0,1,1)"} /> 因此，$(x+y+z)^2$ 的展开式实际上是： <MathBlock raw={"\begin{aligned} \sum_{k_1+k_2+k_3=2} &\binom{2}{k_1,k_2,k_3} x^{k_1}y^{k_2}z^{k_3} = &\binom{2}{2,0,0}x^2y^0z^0 + \binom{2}{0,2,0}x^0y^2z^0 + \binom{2}{0,0,2}x^0y^0z^2 &+ \binom{2}{1,1,0}x^1y^1z^0 + \binom{2}{1,0,1}x^1y^0z^1 + \binom{2}{0,1,1}x^0y^1z^1 &= 1x^2 + 1y^2 + 1z^2 + 2xy + 2xz + 2yz \end{aligned}"} /> 这与我们直接用分配律展开得到的结果完全一致.

证明

我们采用组合论证来确定展开式中任意一个通项 $x^{k_1} y^{k_2} z^{k_3}$ 的系数, 其中 $k_1, k_2, k_3$ 是满足 $k_1+k_2+k_3=n$ 的非负整数.

考虑乘积的展开形式： <MathBlock raw={"(x+y+z)^n = \underbrace{(x+y+z)(x+y+z)\cdots(x+y+z)}_{n \text{个因子}}"} /> 根据乘法分配律，展开后的每一项都是通过从这 $n$ 个 $(x+y+z)$ 因子中的每一个因子里选择一个变量（$x$, $y$ 或 $z$）相乘而得到的.

为了构成一个具体的项 $x^{k_1} y^{k_2} z^{k_3}$，我们必须：

• 恰好从 $n$ 个因子中的 $k_1$ 个因子里选择变量 $x$.

• 恰好从剩下的 $n-k_1$ 个因子中的 $k_2$ 个因子里选择变量 $y$.

• 恰好从最后剩下的 $n-k_1-k_2 = k_3$ 个因子里选择变量 $z$.

  因此，项 $x^{k_1} y^{k_2} z^{k_3}$ 在最终展开式中出现的次数（即它的系数），等于完成上述三步选择的总方案数.

  我们可以使用乘法原理来计算这个方案数：

1. 为 $x$ 选择因子. 我们需要从 $n$ 个不同的因子中, 选出 $k_1$ 个来提供变量 $x$. 这是一个组合问题, 方法数是 $\binom{n}{k_1}$.
2. 为 $y$ 选择因子. 在完成了第一步之后，还剩下 $n-k_1$ 个因子.我们需要从这些剩余的因子中, 选出 $k_2$ 个来提供变量 $y$. 方法数是 $\binom{n-k_1}{k_2}$.
3. 为 $z$ 选择因子. 此时，最后剩下 $n-k_1-k_2 = k_3$ 个因子.我们必须从这 $k_3$ 个因子中选出 $k_3$ 个来提供变量 $z$. 方法数是 $\binom{k_3}{k_3}=1$.

根据乘法原理，总的方案数是以上三步方法数的乘积： <MathBlock raw={"\begin{aligned} \text{系数} &= \binom{n}{k_1} \binom{n-k_1}{k_2} \binom{k_3}{k_3} &= \frac{n!}{k_1!(n-k_1)!} \cdot \frac{(n-k_1)!}{k_2!(n-k_1-k_2)!} \cdot \frac{k_3!}{k_3!0!} &= \frac{n!}{k_1!\cancel{(n-k_1)!}} \cdot \frac{\cancel{(n-k_1)!}}{k_2!(k_3)!} \cdot 1 (\text{因为 } n-k_1-k_2=k_3) &= \frac{n!}{k_1!k_2!k_3!} &= \binom{n}{k_1, k_2, k_3} \end{aligned}"} />

我们已经证明，对于任意满足 $k_1+k_2+k_3=n$ 的非负整数组 $(k_1,k_2,k_3)$, 其对应项 $x^{k_1}y^{k_2}z^{k_3}$ 的系数恰好是三项式系数 $\binom{n}{k_1, k_2, k_3}$.

将所有这些可能的项加起来，就构成了 $(x+y+z)^n$ 的完整展开式.因此，定理得证.

例

求在 $(2x - y + 3z^2)^5$ 的展开式中, $x^2 y z^4$ 项的系数.

解

我们首先将表达式看作 $(A+B+C)^5$ 的形式, 其中 $A=2x, B=-y, C=3z^2$. 我们要寻找的项是 $x^2 y z^4$. 我们需要确定 $A, B, C$ 各自的指数是多少.

令该项为 $A^{k_1} B^{k_2} C^{k_3}$ 的形式, 其中 $k_1+k_2+k_3=5$.

• 为了得到 $x^2$, 我们需要 $(2x)^{k_1}$ 产生 $x^2$, 所以 $k_1=2$.

• 为了得到 $y^1$, 我们需要 $(-y)^{k_2}$ 产生 $y^1$, 所以 $k_2=1$.

• 为了得到 $z^4$, 我们需要 $(3z^2)^{k_3}$ 产生 $z^4$, 即 $(z^2)^{k_3} = z^{2k_3} = z^4$, 所以 $2k_3=4 \implies k_3=2$.

  我们检查指数和：$k_1+k_2+k_3 = 2+1+2 = 5$, 这与 $n=5$ 相符.

  根据三项式定理，包含 $A^2 B^1 C^2$ 的完整项是： <MathBlock raw={"\binom{5}{2, 1, 2} A^2 B^1 C^2"} /> 首先，计算三项式系数： <MathBlock raw={"\binom{5}{2, 1, 2} = \frac{5!}{2!1!2!} = \frac{120}{2 \cdot 1 \cdot 2} = 30"} /> 然后，代入 $A, B, C$ 的具体表达式： <MathBlock raw={"30 \cdot (2x)^2 \cdot (-y)^1 \cdot (3z^2)^2"} /> <MathBlock raw={"= 30 \cdot (4x^2) \cdot (-y) \cdot (9z^4)"} /> <MathBlock raw={"= (30 \cdot 4 \cdot (-1) \cdot 9) x^2 y z^4"} /> <MathBlock raw={"= -1080 x^2 y z^4"} /> 因此，$x^2 y z^4$ 项的系数是 $-1080$.

这个思想可以被自然地推广到任意数量的项，从而得到更一般化的多项式定理.

考虑展开式 $(x_1+x_2+...+x_m)^n$. 其通项必然具有 $x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m}$ 的形式, 其中指数和必须为 $n$, 即 $k_1+k_2+...+k_m=n$.

该项的系数是什么呢？遵循之前的组合论证，这个系数等于将 $n$ 个不同的因子分成 $m$ 组, 并指定第 $i$ 组提供变量 $x_i$ 的方案数, 其中第 $i$ 组的大小恰好为 $k_i$. 我们将这个数称为多项式系数.它的核心组合意义是： 将 $n$ 个不同的物体分成 $m$ 个有区别的组, 使得第 $i$ 组恰好有 $k_i$ 个物体的总方法数.

与二项式系数的关系

二项式系数是多项式系数的一个特例.当我们从 $n$ 个元素中选出 $k$ 个时, 这等价于将 $n$ 个元素分成了两组：一组是“被选中的” $k$ 个元素, 另一组是“未被选中的” $n-k$ 个元素.因此， <MathBlock raw={"\binom{n}{k} = \binom{n}{k, n-k} = \frac{n!}{k!(n-k)!}"} /> 这个视角统一了这些计数工具，揭示了它们共同的“分组”本质.

有了对这个系数组合意义的理解，我们现在可以正式地陈述多项式定理.该定理不仅给出了展开式的完整形式，也同时给出了计算多项式系数的代数公式.

多项式定理

对于任意非负整数 $n$ 和 $m \ge 2$，有 <MathBlock raw={"(x_1+x_2+...+x_m)^n = \sum_{k_1+k_2+...+k_m=n} \binom{n}{k_1, k_2, ..., k_m} x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m}"} /> 其中多项式系数定义为 <MathBlock raw={"\binom{n}{k_1, k_2, ..., k_m} = \frac{n!}{k_1!k_2!\cdots k_m!}"} />

证明

我们将使用一个组合论证，其核心思想是：通过分析代数展开的内在组合结构来确定各项的系数.

首先，我们将 $(x_1+x_2+...+x_m)^n$ 写作 $n$ 个相同因子的乘积： <MathBlock raw={"\underbrace{(x_1+x_2+...+x_m)(x_1+x_2+...+x_m)\cdots(x_1+x_2+...+x_m)}_{n \text{个因子}}"} /> 根据乘法分配律，展开后的每一项都是通过从这 $n$ 个因子中的每一个因子里选择一个变量（$x_1, x_2, ..., \text{或 } x_m$）然后将它们相乘而得到的.

我们来考虑展开式中一个通项的形式，它必然是 $x_1^{k_1} x_2^{k_2} \cdots x_m^{k_m}$, 其中 $k_1, k_2, ..., k_m$ 是非负整数.由于我们总共从 $n$ 个因子中进行选择, 所以指数的总和必须等于 $n$，即 <MathBlock raw={"k_1 + k_2 + ... + k_m = n"} /> 现在，我们的中心任务是计算这个通项的系数.这个系数等于能够产生该项的不同选择方案的总数.换言之，它等于“从 $n$ 个因子中, 选出 $k_1$ 个来提供 $x_1$, 选出 $k_2$ 个来提供 $x_2$, ..., 并选出 $k_m$ 个来提供 $x_m$” 的总方法数.

这本质上是一个将 $n$ 个不同的因子（我们可以想象它们被编号为 $1, 2, ..., n$）分成 $m$ 个不同组的问题, 第 $i$ 组的大小为 $k_i$. 我们可以使用乘法原理，通过一系列连续的组合选择来计算这个方法数：

• 第一步： 从 $n$ 个可用的因子中, 为变量 $x_1$ 选择 $k_1$ 个因子.这有 $\binom{n}{k_1}$ 种方法.

• 第二步： 从剩下的 $n-k_1$ 个因子中, 为变量 $x_2$ 选择 $k_2$ 个因子.这有 $\binom{n-k_1}{k_2}$ 种方法.

• 第三步： 从剩下的 $n-k_1-k_2$ 个因子中, 为变量 $x_3$ 选择 $k_3$ 个因子.这有 $\binom{n-k_1-k_2}{k_3}$ 种方法.

• ...

• 第 $m$ 步： 从最后剩下的 $n-k_1-...-k_{m-1} = k_m$ 个因子中, 为变量 $x_m$ 选择 $k_m$ 个因子.这有 $\binom{k_m}{k_m} = 1$ 种方法.

  根据乘法原理，总的方案数是以上所有步骤方法数的乘积： <MathBlock raw={"\text{系数} = \binom{n}{k_1} \binom{n-k_1}{k_2} \binom{n-k_1-k_2}{k_3} \cdots \binom{k_m}{k_m}"} /> 现在，我们将这些二项式系数用阶乘形式展开，观察化简过程： <MathBlock raw={"\begin{aligned} \text{系数} &= \frac{n!}{k_1!(n-k_1)!} \cdot \frac{(n-k_1)!}{k_2!(n-k_1-k_2)!} \cdot \frac{(n-k_1-k_2)!}{k_3!(n-k_1-k_2-k_3)!} \cdots \frac{k_m!}{k_m!0!} &= \frac{n!}{k_1!\cancel{(n-k_1)!}} \cdot \frac{\cancel{(n-k_1)!}}{k_2!\cancel{(n-k_1-k_2)!}} \cdot \frac{\cancel{(n-k_1-k_2)!}}{k_3!...} \cdots 1 &= \frac{n!}{k_1!k_2!k_3!\cdots k_m!} \end{aligned}"} /> 这正是多项式系数 $\binom{n}{k_1, k_2, ..., k_m}$ 的定义.

  我们已经证明，对于任意满足 $k_1+...+k_m=n$ 的非负整数组 $(k_1, ..., k_m)$, 其对应项 $x_1^{k_1} \cdots x_m^{k_m}$ 的系数恰好是多项式系数 $\binom{n}{k_1, ..., k_m}$.

  将所有这些可能的项（遍历所有满足条件的指数集）加总，便构成了 $(x_1+...+x_m)^n$ 的完整展开式.至此，定理得证.

排列组合

{/* label: sec:ch09-s05 */}

排列与组合的公式为我们提供了计数的代数工具，然而，面对千变万化的计数问题，仅仅掌握公式是远远不够的.真正的挑战在于如何将一个复杂的问题进行剖析、转化，使其结构清晰地对应到我们所学的基本模型上.

相邻与不相邻问题

在排列问题中，元素之间的相对位置关系是最常出现的约束条件之一.“相邻”与“不相邻”构成了一对典型的对立约束，分别对应着两种经典的处理技巧：捆绑法与 插空法.

相邻问题与捆绑法

当问题要求若干个特定元素必须排列在一起（即“相邻”）时，我们可以采用捆绑法来解决.该策略的核心思想是，将这些必须相邻的元素在逻辑上视为一个不可分割的整体，即一个“复合元素”，然后再与其他元素进行排列.

捆绑法

解决元素相邻的排列问题，通常遵循以下步骤：

1. 捆绑：将所有必须相邻的 $m$ 个元素视为一个单一的、不可分割的“大元素”.
2. 外排：将这个“大元素”与其余的 $n-m$ 个元素进行全排列.如果共有 $k$ 个元素（包括“大元素”）, 则此步的方案数为 $k!$.
3. 内排：考虑被捆绑的 $m$ 个元素内部自身的排列方式.此步的方案数通常为 $m!$.
4. 相乘：根据乘法原理，将“外排”和“内排”的方案数相乘，得到最终结果.

例

有5名男生和3名女生站成一排，如果要求3名女生必须站在一起，问有多少种不同的排法？

解

这是一个典型的相邻问题，我们可以运用捆绑法.

第一步：捆绑. 将3名女生视为一个整体，记作 $G$. 现在，问题转化为对5名男生 $B_1, B_2, B_3, B_4, B_5$ 和一个女生整体 $G$ 进行排列.

第二步：外排. 我们现在需要排列的对象是 $\{B_1, B_2, B_3, B_4, B_5, G\}$, 共 $5+1=6$ 个元素. 对这6个元素进行全排列，方法数为 <MathBlock raw={"A(6,6) = 6! = 720"} />

第三步：内排. 在女生构成的整体 $G$ 内部，3名女生自身也可以有不同的排列顺序. 3名女生的全排列方法数为 <MathBlock raw={"A(3,3) = 3! = 6"} />

第四步：相乘. 根据乘法原理，总的排法数是外排和内排方法数的乘积. <MathBlock raw={"N = 6! \times 3! = 720 \times 6 = 4320"} /> 所以，共有4320种不同的排法.

例

用数字 0, 1, 2, 3, 4, 5 组成没有重复数字的六位数，要求偶数数字必须相邻，奇数数字也必须相邻，问能组成多少个这样的六位数？

解

首先，我们确定数字的奇偶性. 偶数集合 $E = \{0, 2, 4\}$，共3个. 奇数集合 $O = \{1, 3, 5\}$，共3个.

问题要求偶数相邻，奇数也相邻.我们应用两次捆绑法.

第一步：捆绑. 将3个偶数捆绑成一个整体，记作 $B_E$. 将3个奇数捆绑成一个整体，记作 $B_O$.

第二步：外排. 现在的问题等价于排列 $B_E$ 和 $B_O$ 这两个“大元素”. 全排列方法数为 $2!$. 但是，组成的数是六位数，首位不能为0.我们需要对 $B_E$ 和 $B_O$ 的排列进行分类讨论.

情况一：奇数捆绑 $B_O$ 在首位. 此时排列为 $(B_O, B_E)$. 这种情况下，首位必然是奇数（1, 3或5），不可能是0，因此所有排列都有效. $B_O$ 内部的排列数：$3! = 6$. $B_E$ 内部的排列数：$3! = 6$. 此情况下的总方法数为 $3! \times 3! = 36$.

情况二：偶数捆绑 $B_E$ 在首位. 此时排列为 $(B_E, B_O)$. 这种情况下, 首位必须是 $B_E$ 中的一个数字. 为了保证是六位数，首位不能是0. 我们考虑 $B_E$ 内部的排列. 它的首位有两个选择（2或4）. 剩下的2个偶数（包括0）在 $B_E$ 内部的后两个位置进行全排列, 有 $2!$ 种方法. 所以，$B_E$ 内部有效的排列数为 $2 \times 2! = 4$. $B_O$ 内部的排列数依然是 $3! = 6$. 此情况下的总方法数为 $4 \times 6 = 24$.

第三步：相加. 根据加法原理，将两种情况的方法数相加. <MathBlock raw={"N = 36 + 24 = 60"} /> 所以，共能组成60个这样的六位数.

不相邻问题与插空法

当问题要求若干个特定元素必须互不相邻时，我们可以采用插空法.该策略的核心思想是，先排列那些没有位置限制的元素，这些元素会自然地形成一些“空隙”，然后将要求不相邻的元素插入到这些空隙中.

插空法

解决元素互不相邻的排列问题，通常遵循以下步骤：

1. 排不受限元素：首先排列那些没有“不相邻”限制的元素.假设有 $n$ 个这样的元素, 它们的排列数为 $n!$.
2. 造空：这 $n$ 个元素排好后, 将产生 $n+1$ 个可供插入的空隙（包括队伍的最前端和最后端）.
3. 插入：将 $m$ 个要求不相邻的元素, 插入到这 $n+1$ 个空隙中.由于每个空隙最多只能放一个元素, 这相当于从 $n+1$ 个空隙中选出 $m$ 个进行排列.方案数为 $A(n+1, m)$.
4. 相乘：根据乘法原理，将上述步骤的方案数相乘，得到最终结果.

例

将3本不同的小说和4本不同的诗集排成一排，要求3本小说互不相邻，问有多少种不同的排法？

解

这是一个典型的“互不相邻”问题，应使用插空法. 小说是受限元素，诗集是不受限元素.

第一步：排诗集. 首先排列4本不同的诗集.方法数为 <MathBlock raw={"A(4,4) = 4! = 24"} />

第二步：造空. 4本诗集排好后，形成5个可供插入的空隙. <MathBlock raw={"\_ P_1 \_ P_2 \_ P_3 \_ P_4 \_"} />

第三步：插小说. 将3本不同的小说插入到这5个空隙中，每空至多一本. 这相当于从5个空隙中选出3个来放置小说，并且要考虑小说的顺序.这是一个排列问题. 方法数为 <MathBlock raw={"A(5,3) = 5 \times 4 \times 3 = 60"} />

第四步：相乘. 根据乘法原理，总的排法数为 <MathBlock raw={"N = 4! \times A(5,3) = 24 \times 60 = 1440"} /> 所以，共有1440种不同的排法.

“不相邻”与“不全相邻”的辨析

在处理计数问题时，必须精确理解约束条件的含义.“互不相邻”与“不全相邻”是两个极易混淆的概念.

• 互不相邻：指任意两个指定的元素都不能相邻.这是插空法的适用范围.

• 不全相邻：指指定的元素不全部连在一起即可，允许其中一部分相邻.

  对于“不全相邻”问题，直接计数通常很困难，因为它包含多种复杂情况.此时，更简洁的策略是使用补集思想（正难则反），即用总的排列数减去其对立面——“全部相邻”的排列数.

例

有5名男生和3名女生站成一排，回答下列问题：

1. 3名女生互不相邻的排法有多少种？
2. 3名女生不全相邻的排法有多少种？

解

这个问题旨在厘清“互不相邻”和“不全相邻”的区别.

(1) 3名女生互不相邻. 这是一个“插空法”问题. 第一步：先排5名男生，有 $5!$ 种方法. 第二步：5名男生形成6个空隙. 第三步：将3名女生插入6个空隙中，有 $A(6,3)$ 种方法. 根据乘法原理，总方法数为 <MathBlock raw={"N_1 = 5! \times A(6,3) = 120 \times (6 \times 5 \times 4) = 120 \times 120 = 14400"} />

(2) 3名女生不全相邻. 这是一个“补集思想”问题.它的对立面是“3名女生全部相邻”. 首先，计算总的排列数.8个人全排列，有 $8!$ 种方法. <MathBlock raw={"8! = 40320"} /> 接着，计算对立事件（3名女生全部相邻）的排列数. 这正是我们用“捆绑法”计算过的第一个例子. 将3名女生捆绑，与5名男生共6个元素全排列，再乘以女生内部的全排列. <MathBlock raw={"N_{\text{全相邻}} = 6! \times 3! = 720 \times 6 = 4320"} /> 最后，用总数减去对立事件数. <MathBlock raw={"N_2 = 8! - (6! \times 3!) = 40320 - 4320 = 36000"} />

比较两个结果，我们可以看到 $N_1 \< N_2$. 这是因为“不全相邻”的情况包含了“恰有两名女生相邻”以及“三名女生互不相邻”这两种情况, 而 $N_1$ 只是后者.

为何捆绑法与插空法有效？

在上一节中，我们介绍了处理相邻与不相邻问题的两种标准化流程：捆绑法与插空法.这些方法之所以强大，是因为它们并非简单的技巧，而是将复杂的约束问题巧妙地转化为基本计数原理应用的典范.本节将深入探讨这两种方法背后的数学逻辑，以揭示其有效性的根本原因.

捆绑法

相邻问题的核心约束是“某些元素必须保持相对位置不变”，这破坏了全排列中每个元素独立性的前提.捆绑法的本质，是将一个带有复杂约束的计数问题，通过逻辑上的等价变换，转化为一个无约束的、分步的构造问题.

核心原理

我们将证明，一个满足“$m$个元素相邻”的排列，可以被唯一地通过以下两个独立的步骤构造出来：

1. 内部构造：将被指定的 $m$ 个元素进行全排列，形成一个有序的、不可分割的复合元素.
2. 外部构造：将此复合元素与其余 $n-m$ 个普通元素进行全排列.

让我们来分析这个构造过程的完备性与唯一性：

• 完备性：任何一个满足条件的最终排列，都能通过这个两步构造法得到吗？答案是肯定的.在任意一个满足条件的排列中，那 $m$ 个相邻的元素必然以某种顺序排列（对应内部构造），并且这个由它们组成的“元素块”必然在整个序列中占据一个位置（对应外部构造）.因此，不存在任何一种合法的排列会被我们的构造过程遗漏.
• 唯一性：是否存在两个不同的构造步骤序列，会产生同一个最终排列？答案是否定的.如果我们改变了内部构造（例如，将捆绑的 $\{A,B\}$ 顺序从 $(A,B)$ 改为 $(B,A)$），那么最终排列中这部分元素的顺序也必然改变.同样，如果我们改变了外部构造（例如，将复合元素的位置移动），那么最终排列也必然不同.因此，每一个独特的“内部构造+外部构造”组合都唯一地对应一个最终的合法排列.

由于我们建立了一个从“构造步骤”到“合法排列”的一一对应关系，那么“合法排列”的总数就精确地等于“构造步骤”的总数.根据乘法原理，构造步骤的总数是每一步方法数的乘积.

• 内部构造的方法数是对 $m$ 个元素的全排列, 即 $m!$.
• 外部构造的方法数是将 $n-m+1$ 个元素（$n-m$个普通元素和1个复合元素）进行全排列, 即 $(n-m+1)!$.

因此，总方法数为 $(n-m+1)! \times m!$. 这就从根本上证明了捆绑法计算逻辑的正确性.它将一个静态的“满足约束的排列集合有多大”的问题，动态地转变为“生成一个这样的排列有多少种方法”的问题.

插空法

不相邻问题的核心约束是“某些元素之间必须被其他元素隔开”.直接处理这种“排斥性”约束是困难的.插空法的精妙之处在于，它通过逆向思维，将一个复杂的定位问题，转化为一个有序的填充问题.

插空法同样是一个构造性的过程，其逻辑的严谨性依赖于以下分步构造的唯一性与完备性：

1. 构建框架：首先排列那些没有位置限制的 $n$ 个元素.这一步的目的是创建一个稳定的“骨架”或“框架”.
2. 填充框架：将要求不相邻的 $m$ 个元素，放置到由上述框架产生的空隙中.

让我们来审视这个过程的数学基础：

• 空隙的定义：$n$ 个已经排好的元素 $U_1, U_2, ..., U_n$, 会在它们之间以及两端, 严格地定义出 $n+1$ 个不同的、可识别的“空隙”位置. <MathBlock raw={"\_ U_1 \_ U_2 \_ ... \_ U_n \_"} /> 这些空隙是放置“不相邻”元素的理想容器，因为任何被放入不同空隙的两个元素，都必然被至少一个框架元素所分隔，从而天然满足了“不相邻”的约束.

• 填充的本质是排列：当我们将 $m$ 个不同的受限元素放入 $n+1$ 个空隙中，并且每个空隙至多放一个元素时，这个过程本身是一个排列问题.它等价于：

• 从 $n+1$ 个空隙中选出 $m$ 个空隙.

• 将 $m$ 个不同的元素排入这 $m$ 个选定的空隙中.

  这正是排列 $A(n+1, m)$ 的组合意义.

与捆绑法类似，这个两步构造过程（构建框架 $\rightarrow$ 填充框架）与所有满足“互不相邻”条件的最终排列之间，也构成了一个一一对应关系.

• 完备性：任何一个合法的排列，其不受限元素必然构成一个有序子序列（对应框架构建），而受限元素必然分布在由这些不受限元素隔开的位置上（对应填充框架）.
• 唯一性：如果框架的排列不同，或者填充空隙的方案不同，最终得到的总排列也必然不同.

因此，满足条件的总排列数，等于构建框架的方法数与填充框架的方法数的乘积.

• 构建框架的方法数是对 $n$ 个不受限元素的全排列, 即 $n!$.
• 填充框架的方法数是从 $n+1$ 个空隙中选 $m$ 个进行排列, 即 $A(n+1, m)$.

最终结果为 $n! \times A(n+1, m)$. 这雄辩地证明了插空法不仅仅是一个便捷的技巧，而是一个逻辑严密、基于乘法原理的构造性证明.

总而言之，捆绑法和插空法是组合思维中“转化与构造”思想的集中体现.捆绑法通过“化零为整”简化了元素间的关系，而插空法通过“先主后次”确定了元素的相对位置.理解它们深层的构造性原理，是我们将这些方法推广应用到更复杂计数问题的关键.

2020.4学军中学高二下期中

一条街道上有 10 盏路灯，将路灯依次排列并编号 1-10. 有关部门要求晚上这 10 盏路灯中相邻的两盏灯不能全开，且这 10 盏路灯中至少打开两盏路灯.则符合要求的开法总数是 \rule{2cm}{0.4pt}.

解

法一：

此问题的核心约束是“开着的灯互不相邻”，并且这是一个组合问题，因为我们只关心哪些位置的灯是开的，而灯本身是无差别的.

问题的关键在于转换视角.直接去挑选 $k$ 个不相邻的位置是困难的，但我们可以反过来思考：利用“不开的灯”来为“开的灯”制造空隙.这正是插空思想的精髓.

我们根据打开的灯数 $k$ 进行分类讨论, 其中 $k \ge 2$.

假设我们打开 $k$ 盏灯, 那么就有 $10-k$ 盏灯是关着的. 我们可以将这 $10-k$ 盏关着的灯（视为相同的元素）先排成一排, 它们自然地形成了 $(10-k)+1 = 11-k$ 个空隙（包括两端）.

为了保证打开的 $k$ 盏灯彼此不相邻, 我们必须将这 $k$ 盏灯放入到这 $11-k$ 个不同的空隙中，且每个空隙最多只能放一盏灯.

由于灯的状态（开或关）是无差别的，这个过程等价于从 $11-k$ 个空隙中选出 $k$ 个来放置要打开的灯.这是一个纯粹的组合问题，方法数为 <MathBlock raw={"\binom{11-k}{k}"} /> 现在我们考虑 $k$ 的取值范围.根据问题要求, $k \ge 2$. 同时, 空隙的数量必须不少于要插入的灯的数量, 即 $11-k \ge k \implies 2k \le 11 \implies k \le 5.5$. 因此 $k$ 的所有可能取值为 $2, 3, 4, 5$.

根据加法原理，我们将所有情况的开法数相加：

• 打开2盏灯 ($k=2$)： 有 $10-2=8$ 盏灯关闭, 形成 $8+1=9$ 个空隙. 方法数为 $\dbinom{9}{2} = \dfrac{9 \times 8}{2} = 36$.

• 打开3盏灯 ($k=3$)： 有 $10-3=7$ 盏灯关闭, 形成 $7+1=8$ 个空隙. 方法数为 $\dbinom{8}{3} = \dfrac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$.

• 打开4盏灯 ($k=4$)： 有 $10-4=6$ 盏灯关闭, 形成 $6+1=7$ 个空隙. 方法数为 $\dbinom{7}{4} = \dbinom{7}{3} = 35$.

• 打开5盏灯 ($k=5$)： 有 $10-5=5$ 盏灯关闭, 形成 $5+1=6$ 个空隙. 方法数为 $\dbinom{6}{5} = 6$.

  将所有可能情况相加，得到总的开法数为 <MathBlock raw={"N = \binom{9}{2} + \binom{8}{3} + \binom{7}{4} + \binom{6}{5} = 36 + 56 + 35 + 6 = 133"} /> 所以，符合要求的开法总数是133. 法二：

  此问题包含两个核心约束：(1) “开”的灯不能相邻；(2) “开”的灯的数量至少为2. 问题的本质是从10个位置中，选出若干个互不相邻的位置. 这是一个组合问题，而非排列问题，因为我们只关心哪些灯是开的，而不关心其顺序.

  设我们选择打开 $k$ 盏灯. 这等价于从集合 $\{1, 2, ..., 10\}$ 中选取 $k$ 个数，且任意两个数均不相邻. 令选出的 $k$ 个数（即灯的编号）为 $1 \le x_1 \< x_2 \< ... \< x_k \le 10$. “互不相邻”的约束条件可以数学化为 $x_{i+1} - x_i \ge 2$ 对于所有 $i=1, ..., k-1$.

  为了处理这个不等式约束，我们构造一个双射. 定义一个新的整数序列 $y_1, y_2, ..., y_k$ 如下： <MathBlock raw={"y_i = x_i - (i-1)"} /> 我们来分析新序列的性质： $y_1 = x_1 \ge 1$. $y_k = x_k - (k-1) \le 10 - (k-1) = 11-k$. 对于任意 $i$, $y_{i+1} - y_i = (x_{i+1}-i) - (x_i-(i-1)) = (x_{i+1}-x_i) - 1$. 由于 $x_{i+1}-x_i \ge 2$, 我们有 $y_{i+1}-y_i \ge 1$, 这意味着 $y_1 \< y_2 \< ... \< y_k$.

  因此，原问题中选择 $k$ 个互不相邻的数 $x_i$ 从 $\{1, ..., 10\}$, 等价于从集合 $\{1, ..., 11-k\}$ 中选择 $k$ 个不同的数 $y_i$. 这种选择的方法数即为组合数 <MathBlock raw={"\binom{11-k}{k}"} /> 现在我们考虑 $k$ 的取值范围. 根据问题要求, $k \ge 2$. 同时, 为了能够选出 $k$ 个数, 必须有 $11-k \ge k$, 即 $2k \le 11$, 所以 $k \le 5.5$. 因此 $k$ 的可能取值为 $2, 3, 4, 5$.

  根据加法原理，我们将所有可能情况的开法数相加： 当 $k=2$ 时, 方法数为 $\dbinom{11-2}{2} = \dbinom{9}{2} = \dfrac{9 \times 8}{2} = 36$. 当 $k=3$ 时, 方法数为 $\dbinom{11-3}{3} = \dbinom{8}{3} = \dfrac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$. 当 $k=4$ 时, 方法数为 $\dbinom{11-4}{4} = \dbinom{7}{4} = \dbinom{7}{3} = \dfrac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$. 当 $k=5$ 时, 方法数为 $\dbinom{11-5}{5} = \dbinom{6}{5} = 6$.

  总的开法总数为 <MathBlock raw={"N = 36 + 56 + 35 + 6 = 133"} /> 所以，符合要求的开法总数是133.

2014 重庆理

某次联欢会要安排3个歌舞类节目、2个小品类节目和1个相声类节目的演出顺序，则同类节目不相邻的排法种数是（ ）. \begin{multicols}{4}

[label=\Alph*.]

1. 72
2. 120
3. 144
4. 168

\end{multicols}

解

本题涉及对多个元素集合的“不相邻”约束，正面来很复杂，使用容斥原理（正难则反）正好.

首先，我们假定所有6个节目都是独一无二的. 总的排列数（没有任何限制）为 <MathBlock raw={"N_{总} = 6! = 720"} /> 我们需要排除所有不符合“同类节目不相邻”要求的排列. “同类节目不相邻”的对立面是“至少有一类同类节目是相邻的”. 具体来说，就是“2个小品相邻”或者“3个歌舞中有节目相邻”.

设 $U$ 为所有排列的全集, $|U|=720$. 令 $A$ 为 “2个小品节目相邻” 的排列构成的集合. 令 $B$ 为 “至少有2个歌舞节目相邻” 的排列构成的集合. 我们要求解的是 $|U| - |A \cup B|$. 根据容斥原理, $|A \cup B| = |A| + |B| - |A \cap B|$.

将2个小品节目捆绑成一个复合元素.现在我们排列 {歌舞1, 歌舞2, 歌舞3, 相声, (小品块)} 这5个对象，有 $5!$ 种方法. 小品块内部有 $2!$ 种排列. <MathBlock raw={"|A| = 5! \times 2! = 120 \times 2 = 240"} />

直接计算“至少有2个歌舞相邻”比较复杂，我们计算其补集，即“3个歌舞节目互不相邻”（记作 $B^c$）. 为此，我们使用插空法.先排列非歌舞节目{小品1, 小品2, 相声}，有 $3!$ 种方法. 这3个节目形成了4个空隙.将3个不同的歌舞节目插入这4个空隙中，有 $A(4,3)$ 种方法. <MathBlock raw={"|B^c| = 3! \times A(4,3) = 6 \times 24 = 144"} /> 因此，$|B| = |U| - |B^c| = 720 - 144 = 576$.

这个集合表示“小品相邻” 且 “歌舞至少有2个相邻”. 我们同样可以利用补集思想来计算这个交集的大小，即 $|A \cap B| = |A| - |A \cap B^c|$. $|A \cap B^c|$ 表示“小品相邻” 且 “歌舞互不相邻”. 我们再次使用插空法. 将被捆绑的小品块和相声节目作为框架.排列 {(小品块), 相声} 有 $2!$ 种方法.小品块内部有 $2!$ 种排列. 故框架的排列数为 $2! \times 2! = 4$. 这个框架形成了3个空隙.将3个不同的歌舞节目插入这3个空隙中，有 $A(3,3) = 3!$ 种方法. <MathBlock raw={"|A \cap B^c| = (2! \times 2!) \times 3! = 4 \times 6 = 24"} /> 所以, $|A \cap B| = |A| - |A \cap B^c| = 240 - 24 = 216$.

不符合要求的排列总数为 <MathBlock raw={"|A \cup B| = |A| + |B| - |A \cap B| = 240 + 576 - 216 = 600"} /> 因此，符合要求的排列种数为 <MathBlock raw={"N = |U| - |A \cup B| = 720 - 600 = 120"} /> 故选B.

定序问题与倍缩策略

在排列问题中，除了相邻与不相邻的约束外，另一类常见的限制是定序问题，即要求某几个元素必须保持特定的相对顺序.例如，在排列 A, B, C, D 时，要求 A 必须始终在 B 的左边.

面对这类问题，一个极其强大的思想是倍缩策略，其本质是“先放后缩”.我们首先忽略定序的约束，对所有相关元素进行全排列，得到一个总数.然后，我们分析在这个总数中，我们所关注的、被定了序的元素有多少种排列方式.由于题目只允许其中的一种特定顺序，我们原来的计数就“夸大”或“重复”了，其倍数恰好是被定序元素的全排列数.因此，我们用总排列数除以这个“重复倍数”，即可得到最终答案.

这个思想并非全新.事实上，组合数的公式本身就是倍缩策略最经典的体现. <MathBlock raw={"\binom{n}{k} = \frac{A(n,k)}{k!}"} /> 此公式的组合意义是：要从 $n$ 个元素中选出 $k$ 个（不计顺序）, 我们可以先选出 $k$ 个并排列它们（共 $A(n,k)$ 种方法）, 但由于我们不关心这 $k$ 个元素的顺序, 而它们自身有 $k!$ 种不同的排列, 所以我们将 $A(n,k)$ 除以 $k!$ 来“消除”顺序的影响.

倍缩策略，即用总排列数除以被定序元素的全排列数，是解决定序问题的一种高效方法.然而，这种“除法”操作并非凭空产生的技巧，而是乘法原理的逆向应用，其背后是深刻的集合划分与一一对应思想.为了彻底理解其有效性，我们必须回归计数的本源.

我们的目标是计算一个集合 $S$（含 $n$ 个元素）的所有排列中, 满足特定 $m$ 个元素 $M = \{e_1, e_2, ..., e_m\}$ 保持固定相对顺序（例如, $e_1$ 必须在 $e_2$ 之前, $e_2$ 必须在 $e_3$ 之前, 以此类推）的排列总数.令这个我们想求的、符合条件的排列集合为 $\mathcal{A}$, 其大小为 $N = |\mathcal{A}|$.

直接计算 $N$ 是困难的, 因此我们引入一个我们熟知的、更大的集合作为参照：令 $\mathcal{U}$ 为 $S$ 中所有 $n$ 个元素的全排列集合, 我们知道 $|\mathcal{U}| = n!$.

关键在于建立集合 $\mathcal{U}$ 与集合 $\mathcal{A}$ 之间的数学关系.我们将通过一个构造性的论证, 使用乘法原理来表达 $|\mathcal{U}|$.

考虑如何构造出 $\mathcal{U}$ 中的任意一个排列.我们可以通过一个两步过程来唯一地生成每一个排列：

1. 选择一个“骨架”排列. 我们从符合定序条件的集合 $\mathcal{A}$ 中任意选择一个排列. 在这个排列中, 那 $m$ 个特殊元素的相对顺序是正确的.完成这一步, 我们有 $N$ 种选择.
2. 对特殊元素进行“内部重排”. 在上一步选出的“骨架”排列中，那 $m$ 个特殊元素占据了 $m$ 个确定的位置.现在, 我们保持其他 $n-m$ 个元素不动, 只将这 $m$ 个特殊元素在这 $m$ 个位置上进行任意的全排列.完成这一步, 有 $m!$ 种方法.

根据乘法原理，通过这两个步骤，我们总共可以构造出 $N \times m!$ 个不同的排列.

现在，我们必须证明这个构造过程与集合 $\mathcal{U}$ 是等价的.也就是说, 它不重不漏地生成了 $\mathcal{U}$ 中的所有 $n!$ 个排列.

• 无遗漏): $\mathcal{U}$ 中的任何一个排列能否被我们的方法构造出来？ 答案是肯定的.任取一个 $\mathcal{U}$ 中的排列 $p$, 其中 $m$ 个特殊元素的位置和内部顺序是任意的.我们可以通过一个“标准化”操作, 将这 $m$ 个元素按照题目要求的固定顺序重新排列, 从而得到一个唯一对应的“骨架”排列（它必然属于集合 $\mathcal{A}$）.这证明了任何排列 $p$ 都有其构造来源.
• 无重复: 两个不同的构造步骤组合，是否会产生同一个最终排列？ 答案是否定的.假设我们通过 $(\text{骨架}_1, \text{重排}_1)$ 和 $(\text{骨架}_2, \text{重排}_2)$ 得到了同一个最终排列 $p$. 一个排列中，所有非特殊元素的位置，以及所有特殊元素所占据的位置集合，都是唯一的.因此，$\text{骨架}_1$ 和 $\text{骨架}_2$ 必须具有相同的结构, 即相同的非特殊元素排列和相同的特殊元素占位.又因为在“骨架”排列的定义中, 特殊元素的相对顺序是固定的, 所以 $\text{骨架}_1$ 必须等于 $\text{骨架}_2$. 既然骨架相同，而最终结果 $p$ 也相同, 那么施加在骨架上的“内部重排”操作也必须相同, 即 $\text{重排}_1$ 等于 $\text{重排}_2$. 这证明了每一种构造组合都唯一地对应一个最终排列.

上述论证表明，我们建立了一个从“构造步骤对”到“全排列集合 $\mathcal{U}$” 的一一对应关系.因此，它们的大小必然相等： <MathBlock raw={"|\mathcal{U}| = N \times m!"} /> 我们已知 $|\mathcal{U}| = n!$，所以 <MathBlock raw={"n! = N \times m!"} /> 由此解出我们最初的目标 $N$: <MathBlock raw={"N = \frac{n!}{m!}"} /> 这个推导从根本上揭示了倍缩策略的本质：它不是简单的除法，而是对乘法原理方程 $n! = N \times m!$ 的求解.

从另一个角度看，这个过程等价于将 $n!$ 个全排列进行分组或划分. 我们将所有排列按照“除了 $m$ 个特殊元素的内部顺序外，其他一切都相同”的规则进行分组. 例如，排列 $(e_2, x, e_1, y)$ 和 $(e_1, x, e_2, y)$ 就属于同一组, 因为它们的骨架（非 $e$ 元素的位置和 $e$ 元素所占的位置）是相同的. 每一组内有多少个排列？这恰好等于这 $m$ 个特殊元素自身的全排列数, 即 $m!$ 个. 而题目要求的“定序排列”是什么？它恰好是每一组中那唯一一个满足特定顺序的排列. 因此，符合条件的排列总数 $N$，就等于这个分组的数量. 根据除法原理，分组的数量为： <MathBlock raw={"N = \frac{\text{总元素数}}{\text{每组的元素数}} = \frac{n!}{m!}"} /> 这两种视角都严谨地证明了倍缩策略的正确性.它将一个带有复杂“相对顺序”约束的问题，转化为一个结构清晰的、关于等价类的计数问题.

倍缩策略

若在一组共 $n$ 个元素的排列中, 有 $m$ 个特定元素被要求保持固定的相对顺序，则符合条件的排列数可以通过以下方式计算：

1. 计算这 $n$ 个元素的全排列数, 即 $n!$.
2. 这 $m$ 个被定序的元素在上述全排列中, 自身有 $m!$ 种不同的排列方式.
3. 由于约束只允许这 $m!$ 种排列中的一种, 我们将总数除以 $m!$.

最终的排列数为 $\dfrac{n!}{m!}$. 如果有多组元素被定序，则需除以各组元素内部全排列数的乘积.

2024年1月浙江省宁波九校联考

体育课上，罗老师让8名身高各不相同的同学排队，要求排成前后两排，每排4人，且每排同学从左到右身高依次递增，则不同排法的种数为（ ）. \begin{multicols}{4}

[label=\Alph*.]

1. 60
2. 70
3. 80
4. 90

\end{multicols}

解

此问题的核心在于，一旦确定了哪些同学在前排、哪些同学在后排，那么由于“身高依次递增”的严格约束，每一排的站位顺序就唯一确定了.因此，问题的本质从一个排列问题，退化为了一个分组或组合问题.

我们的任务可以简化为：将8名独一无二的同学分成两组，一组是“前排组”，另一组是“后排组”，每组4人.

我们可以通过确定“前排组”的人选来完成这个任务.从8名同学中选出4名到前排，这是一个组合问题，其方法数为 <MathBlock raw={"\binom{8}{4} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70"} /> 一旦这4名同学被选定，他们只能以身高从低到高的一种方式站立.

剩下的 $8-4=4$ 名同学自动成为“后排组”，同样，他们的站立方式也只有一种.

根据乘法原理，总的排法数就是分组的方法数，即 $70 \times 1 \times 1 = 70$.

我们也可以从倍缩策略的角度来理解这个问题，这种视角更能揭示其排列的本质.

首先，我们不考虑任何身高顺序的限制，将8名同学安排到8个具体的位置上（4个前排位置，4个后排位置）.这相当于8名同学的全排列，总方法数为 $8!$.

现在我们引入约束条件. 对于最终被安排在前排的4名同学，无论他们是谁，在我们的 $8!$ 种总排列中, 他们在这4个前排位置上可以有 $4!$ 种不同的排列方式.然而, 题目要求他们必须按身高递增排列, 这只是 $4!$ 种排列中的一种.因此, 我们对前排的排列多算了 $4!$ 倍.

同理，对于最终被安排在后排的4名同学，他们的顺序也被唯一确定，所以我们对后排的排列也多算了 $4!$ 倍.

根据倍缩策略，我们将总排列数除以这两个重复的倍数，得到符合条件的排法数： <MathBlock raw={"N = \frac{8!}{4! \times 4!} = \frac{40320}{24 \times 24} = \frac{40320}{576} = 70"} /> 这与我们从组合角度得到的结果完全一致.故选B.

2008 安徽理

12名同学合影，站成前排4人后排8人，现摄影师要从后排8人中抽2人调整到前排，若其他人的相对顺序不变，则不同调整方式的种数是（ ）. \begin{multicols}{4}

[label=\Alph*.]

1. $C_8^2 A_3^2$
2. $C_8^2 A_6^6$
3. $C_8^2 A_6^2$
4. $C_8^2 A_5^2$

\end{multicols}

解

此问题可以分解为两个独立且连续的步骤：首先是“选人”，然后是“排位”.

第一步是选人. 摄影师需要从后排的8名同学中选出2人调到前排.这是一个组合问题，因为此时我们只关心选出的是哪两个人，而不涉及他们的顺序. 选人的方法数为 <MathBlock raw={"\binom{8}{2}"} />

第二步是排位. 调整后，前排将有 $4+2=6$ 名同学.这6名同学由原来的4位和新选出的2位构成. 后排则剩下 $8-2=6$ 名同学.

问题的核心约束是“其他人的相对顺序不变”. 这意味着：

• 原前排4人的相对顺序保持不变.

• 原后排剩下的6人的相对顺序也保持不变.

  由于后排6人的位置和相对顺序都已固定，我们只需考虑前排这6人的新排法.

  在前排的6个位置上，我们需要安排4名“旧”同学和2名“新”同学.其中，4名“旧”同学的相对顺序是固定的.这是一个典型的定序问题.

  我们可以使用插空法的思想来解决排位问题. 前排的6个位置可以看作6个空位.我们需要为新选出的2名同学选择位置. 为第一位新同学选择位置，有6个选择. 为第二位新同学选择位置，有5个选择. 由于这两位新同学是不同的个体，他们的顺序是重要的. 因此，为这两位新同学安排位置的方法数是一个排列问题，共有 <MathBlock raw={"A(6,2) = 6 \times 5 = 30"} /> 一旦这两位新同学的位置确定，剩下的4个位置将由4名“旧”同学按他们原有的相对顺序依次填入，方法只有1种.

  或者，我们也可以运用倍缩策略来思考排位问题. 如果不考虑任何顺序限制，将这6名同学（4旧2新）排在前排6个位置上，共有 $6!$ 种方法. 但是，题目要求4名“旧”同学的相对顺序不变.在这 $6!$ 种排列中, 这4名“旧”同学自身有 $4!$ 种排列方式，而我们只接受其中的1种. 因此，符合条件的排法数为 <MathBlock raw={"\frac{6!}{4!} = \frac{720}{24} = 30 = A(6,2)"} />

  最后，根据乘法原理，将“选人”和“排位”两个步骤的方法数相乘，得到总的调整方式种数： <MathBlock raw={"N = \binom{8}{2} \times A(6,2)"} /> 在题目选项的记法中，即为 $C_8^2 A_6^2$.故选C.

重复元素的排列

计算由单词 \texttt{MISSISSIPPI} 中所有字母构成的不同排列（字符串）的数量.

解

这个问题引入了一种新的复杂性：元素中存在重复. 单词 \texttt{MISSISSIPPI} 共包含11个字母，但它们并非各不相同. 具体的构成为：1个 M, 4个 I, 4个 S, 2个 P.

直接应用排列公式是行不通的，因为它要求所有元素都是可区分的. 然而，我们可以借助倍缩策略，通过一个思想实验来解决此问题.

首先，我们假想所有的字母都是可区分的. 我们可以给相同的字母加上下标来区分它们，例如： <MathBlock raw={"M_1, I_1, S_1, S_2, I_2, S_3, S_4, I_3, P_1, P_2, I_4"} /> 现在我们拥有11个完全不同的对象，将它们进行全排列，总方法数为 $11!$.

接下来，我们考虑去除下标，回到原始问题. 当我们这样做时，会发生什么情况？ 考虑任意一个具体的排列，例如 $S_1 I_1 P_1 M_1 I_2 S_2 S_3 I_3 P_2 S_4 I_4$. 现在我们关注其中的4个I ($I_1, I_2, I_3, I_4$). 在这个排列的特定位置上, 这4个I自身可以有 $4!$ 种不同的排列方式（例如 $I_2$ 和 $I_1$ 交换位置）. 在我们假想的“可区分”世界里, 这些都是不同的排列. 但在现实世界中, 由于所有的I都是一样的, 这 $4!$ 种排列都对应着同一个字符串 \texttt{SIPMISSSIPSI}.

这意味着，我们最初计算的 $11!$ 对每一个最终的、唯一的字符串, 都因为I的存在而重复计数了 $4!$ 倍. 因此, 我们必须用总数除以 $4!$ 来消除这种由I引起的重复.

同理，对于4个S，我们也重复计数了 $4!$ 倍. 对于2个P，我们重复计数了 $2!$ 倍.

根据倍缩策略，我们将总的假想排列数，除以由每种重复元素内部排列所产生的重复倍数. <MathBlock raw={"N = \frac{11!}{4! \times 4! \times 2! \times 1!} = \frac{39916800}{(24) \times (24) \times (2) \times (1)} = \frac{39916800}{1152} = 34650"} /> 所以，共有34650个不同的排列.

此例导出了一个普遍的结论：对于包含 $n$ 个对象的多重集, 其中有 $k_1$ 个第一类相同对象, $k_2$ 个第二类相同对象, ..., $k_m$ 个第 $m$ 类相同对象（其中 $k_1+k_2+...+k_m=n$），其不同的排列数为 <MathBlock raw={"\binom{n}{k_1, k_2, ..., k_m} = \frac{n!}{k_1!k_2!\cdots k_m!}"} /> 这正是我们之前遇到的多项式系数. 倍缩策略为其提供了一个至关重要的组合解释.

圆排列

将 $n$ 位不同的宾客安排在一个圆形的餐桌旁就座，有多少种不同的就座方式？（如果两种就座方式中，每位宾客的左邻和右邻都完全相同，则认为这两种方式是相同的.）

解

这个问题是典型的圆排列问题. 其核心在于，圆桌没有“起点”或“终点”的概念，排列的评价标准从绝对位置变为了相对位置.

我们再次运用倍缩策略，从一个更简单、我们熟知的线性排列开始.

首先，我们暂时忽略圆桌的特性，想象将这 $n$ 位宾客排成一条直线. 我们可以轻易得到, 总的线性排列数为 $n!$.

现在，我们将任意一个线性排列，例如 $(P_1, P_2, ..., P_n)$， “弯曲”成一个圆圈，使其首尾相连. 考虑这个线性排列通过“旋转”可以得到哪些其他的线性排列？ <MathBlock raw={"\begin{aligned} (P_1, P_2, P_3, ..., P_n) (P_n, P_1, P_2, ..., P_{n-1}) (P_{n-1}, P_n, P_1, ..., P_{n-2}) \vdots (P_2, P_3, P_4, ..., P_1) \end{aligned}"} /> 通过 $n$ 次旋转, 我们得到了 $n$ 个不同的线性排列. 然而, 当我们将它们都布置到圆桌上时, 它们描述的是同一种就座方式. 为什么？因为在每一种情况中, $P_1$ 的左边总是 $P_n$、右边总是 $P_2$；$P_2$ 的左边总是 $P_1$、右边总是 $P_3$，以此类推. 相对位置关系是完全一样的.

这揭示了一个关键事实：我们最初计算的 $n!$ 种线性排列, 可以将它们 $n$ 个一组进行划分. 每一组中的 $n$ 个线性排列，都对应着同一个圆排列. 因此，我们的初始计数 $n!$ 将每一种真正的圆排列都重复计算了 $n$ 倍.

根据倍缩策略，我们将线性排列总数除以这个重复的倍数 $n$，即可得到圆排列的数目. <MathBlock raw={"N = \frac{n!}{n} = (n-1)!"} /> 所以，有 $(n-1)!$ 种不同的就座方式.

延伸思考：项链问题. 如果不是安排宾客，而是将 $n$ 颗不同的珠子串成一条项链，有多少种不同的方法？项链不仅可以旋转，还可以从空间中拿起来翻转. 对于 $n\>2$ 的情况, 每一次翻转都会将一个圆排列变成它的“镜像”排列. 除非一个排列本身是左右对称的（这种情况较为特殊）, 否则一个排列和它的镜像排列是不同的圆排列, 但对应的是同一条项链. 因此, 除了极少数对称情况, 我们之前的计数 $(n-1)!$ 又将每条项链重复计算了2倍（其自身和其镜像）. 对于大多数非对称的项链，其方法数是 $\dfrac{(n-1)!}{2}$.

棋盘问题*

在一个 $m \times n$ 的棋盘格上, 一个棋子从左下角 $(0,0)$ 出发, 要到达右上角 $(m,n)$. 如果每次只能向上或向右移动一个单位，总共有多少条不同的最短路径？

解

这是一个经典的格路计数问题，可以通过多种方式来解决，而倍缩策略提供了一种非常直观且深刻的视角.

首先，我们分析路径的构成. 任何一条从 $(0,0)$ 到 $(m,n)$ 的最短路径, 都必须包含 $m$ 次向右的移动（我们记作 R）和 $n$ 次向上的移动（我们记作 U）. 因此，每一条不同的路径都唯一地对应着一个由 $m$ 个 R 和 $n$ 个 U 构成的序列, 该序列的总长度为 $m+n$.

例如，在 $2 \times 1$ 的棋盘上, 从 $(0,0)$ 到 $(2,1)$ 的路径：

• 路径 $(0,0) \to (1,0) \to (2,0) \to (2,1)$ 对应序列 \texttt{RRU}.

• 路径 $(0,0) \to (1,0) \to (1,1) \to (2,1)$ 对应序列 \texttt{RUR}.

• 路径 $(0,0) \to (0,1) \to (1,1) \to (2,1)$ 对应序列 \texttt{URR}.

  于是，原问题就转化为：计算由 $m$ 个 R 和 $n$ 个 U 构成的不同序列的数量.

  这是一个带有重复元素的排列问题，正是倍缩策略的用武之地.

  我们想象有 $m+n$ 次移动, 它们分别是 $R_1, R_2, ..., R_m$ 和 $U_1, U_2, ..., U_n$. 将这 $m+n$ 个不同的操作进行全排列, 总方法数为 $(m+n)!$.

  在现实问题中，所有的向右移动 R 是没有区别的，所有的向上移动 U 也是没有区别的. 在我们假想的 $(m+n)!$ 种排列中, 那 $m$ 个不同的向右操作 $R_1, ..., R_m$ 自身可以有 $m!$ 种不同的排列方式. 但这些都对应着同一个由 $m$ 个 R 组成的移动模式. 因此, 我们的计数因 R 的存在而重复了 $m!$ 倍.

  同理，我们的计数也因 U 的存在而重复了 $n!$ 倍.

  我们将总的假想排列数除以由重复元素产生的倍数，得到最终的路径数： <MathBlock raw={"N = \frac{(m+n)!}{m!n!}"} />

  我们立刻认出，这个结果就是组合数 $\binom{m+n}{m}$ 或 $\binom{m+n}{n}$. 这为组合数提供了一个全新的、极其重要的组合解释： <MathBlock raw={"\binom{m+n}{m} = \text{从 (0,0) 到 (m,n) 的格路数}"} />

  另一种组合视角： 我们也可以直接用组合的定义来解决. 一条路径总共需要 $m+n$ 步. 我们只需要在这 $m+n$ 步中，决定哪几步是向右移动（R），剩下的就自动是向上移动（U）. 从 $m+n$ 个总步数中, 选出 $m$ 步来执行向右移动，方法数为 <MathBlock raw={"\binom{m+n}{m}"} /> 这与倍缩策略得到的结果完全一致，再次印证了倍缩策略与组合定义的内在统一性. 这种将排列问题转化为序列编码，再利用倍缩策略求解的方法，是组合数学中一种非常强大的通用技巧.

2024年1月湖南省邵阳市高三第一次联考

城步苗族自治县“六月六山歌节”是湖南省四大节庆品牌之一，至今已举办25届.假设在即将举办的第26届“六月六山歌节”中，组委会要在原定排好的10个“本土歌舞”节目中增加2个“歌王对唱”节目.若保持原来10个节目的相对顺序不变，则不同的排法种数为（ ）. \begin{multicols}{4}

[label=\Alph*.]

1. 110
2. 144
3. 132
4. 156

\end{multicols}

解

问题的核心约束在于“保持原来10个节目的相对顺序不变”. 这意味着，如果我们把原来的10个节目记为 $O_1, O_2, ..., O_{10}$, 那么在最终的节目单中, $O_1$ 必须出现在 $O_2$ 之前, $O_2$ 必须出现在 $O_3$ 之前，以此类推. 这是一个典型的定序问题，非常适合使用倍缩策略来解决.

在增加了2个新的“歌王对唱”节目后（我们视这两个新节目为不同的个体 $N_1, N_2$）, 总的节目数量为 $10+2=12$ 个.

法一：倍缩策略

首先，我们忽略“相对顺序不变”的约束，考虑将这12个不同的节目进行全排列. 总的排列方法数为 <MathBlock raw={"12!"} />

现在，我们引入约束条件. 在上述 $12!$ 种排列中, 那10个原来的节目自身可以有 $10!$ 种不同的内部排列方式. 然而，题目要求只接受它们“按原有顺序”排列的那一种.

这意味着，对于任何一种满足条件的最终排法，我们最初的 $12!$ 计数都将其重复计算了 $10!$ 次（因为这 $10!$ 次内部重排都被我们算作了不同的情况）. 因此，我们必须用总排列数除以这个重复的倍数.

符合条件的排法种数为 <MathBlock raw={"N = \frac{12!}{10!} = \frac{12 \times 11 \times (10!)}{10!} = 12 \times 11 = 132"} />

法二：选位法 (插空思想的变体)

我们也可以从构造的角度来思考这个问题. 总共有12个节目位置需要安排. 问题的本质可以转化为：先为2个新节目选择位置，剩下的位置自然就由10个旧节目按照它们固有的顺序填充.

第一步：为2个新节目选择位置. 我们需要从12个可用的时间槽中，为2个不同的新节目选定它们的表演位置. 这相当于从12个位置中选出2个进行排列. 方法数为 <MathBlock raw={"A(12, 2) = 12 \times 11 = 132"} />

第二步：安排10个旧节目. 一旦新节目的位置被确定，就只剩下 $12-2=10$ 个空位. 由于这10个旧节目的相对顺序是固定的，它们填充这10个空位的方式是唯一确定的. 方法数为1.

根据乘法原理，总的排法种数为 $A(12, 2) \times 1 = 132$.

两种方法殊途同归，都得到了相同的结果. 故选C.

变式一：待插入元素相同

沿用上题背景，假设增加的2个“歌王对唱”节目是完全相同的（例如，都是同一首歌的两个不同时段重播），若仍要保持原来10个节目的相对顺序不变，则不同的排法种数为（ ）. \begin{multicols}{4}

[label=\Alph*.]

1. 55
2. 66
3. 78
4. 132

\end{multicols}

解

这个问题与原题的核心区别在于，新增的2个节目从“可区分”变为了“不可区分”. 这个变化直接影响了我们计数的方式.

法一：选位法 (组合思想)

总共有12个节目位置. 我们的任务是为2个相同的新节目选择位置. 由于新节目是相同的，我们选择 {第3位, 第8位} 和选择 {第8位, 第3位} 最终产生的节目单是完全一样的. 因此，这不再是一个排列问题，而是一个纯粹的组合问题.

我们需要从12个可用的位置中，选出2个位置来安放这两个相同的新节目. 方法数为 <MathBlock raw={"\binom{12}{2} = \frac{12 \times 11}{2 \times 1} = 66"} />

一旦新节目的位置被确定，剩下的10个位置将由10个旧节目按照它们固有的顺序唯一地填充. 根据乘法原理，总排法种数为 $\binom{12}{2} \times 1 = 66$.

法二：倍缩策略的叠加应用

我们从12个节目全排列出发，总数为 $12!$.

首先，应用第一个约束：10个旧节目的相对顺序不变. 这意味着我们将总数除以 $10!$ 来消除这10个节目内部顺序的重复计数. <MathBlock raw={"N_1 = \frac{12!}{10!}"} />

接着，应用第二个约束：2个新节目是完全相同的. 这意味着在上述结果中，我们仍然将这两个新节目视为可区分的，从而对它们自身的 $2!$ 种排列进行了重复计数. 因此, 我们必须再次应用倍缩策略, 除以 $2!$.

最终的排法种数为 <MathBlock raw={"N = \frac{12!}{10! \times 2!} = \frac{A(12,2)}{2!} = \frac{132}{2} = 66"} />

这个结果正是组合数 $\binom{12}{2}$ 的定义. 这深刻揭示了组合数 $\binom{n}{k}$ 的一个本质：它是在 $n$ 个对象的排列中, 同时对“选出的 $k$ 个元素”和“未选的 $n-k$ 个元素”施加定序（或视其为相同）约束的结果. 故选B.

变式二：增加不相邻约束

沿用原题背景，即增加的2个“歌王对唱”节目是不同的. 若不仅要保持原来10个节目的相对顺序不变，还要求这两个新增的“歌王对唱”节目不能相邻，则不同的排法种数为（ ）. \begin{multicols}{4}

[label=\Alph*.]

1. 110
2. 120
3. 121
4. 132

\end{multicols}

解

这个问题在原题的基础上，增加了一个“不相邻”的约束. 这种“定序”与“不相邻”的复合约束，是插空法与倍缩思想结合的经典场景.

法一：插空法

处理“不相邻”问题的最直接方法是插空法. 在这里，10个旧节目是“骨架”，2个新节目是等待插入的元素.

第一步：排列骨架. 我们要先安排10个旧节目. 由于它们的相对顺序是固定的，因此排列它们的方法只有一种. <MathBlock raw={"O_1, O_2, O_3, O_4, O_5, O_6, O_7, O_8, O_9, O_{10}"} />

第二步：创造空隙. 这10个排好的节目，形成了11个可供插入的空隙 (包括最前和最后). <MathBlock raw={"\_ O_1 \_ O_2 \_ ... \_ O_{10} \_"} />

第三步：插入元素. 我们需要将2个不同的新节目插入到这11个空隙中，每个空隙至多放一个节目，以保证它们不相邻. 这相当于从11个空隙中选出2个，并将2个不同的节目排列进去. 这是一个排列问题. 方法数为 <MathBlock raw={"A(11, 2) = 11 \times 10 = 110"} />

根据乘法原理，总的排法种数为 $1 \times A(11,2) = 110$.

法二：补集思想 (正难则反)

我们也可以从原问题的总数中，减去不满足“不相邻”约束的情况，即减去“2个新节目必须相邻”的情况.

原问题（只要求旧节目定序）的总排法数，我们已经计算过是 $132$.

现在计算“旧节目定序”且“新节目相邻”的排法数. 我们可以使用捆绑法. 将2个不同的新节目捆绑成一个“大节目块”. 这个“大节目块”内部，2个新节目可以有 $2! = 2$ 种排列方式.

现在的问题转化为：将这个“大节目块”和10个旧节目进行排列，同时保持10个旧节目的相对顺序不变. 这等价于将1个“大节目块”插入到10个旧节目形成的11个空隙（包括首尾）中. 选择插入位置的方法数有 $\binom{11}{1} = 11$ 种.

因此，“新节目相邻”的排法数为 <MathBlock raw={"N_{\text{相邻}} = (\text{内部排列}) \times (\text{外部插入}) = 2! \times \binom{11}{1} = 2 \times 11 = 22"} />

最后，用总数减去相邻数： <MathBlock raw={"N_{\text{不相邻}} = N_{\text{总}} - N_{\text{相邻}} = 132 - 22 = 110"} />

两种方法再次得到了一致的结果. 故选A.

分组问题

在组合计数中，一类核心问题是将一个包含 $n$ 个不同元素的集合，划分成若干个互不相交的子集（即“组”）. 解决这类问题的关键，在于精确辨析一个核心要素：这些最终形成的“组”，本身是可区分的还是不可区分的？

我们通过一个场景来引入这两种模型的根本差异. 想象有6本完全不同的书，需要将它们分成三份，每份2本.

• 情景一： 将这些书分给甲、乙、丙三个人，每人2本.
• 情景二： 将这些书打包成三份，每份2本，堆在桌子上.

\begin{figure}[htbp]

TikZ 图 116

\end{figure} 图：有序分组：组是可区分的

\begin{figure}[htbp]

TikZ 图 117

\end{figure} 图：无序分组：组是不可区分的

有序分组

在情景一中，最终分到书的三个人“甲、乙、丙”是明确可区分的. 甲拿到 $\{B_1, B_2\}$ 和乙拿到 $\{B_1, B_2\}$ 是两种完全不同的分配结果. 因此，这些“组”因为其归属（甲、乙、丙）而被赋予了身份，是可区分的. 我们称之为有序分组或定序分组.

计算这类问题的过程是一个连续的组合决策：

• 首先，从6本书中为甲选出2本，方法数为 $\binom{6}{2}$.
• 接着，从剩下的4本书中为乙选出2本，方法数为 $\binom{4}{2}$.
• 最后，剩下的2本书自动归丙所有，方法数为 $\binom{2}{2}$.

根据乘法原理，总的分配方法数为 <MathBlock raw={"N_1 = \binom{6}{2}\binom{4}{2}\binom{2}{2} = \frac{6 \times 5}{2} \times \frac{4 \times 3}{2} \times 1 = 15 \times 6 \times 1 = 90"} /> 我们将这个结果用阶乘形式展开，可以观察到其本质： <MathBlock raw={"\frac{6!}{2!4!} \times \frac{4!}{2!2!} \times \frac{2!}{2!0!} = \frac{6!}{2!2!2!}"} /> 这正是将6个不同元素分成大小为2, 2, 2的三个有序组的方法数，其形式与多项式系数完全一致.

有序分组模型

将 $n$ 个不同元素分成 $m$ 个可区分的组（例如, 分配给 $m$ 个不同的人, 或放入 $m$ 个有标签的盒子）, 各组的元素个数分别为 $k_1, k_2, ..., k_m$ (其中 $\sum k_i = n$)，其总方法数为 <MathBlock raw={"N = \binom{n}{k_1}\binom{n-k_1}{k_2}\cdots\binom{k_m}{k_m} = \frac{n!}{k_1!k_2!\cdots k_m!}"} />

证明

我们通过一个构造性的论证来证明此公式的正确性.其核心思想是将“完成一次有序分组”这一任务，分解为一系列连续且独立的组合选择，然后应用乘法原理.

设原始集合为 $S$, 包含 $n$ 个不同的元素. 我们的目标是将其划分为 $m$ 个有序的子集 $G_1, G_2, ..., G_m$, 使得对任意 $i=1, ..., m$, 子集 $G_i$ 的大小为 $|G_i|=k_i$.

我们可以按顺序为这 $m$ 个可区分的组选择它们的成员：

首先，为第一个组 $G_1$ 选择成员. 我们需要从 $S$ 中的 $n$ 个元素里, 不计顺序地选出 $k_1$ 个. 根据组合数的定义，完成这一步的方法数为 <MathBlock raw={"\binom{n}{k_1}"} />

在确定了 $G_1$ 的成员后, 集合 $S$ 中还剩下 $n-k_1$ 个元素可供分配. 接下来, 我们为第二个组 $G_2$ 选择成员. 我们需要从这 $n-k_1$ 个剩余元素中, 选出 $k_2$ 个. 方法数为 <MathBlock raw={"\binom{n-k_1}{k_2}"} />

这个过程依次进行. 当我们为第 $i$ 个组 $G_i$ 选择成员时, 已有 $k_1+k_2+...+k_{i-1}$ 个元素被分配. 因此, 我们需要从剩下的 $n - \sum_{j=1}^{i-1} k_j$ 个元素中, 选出 $k_i$ 个.

直至最后一个组 $G_m$, 此时剩下的元素数量为 $n - \sum_{j=1}^{m-1} k_j = k_m$. 我们需要从这 $k_m$ 个元素中选出 $k_m$ 个, 方法数为 $\binom{k_m}{k_m}=1$.

由于整个分组任务必须完成所有这些步骤，根据乘法原理，总的方法数 $N$ 是每一步方法数的乘积. <MathBlock raw={"N = \binom{n}{k_1}\binom{n-k_1}{k_2}\cdots\binom{n - \sum_{j=1}^{m-2} k_j}{k_{m-1}}\binom{k_m}{k_m}"} /> 这便证明了公式的第一个等式.

为了推导其更为简洁的阶乘形式，我们将每一个组合数用其阶乘定义展开. <MathBlock raw={"\begin{aligned} N &= \frac{n!}{k_1!(n-k_1)!} \times \frac{(n-k_1)!}{k_2!(n-k_1-k_2)!} \times ... \times \frac{(k_m)!}{k_m!(k_m-k_m)!} &= \frac{n!}{k_1!\cancel{(n-k_1)!}} \times \frac{\cancel{(n-k_1)!}}{k_2!\cancel{(n-k_1-k_2)!}} \times ... \times 1 \end{aligned}"} /> 我们观察到，前一项分母中的阶乘项，恰好被后一项的分子所抵消. 这种级联式的约分会一直持续到最后.

最终，所有中间的阶乘项都被消去，只剩下最初的分子 $n!$ 和每一项分母中代表各组大小的阶乘 $k_i!$. <MathBlock raw={"N = \frac{n!}{k_1!k_2!\cdots k_m!}"} /> 这与多项式系数的形式完全吻合.

例

某学校的志愿者社团共有9名成员，需要将他们分配到 A, B, C 三个不同的社区服务中心. A 中心需要2名成员，B 中心需要3名成员，C 中心需要4名成员. 问共有多少种不同的分配方案？

解

此问题要求将9名不同的成员分配到三个可区分的中心，且每个中心所需的人数已经确定. 这构成了一个有序分组问题. 我们可以将分配过程视为一个连续的决策步骤.

首先，为 A 中心从9名成员中选派2人. 这是一个组合问题，因为成员在此步骤中仅被选中，其顺序无关紧要. 方法数为 <MathBlock raw={"\binom{9}{2}"} /> 接着，需从余下的 $9-2=7$ 名成员中，为 B 中心选派3人. 方法数为 <MathBlock raw={"\binom{7}{3}"} /> 最后，剩下的 $7-3=4$ 名成员将全部被派往 C 中心，这是一种必然的结果. 方法数为 <MathBlock raw={"\binom{4}{4}"} /> 根据乘法原理，完成整个分配任务的总方案数是上述所有步骤方法数的乘积. <MathBlock raw={"N = \binom{9}{2}\binom{7}{3}\binom{4}{4} = \frac{9 \times 8}{2 \times 1} \times \frac{7 \times 6 \times 5}{3 \times 2 \times 1} \times 1 = 36 \times 35 \times 1 = 1260"} />

此结果亦可直接通过有序分组的通用公式得到. 将 $n=9$ 个元素分成大小为 $k_1=2, k_2=3, k_3=4$ 的可区分的三组，其方法数由多项式系数给出. (为何这个公式是适用的？) <MathBlock raw={"\binom{9}{2,3,4} = \frac{9!}{2!3!4!} = \frac{362880}{2 \times 6 \times 24} = \frac{362880}{288} = 1260"} /> 两种计算路径的结果是一致的. 故共有1260种不同的分配方案.

例

将5名新入职的员工分配到三个不同的项目中，其中项目A需要1名员工，项目B需要2名员工，项目C需要2名员工. 问有多少种不同的分配方案？

解

此任务的核心是将5名可区分的员工，分配到三个可区分的项目（A, B, C）中. 这是一个有序分组问题，即使其中两个项目所需的人数相同（均为2人），项目本身（B与C）的差异性使得分组是有序的. (若项目B和C是无法区分的，结果会如何变化？)

我们可以采用连续组合选择的方式来解决. 首先，为项目A从5名员工中选定1人. 方法数为 <MathBlock raw={"\binom{5}{1} = 5"} /> 接着，为项目B从剩下的4名员工中选定2人. 方法数为 <MathBlock raw={"\binom{4}{2} = \frac{4 \times 3}{2} = 6"} /> 最后，剩下的2名员工自动被分配到项目C. 方法数为 <MathBlock raw={"\binom{2}{2} = 1"} /> 依据乘法原理，总的分配方案数为 <MathBlock raw={"N = \binom{5}{1}\binom{4}{2}\binom{2}{2} = 5 \times 6 \times 1 = 30"} />

作为对比，我们也可以直接应用有序分组的公式. 将 $n=5$ 个元素分成大小为 $k_1=1, k_2=2, k_3=2$ 的三组，其方法数为 <MathBlock raw={"\binom{5}{1,2,2} = \frac{5!}{1!2!2!} = \frac{120}{1 \times 2 \times 2} = 30"} /> 两种路径再次导向了相同的结果. 故共有30种不同的分配方案.

例

在一副标准的52张扑克牌（所有牌均不相同）中，将所有牌平均发给东、南、西、北四位玩家，每位玩家获得13张牌. 问总共有多少种不同的发牌结果？

解

此问题要求将52张不同的牌，分配给四个可区分的玩家. 这是一个将 $n=52$ 个不同元素分成四组, 每组大小均为 $k=13$ 的有序分组问题.

我们可以模拟发牌的连续过程来构建解决方案. 首先，为“东”这位玩家从52张牌中发出13张. 方法数为 <MathBlock raw={"\binom{52}{13}"} /> 接着，为“南”这位玩家从剩下的 $52-13=39$ 张牌中发出13张. 方法数为 <MathBlock raw={"\binom{39}{13}"} /> 然后，为“西”这位玩家从剩下的 $39-13=26$ 张牌中发出13张. 方法数为 <MathBlock raw={"\binom{26}{13}"} /> 最后，剩下的13张牌全部发给“北”这位玩家. 方法数为 <MathBlock raw={"\binom{13}{13}"} /> 根据乘法原理，总的发牌结果数为 <MathBlock raw={"N = \binom{52}{13}\binom{39}{13}\binom{26}{13}\binom{13}{13}"} />

现在，我们利用有序分组的通用公式，从一个更宏观的视角来验证这个结果. 该问题是把 $n=52$ 个元素分成大小分别为 $k_1=13, k_2=13, k_3=13, k_4=13$ 的四个可区分的组. 其总方法数由以下公式直接给出： <MathBlock raw={"N = \frac{52!}{13!13!13!13!} = \frac{52!}{(13!)^4}"} />

我们有必要验证这两种表达方式的等价性，这有助于加深对公式本质的理解. <MathBlock raw={"\begin{aligned} \binom{52}{13}\binom{39}{13}\binom{26}{13}\binom{13}{13} &= \frac{52!}{13!(52-13)!} \cdot \frac{39!}{13!(39-13)!} \cdot \frac{26!}{13!(26-13)!} \cdot \frac{13!}{13!(13-13)!} &= \frac{52!}{13! \cdot 39!} \cdot \frac{39!}{13! \cdot 26!} \cdot \frac{26!}{13! \cdot 13!} \cdot \frac{13!}{13! \cdot 0!} &= \frac{52!}{13! \cdot \cancel{39!}} \cdot \frac{\cancel{39!}}{13! \cdot \cancel{26!}} \cdot \frac{\cancel{26!}}{13! \cdot 13!} \cdot 1 (\text{注意 } 0!=1) &= \frac{52!}{13! \cdot 13! \cdot 13! \cdot 13!} \end{aligned}"} /> 两种方法的结果完全吻合. 最终的结果是一个天文数字，通常无需计算其具体值，以阶乘或组合数的形式表示即可.

无序分组

现在，我们转向情景二. 在这里，我们只是将书打包成三份，这些“份”或“堆”之间没有任何身份标签，它们是不可区分的. 例如，分组结果 $\{\{B_1,B_2\}, \{B_3,B_4\}, \{B_5,B_6\}\}$ 与 $\{\{B_3,B_4\}, \{B_1,B_2\}, \{B_5,B_6\}\}$ 是完全相同的一种分组，因为它们都只是把这六本书分成了同样的三堆.

直接计算无序分组是困难的，但我们可以借助有序分组的结果和倍缩策略. 我们不妨先假装这些组是有区别的，比如给它们贴上A, B, C的标签. 正如我们所计算的，这样做有90种方法.

现在我们来分析，这种“贴标签”的操作导致了多少倍的重复计数. 考虑一个具体的无序分组结果，例如 $G = \{\{B_1,B_2\}, \{B_3,B_4\}, \{B_5,B_6\}\}$. 在我们的有序分组计数中，这个单一的结果被我们重复计算了多少次？它对应于将A, B, C三个标签分配给这三个小组的全部分配方式.

• (A: $\{B_1,B_2\}$, B: $\{B_3,B_4\}$, C: $\{B_5,B_6\}$)
• (A: $\{B_1,B_2\}$, C: $\{B_3,B_4\}$, B: $\{B_5,B_6\}$)
• ...

将A, B, C三个标签进行全排列，共有 $3! = 6$ 种方式. 这意味着, 每一个我们真正想要的无序分组, 在有序分组的计算中都被重复计数了 $3!$ 次.

因此，根据倍缩策略，我们必须用有序分组的结果除以这个重复的倍数. <MathBlock raw={"N_2 = \frac{N_1}{3!} = \frac{\binom{6}{2}\binom{4}{2}\binom{2}{2}}{3!} = \frac{90}{6} = 15"} /> 所以，将6本不同的书分成无法区分的三堆，每堆2本，只有15种方法.

这个思想可以推广. 如果我们将 $n$ 个元素分组, 其中有 $m$ 个组的大小完全相同, 那么在计算有序分组后, 需要除以 $m!$ 来消除这些相同大小的组之间的顺序所带来的重复.

无序分组模型

将 $n$ 个不同元素分组.

1. 各组大小均不相同: 若各组大小为 $k_1, k_2, ..., k_m$ 且彼此不等, 则无序分组与有序分组的结果相同, 为 $\dfrac{n!}{k_1!k_2!\cdots k_m!}$. (因为组的大小本身就成为了它们的天然“标签”)
2. 部分组大小相同: 若其中有 $m_1$ 个组的大小为 $k_1$, $m_2$ 个组的大小为 $k_2$, ..., 则总方法数为 <MathBlock raw={"N = \frac{\binom{n}{...}}{m_1! m_2! \cdots} = \frac{n!}{(k_1!)^{m_1}(k_2!)^{m_2}\cdots (m_1!)(m_2!)\cdots}"} /> 简而言之，先按有序分组计算，然后对每一类“大小相同的组”，除以该类组数的阶乘.

例

将6个颜色互不相同的球全部放入三个完全相同的盒子里，每个盒子里至少放一个球且数目不同，则不同的放球方法有（ ）种. \begin{multicols}{4}

[label=\Alph*.]

1. 10
2. 20
3. 360
4. 60

\end{multicols}

\begin{figure}[htbp]

TikZ 图 118

\end{figure} 图：分组过程图解

解

此问题是将相异物体放入相同容器的无序分组问题，并附加了双重约束. 问题的解决分为两个逻辑步骤：首先确定满足约束的“分组数量方案”，然后计算对应的“物品分配方案”.

第一步是确定分组的数量构成. 设三个盒子里的球数分别为 $k_1, k_2, k_3$. 根据题意，这些数量必须满足以下条件：

• $k_1 + k_2 + k_3 = 6$ (球的总数)

• $k_1, k_2, k_3 \ge 1$ (每个盒子至少一个球)

• $k_1, k_2, k_3$ 互不相同 (数目不同)

  我们实质上是在寻找将整数6分拆为3个不同的正整数之和的方法. 不妨设 $1 \le k_1 \< k_2 \< k_3$. 若 $k_1=1$, 则 $k_2+k_3=5$. 满足 $1\<k_2\<k_3$ 的唯一整数解是 $k_2=2, k_3=3$. 这给出了分组方案 $(1, 2, 3)$. 若 $k_1 \ge 2$, 则 $k_1+k_2+k_3$ 的最小可能值为 $2+3+4=9$, 这大于6. 因此，唯一满足条件的分组数量方案是，将6个球分成数量为1, 2, 3的三组.

  第二步是计算将6个不同的球按此方案分组的方法数. 我们需要将6个不同的球分成三组，各组大小分别为1, 2, 3. 首先，从6个球中选出1个作为一组，有 $\binom{6}{1}$ 种方法. 然后，从剩下的5个球中选出2个作为一组，有 $\binom{5}{2}$ 种方法. 最后，剩下的3个球自成一组，有 $\binom{3}{3}$ 种方法.

  根据乘法原理，形成这三组的方法数为 <MathBlock raw={"N = \binom{6}{1}\binom{5}{2}\binom{3}{3} = 6 \times \frac{5 \times 4}{2} \times 1 = 6 \times 10 = 60"} />

  现在我们必须审视“三个完全相同的盒子”这一条件. 这意味着分组是无序的. 然而，在本题中，三组球的数量分别为1, 2, 3，彼此各不相同. 组的“大小”本身就成为了一个天然的、无法磨灭的标签，使得这三组是客观上可区分的. 因此，我们无需像处理等大分组那样再除以组数的阶乘.

  所以，不同的放球方法总数就是分组的方法数. 故选D.

例

将10名实习生分配到三个不同的部门 A, B, C 进行实习，其中A部门3人，B部门3人，C部门4人. 问有多少种分配方案？

解

这是一个典型的有序分组问题，因为部门 A, B, C 是明确可区分的.

我们可以分步进行选择： 首先为A部门从10人中选出3人，有 $\binom{10}{3}$ 种方法. 然后为B部门从剩下的7人中选出3人，有 $\binom{7}{3}$ 种方法. 最后剩下的4人全部到C部门，有 $\binom{4}{4}$ 种方法.

根据乘法原理，总方案数为 <MathBlock raw={"N = \binom{10}{3}\binom{7}{3}\binom{4}{4} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} \times \frac{7 \cdot 6 \cdot 5}{3 \cdot 2 \cdot 1} \times 1 = 120 \times 35 = 4200"} /> 所以，共有4200种不同的分配方案.

例

将10名实习生分成三组，两组3人，一组4人，再将这三组派往三个不同的城市进行社会调研. 问有多少种派遣方案？

解

这个问题是一个复合问题，包含“分组”和“分配”两个阶段.

法一：分步处理 (先分组，后分配)

第一步：分组. 我们需要将10名实习生分成三组，其中两组3人，一组4人. 注意，此时这些“组”本身是没有身份的，我们只关心组内的成员构成. 这是一个无序分组问题. 两个3人组的大小相同，它们之间是不可区分的.

我们先按有序分组计算，假定两个3人组分别为 $G_1, G_2$. 方法数为 $\binom{10}{3}\binom{7}{3}\binom{4}{4} = 4200$. 但是，将 $\{S_1,S_2,S_3\}$ 分给 $G_1$ 和将 $\{S_4,S_5,S_6\}$ 分给 $G_2$, 与将 $\{S_4,S_5,S_6\}$ 分给 $G_1$ 和将 $\{S_1,S_2,S_3\}$ 分给 $G_2$ 最终形成的无序分组是同一种. 由于两个3人组是不可区分的，我们需要除以 $2!$ 来消除它们的顺序.

分组的方法数为 <MathBlock raw={"N_{\text{分组}} = \frac{\binom{10}{3}\binom{7}{3}\binom{4}{4}}{2!} = \frac{4200}{2} = 2100"} />

第二步：分配. 现在我们有了三组确定的人员（两个3人组，一个4人组）. 我们需要将这三组分配到三个不同的城市. 这三组因为人数不同（3人 vs 4人）或人员构成不同而一定是可区分的. 将这三组分配给三个城市，是一个全排列问题. 分配的方法数为 $3! = 6$.

根据乘法原理，总的派遣方案数为 <MathBlock raw={"N = N_{\text{分组}} \times N_{\text{分配}} = 2100 \times 6 = 12600"} />

法二：等价视角 (直接分配)

这个问题也可以等价地看作：将10名实习生直接分配到三个城市的岗位上，其中两个城市各需3人，一个城市需4人.

这需要我们对城市进行分类讨论，因为哪个城市得到4人是不同的情况.

情况一：城市1得到4人，城市2和城市3各得到3人. 方法数为 $\binom{10}{4}\binom{6}{3}\binom{3}{3} = 210 \times 20 \times 1 = 4200$.

情况二：城市2得到4人，城市1和城市3各得到3人. 方法数同样为 $\binom{10}{4}\binom{6}{3}\binom{3}{3} = 4200$.

情况三：城市3得到4人，城市1和城市2各得到3人. 方法数同样为 $\binom{10}{4}\binom{6}{3}\binom{3}{3} = 4200$.

根据加法原理，总方案数为 <MathBlock raw={"N = 4200 + 4200 + 4200 = 3 \times 4200 = 12600"} />

两种方法的结果完全一致. 法一“先分后配”的思路在面对更复杂问题时通常更为清晰和系统. 它揭示了一个深刻的联系： <MathBlock raw={"\left( \frac{\binom{10}{3}\binom{7}{3}\binom{4}{4}}{2!} \right) \times 3! = 3 \times \binom{10}{4}\binom{6}{3}"} /> 这展示了如何通过不同的计数路径验证结果的正确性.