ch09-计數原理

{/* label: chap:ch09 */}

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

\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$ 种不同的途径，那么完成這件事共有

N = m_1 + m_2 + ... + m_k

种不同的方法.

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

從集合論的观点看，如果 $A_i$ 代表第 $i$ 類方法的集合, 那么這些集合两两不交, 即 $A_i \cap A_j = \emptyset$ for $i \neq j$ . 完成任务的总方法數就是這些集合的并集的大小：

|A_1 \cup A_2 \cup ... \cup A_k| = |A_1| + |A_2| + ... + |A_k|

現在我们看一些加法原理的有趣應用：

例

某大學的课程目錄中，數學係開设了5门不同的選修课，计算机係開设了3门不同的選修课.一名學生希望從中選择一门课来學習，他有多少种不同的選择？

解

這個問題是加法原理最直接的應用.學生的目標是“選择一门课”. 我们可以将所有可選的课程分為两類：第一類：選择數學係的课程，有 $5$ 种方法. 第二類：選择计算机係的课程，有 $3$ 种方法.

由于一個學生不能同时選择數學课和计算机课来满足“選择一门课”這個目標（即這两類選择是互斥的），因此总的選择數是两類方法數之和.

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，所以這两類情况是互斥的.根据加法原理，总的密码個數是

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$ ）是唯一的.因此，根据加法原理，我们得到了一個递推關係：

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)$ .

根据加法原理，我们得到递推關係：

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$

最后，我们计算目標点：

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的倍數）.因此，根据加法原理，满足条件的因數总數為

N = 8 + 2 = 10

所以，共有10個這样的因數.

通過精巧地定義分類標准（ $A$ 和 $B \setminus A$ ），我们将一個潜在的容斥原理問題转化為了纯粹的加法原理問題，這展示了在计數中“如何分類”本身就是一门艺术.

乘法原理

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

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

乘法原理

如果完成一件事需要分成 $k$ 個步骤, 完成第一個步骤有 $m_1$ 种不同的方法, 完成第二個步骤有 $m_2$ 种不同的方法, ..., 完成第 $k$ 個步骤有 $m_k$ 种不同的方法，那么完成這件事共有

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$ . 用集合符号表示為：

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$ .

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 \}

笛卡尔積的大小，即其元素的個數，恰好就是乘法原理给出的结果.如果這些集合都是有限集，那么

|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$ ，其大小為

|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$ .

其大小為：

|T \times M| = |T| \times |M| = 2 \times 3 = 6

這個集合的具體内容是：

\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$ .

根据笛卡尔積的基數公式，总的方案數是：

|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$ 种選择. 根据乘法原理，总共有

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”的三位數共有

8 \times 9 \times 9 = 648

個.

我们已經将所有三位數分成了两類：“至少含有一個7”的和“一個7也没有”的. 這两類是互斥的，它们的总和就是全部三位數的個數. 因此，根据加法原理的變形（也称為补集原理或容斥原理的最簡單形式），我们得到

(\text{至少含有一個7的個數}) = (\text{总個數}) - (\text{一個7也没有的個數})

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$ 种選择.

根据乘法原理，要完成這全部三個步骤，总的方法數是每一步方法數的乘積.

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$ 种選择.

根据乘法原理，所有可能的排名总數為：

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$ 進行素數分解：

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$ 种選择.

根据乘法原理，正因數的总個數為：

\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$ 种選择.

根据乘法原理，总的染色方法數為：

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种選择的决策，总的方法數為：

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$ . 它们都表示同一個數學概念.

在本書中，我们主要采用国际通用的二項式係數 记法：

\binom{n}{k}

這個符号讀作““從 $n$ 中選 $k$ 個””，為了确保清晰，請记住它们之間的恒等關係：

\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!$ 次.因此，為了得到正确的组合數，我们必须用有序選法总數除以這個重複的倍數.

\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$ ) 為

\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$ 种選择.

根据乘法原理，总的排列數是這些選择數的乘積：

P(n,k) = n(n-1)\cdots(n-k+1)

為了将其表达為更紧凑的階乘形式，我们在分子和分母上同乘以 $(n-k)!$ :

P(n,k) = \frac{n(n-1)\cdots(n-k+1) \cdot (n-k)!}{(n-k)!} = \frac{n!}{(n-k)!}

法二：通過组合數間接计算排列數.

我们也可以将構造一個 $k$ -排列的任务分解為两個连續的步骤：

選择元素 (组合)： 首先，從 $n$ 個元素中不计顺序地選出 $k$ 個元素.根据定義, 完成這一步的方法數正是我们要计算的组合數 $\binom{n}{k}$ .
安排顺序 (全排列)： 接着，将這已經選出的 $k$ 個元素進行全排列.這有 $k!$ 种方法.

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

由于两种方法计算的是同一個量 $P(n,k)$ ，因此它们的结果必须相等：

\binom{n}{k} \times k! = P(n,k) = \frac{n!}{(n-k)!}

現在，我们两边同除以 $k!$ (由于 $k \ge 0$ , $k! \ge 1$ , 所以可以安全地相除), 即可解出 $\binom{n}{k}$ :

\binom{n}{k} = \frac{n!}{k!(n-k)!}

将 $P(n,k)$ 的另一种形式代入等式 $\binom{n}{k} \times k! = n(n-1)\cdots(n-k+1)$ ，我们可以得到公式的另一种常用形式：

\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$ 的合理性.

現在，我们可以回答彩票問題了.

\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)$ 呢？我们可以把“完成一次排列”這個任务，看作是應用乘法原理的两個步骤：

第一步：選材. 從 $n$ 個元素中, 先“選出”要參與排列的 $k$ 個元素.根据我们刚刚學到的知识, 這一步有 $\binom{n}{k}$ 种方法.
第二步：排序. 将這選出的 $k$ 個元素進行全排列.根据乘法原理, 這一步有 $k!$ 种方法.

因為必须完成所有步骤，任务才算完成，所以根据乘法原理，我们得到排列數與组合數之間的一個至關重要的關係：

A(n,k) = \binom{n}{k} \times k!

這個關係式深刻地揭示了排列和组合的内在联係：一個排列，本質上就是一個组合再加上對所選元素的排序.

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

排列數公式

從 $n$ 個不同元素中取出 $k$ 個元素的排列數 ( $0 \le k \le n$ ) 為

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$ 個步骤的总方法數是每一步方法數的乘積.因此，

A(n,k) = n \times (n-1) \times (n-2) \times \cdots \times (n-k+1)

這便證明了公式的第一個等式.

為了得到階乘形式的表达式，我们可以對上式進行一個簡單的代數變換.通過在分子和分母上同时乘以 $(n-k)!$ :

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)!$ . 所以，

A(n,k) = \frac{n!}{(n-k)!}

這就證明了公式的第二個等式.

最后，根据我们在上一节推導出的排列與组合的關係 $A(n,k) = \binom{n}{k} \times k!$ ，我们可以验證其一致性：

\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個人進行排列.

P(10,3) = \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10 \times 9 \times 8 = 720

法二：利用“先组合，后排序”的思想. 第一步：從10人中選出3個“幸运儿”.這有 $\binom{10}{3}$ 种方法.

\binom{10}{3} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 10 \times 3 \times 4 = 120

第二步：為這3個選出的人分配3個不同的职位.這有 $3!$ 种方法.

3! = 3 \times 2 \times 1 = 6

根据乘法原理，总的選举结果為

N = \binom{10}{3} \times 3! = 120 \times 6 = 720

两种方法的结果完全一致，這验證了我们對排列與组合關係的理解.

二項式定理

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

在上一节中，我们引入了组合數 $\binom{n}{k}$ , 并将其定義為從 $n$ 個不同元素中選取 $k$ 個的方案數.這個符号也被称為二項式係數.這個名字本身就暗示了它與“二項式”——即形如 $(x+y)$ 的代數表达式——之間存在着深刻的联係.本节的目標就是揭示這一联係，它集中體現在數學中最重要和最美丽的定理之一：二項式定理.

让我们從簡單的例子開始，观察其展開式的係數规律：

\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$ ，下述展開式成立：

(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k

展開来看，即：

(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

證明

考虑乘積的完全展開形式：

(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$ )，我们将所有這些項加起来，就得到了二項式定理的完整形式：

(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k

這個證明完美地解释了為什么组合數会作為係數出現在二項式的展開式中.

杨辉三角

将二項式係數 $\binom{n}{k}$ 排列成一個三角形的陣列，我们就得到了著名的杨辉三角.

\begin{figure}[htbp]

{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$ ，有

\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}$ .

根据加法原理，完成“選班委”這件事的总方法數，等于上述两种互斥情况的方法數之和.因此，我们得到：

\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}

從三項式定理到多項式定理*

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

一旦我们得出了二項式定理，一個更自然的問題是：是否有類似的三項式定理、四項式定理 $\cdots$ 呢？让我们沿用證明二項式定理时的组合思想来分析 $(x+y+z)^n$ 的展開式.

(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$ ，即

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$ 的总方案數.我们可以通過分步计數来解决這個問題：

第一步：為 $x$ 選择因子. 從 $n$ 個可用的因子中, 選出 $k_1$ 個.這有 $\binom{n}{k_1}$ 种方法.
第二步：為 $y$ 選择因子. 從剩下的 $n-k_1$ 個因子中, 選出 $k_2$ 個.這有 $\binom{n-k_1}{k_2}$ 种方法.
第三步：為 $z$ 選择因子. 最后剩下的 $n-k_1-k_2 = k_3$ 個因子, 全部用于提供 $z$ .這只有 $\binom{k_3}{k_3}=1$ 种方法.

根据乘法原理，总的方案數為：

\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$ ，三項式係數被定義為

\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$ ，下述展開式成立：

(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)$ 進行求和：

$k_1, k_2, k_3$ 均為非负整數, 即 $k_1 \ge 0, k_2 \ge 0, k_3 \ge 0$ .
它们的和恰好等于 $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個三元组的項全部加起来：

(2,0,0), (0,2,0), (0,0,2), (1,1,0), (1,0,1), (0,1,1)

因此， $(x+y+z)^2$ 的展開式实际上是：

\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$ 的非负整數.

考虑乘積的展開形式：

(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}$ 在最终展開式中出現的次數（即它的係數），等于完成上述三步選择的总方案數.

我们可以使用乘法原理来计算這個方案數：

為 $x$ 選择因子. 我们需要從 $n$ 個不同的因子中, 選出 $k_1$ 個来提供變量 $x$ . 這是一個组合問題, 方法數是 $\binom{n}{k_1}$ .
為 $y$ 選择因子. 在完成了第一步之后，还剩下 $n-k_1$ 個因子.我们需要從這些剩余的因子中, 選出 $k_2$ 個来提供變量 $y$ . 方法數是 $\binom{n-k_1}{k_2}$ .
為 $z$ 選择因子. 此时，最后剩下 $n-k_1-k_2 = k_3$ 個因子.我们必须從這 $k_3$ 個因子中選出 $k_3$ 個来提供變量 $z$ . 方法數是 $\binom{k_3}{k_3}=1$ .

根据乘法原理，总的方案數是以上三步方法數的乘積：

\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$ 的完整項是：

\binom{5}{2, 1, 2} A^2 B^1 C^2

首先，计算三項式係數：

\binom{5}{2, 1, 2} = \frac{5!}{2!1!2!} = \frac{120}{2 \cdot 1 \cdot 2} = 30

然后，代入 $A, B, C$ 的具體表达式：

30 \cdot (2x)^2 \cdot (-y)^1 \cdot (3z^2)^2

= 30 \cdot (4x^2) \cdot (-y) \cdot (9z^4)

= (30 \cdot 4 \cdot (-1) \cdot 9) x^2 y z^4

= -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$ 個元素.因此，

\binom{n}{k} = \binom{n}{k, n-k} = \frac{n!}{k!(n-k)!}

這個视角统一了這些计數工具，揭示了它们共同的“分组”本質.

有了對這個係數组合意義的理解，我们現在可以正式地陈述多項式定理.该定理不僅给出了展開式的完整形式，也同时给出了计算多項式係數的代數公式.

多項式定理

對于任意非负整數 $n$ 和 $m \ge 2$ ，有

(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}

其中多項式係數定義為

\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$ 個相同因子的乘積：

\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$ ，即

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$ 种方法.

根据乘法原理，总的方案數是以上所有步骤方法數的乘積：

\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}

現在，我们将這些二項式係數用階乘形式展開，观察化簡過程：

\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 */}

排列與组合的公式為我们提供了计數的代數工具，然而，面對千變万化的计數問題，僅僅掌握公式是远远不够的.真正的挑战在于如何将一個複杂的問題進行剖析、转化，使其结構清晰地對應到我们所學的基本模型上.

相邻與不相邻問題

在排列問題中，元素之間的相對位置關係是最常出現的约束条件之一.“相邻”與“不相邻”構成了一對典型的對立约束，分别對應着两种經典的处理技巧：捆绑法與 插空法.

相邻問題與捆绑法

当問題要求若干個特定元素必须排列在一起（即“相邻”）时，我们可以采用捆绑法来解决.该策略的核心思想是，将這些必须相邻的元素在逻辑上视為一個不可分割的整體，即一個“複合元素”，然后再與其他元素進行排列.

捆绑法

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

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

例

有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個元素進行全排列，方法數為

A(6,6) = 6! = 720

第三步：内排. 在女生構成的整體 $G$ 内部，3名女生自身也可以有不同的排列顺序. 3名女生的全排列方法數為

A(3,3) = 3! = 6

第四步：相乘. 根据乘法原理，总的排法數是外排和内排方法數的乘積.

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$ .

第三步：相加. 根据加法原理，将两种情况的方法數相加.

N = 36 + 24 = 60

所以，共能组成60個這样的六位數.

不相邻問題與插空法

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

插空法

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

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

例

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

解

這是一個典型的“互不相邻”問題，應使用插空法. 小說是受限元素，诗集是不受限元素.

第一步：排诗集. 首先排列4本不同的诗集.方法數為

A(4,4) = 4! = 24

第二步：造空. 4本诗集排好后，形成5個可供插入的空隙.

\_ P_1 \_ P_2 \_ P_3 \_ P_4 \_

第三步：插小說. 将3本不同的小說插入到這5個空隙中，每空至多一本. 這相当于從5個空隙中選出3個来放置小說，并且要考虑小說的顺序.這是一個排列問題. 方法數為

A(5,3) = 5 \times 4 \times 3 = 60

第四步：相乘. 根据乘法原理，总的排法數為

N = 4! \times A(5,3) = 24 \times 60 = 1440

所以，共有1440种不同的排法.

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

在处理计數問題时，必须精确理解约束条件的含義.“互不相邻”與“不全相邻”是两個極易混淆的概念.

互不相邻：指任意两個指定的元素都不能相邻.這是插空法的适用范围.
不全相邻：指指定的元素不全部连在一起即可，允许其中一部分相邻.

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

例

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

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

解

這個問題旨在厘清“互不相邻”和“不全相邻”的区别.

(1) 3名女生互不相邻. 這是一個“插空法”問題. 第一步：先排5名男生，有 $5!$ 种方法. 第二步：5名男生形成6個空隙. 第三步：将3名女生插入6個空隙中，有 $A(6,3)$ 种方法. 根据乘法原理，总方法數為

N_1 = 5! \times A(6,3) = 120 \times (6 \times 5 \times 4) = 120 \times 120 = 14400

(2) 3名女生不全相邻. 這是一個“补集思想”問題.它的對立面是“3名女生全部相邻”. 首先，计算总的排列數.8個人全排列，有 $8!$ 种方法.

8! = 40320

接着，计算對立事件（3名女生全部相邻）的排列數. 這正是我们用“捆绑法”计算過的第一個例子. 将3名女生捆绑，與5名男生共6個元素全排列，再乘以女生内部的全排列.

N_{\text{全相邻}} = 6! \times 3! = 720 \times 6 = 4320

最后，用总數减去對立事件數.

N_2 = 8! - (6! \times 3!) = 40320 - 4320 = 36000

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

為何捆绑法與插空法有效？

在上一节中，我们介绍了处理相邻與不相邻問題的两种標准化流程：捆绑法與插空法.這些方法之所以强大，是因為它们并非簡單的技巧，而是将複杂的约束問題巧妙地转化為基本计數原理應用的典范.本节将深入探讨這两种方法背后的數學逻辑，以揭示其有效性的根本原因.

捆绑法

相邻問題的核心约束是“某些元素必须保持相對位置不變”，這破坏了全排列中每個元素独立性的前提.捆绑法的本質，是将一個带有複杂约束的计數問題，通過逻辑上的等价變換，转化為一個无约束的、分步的構造問題.

核心原理

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

内部構造：将被指定的 $m$ 個元素進行全排列，形成一個有序的、不可分割的複合元素.
外部構造：将此複合元素與其余 $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!$ . 這就從根本上證明了捆绑法计算逻辑的正确性.它将一個静态的“满足约束的排列集合有多大”的問題，动态地转變為“生成一個這样的排列有多少种方法”的問題.

插空法

不相邻問題的核心约束是“某些元素之間必须被其他元素隔開”.直接处理這种“排斥性”约束是困难的.插空法的精妙之处在于，它通過逆向思維，将一個複杂的定位問題，转化為一個有序的填充問題.

插空法同样是一個構造性的過程，其逻辑的严谨性依赖于以下分步構造的唯一性與完備性：

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

让我们来审视這個過程的數學基礎：

空隙的定義： $n$ 個已經排好的元素 $U_1, U_2, ..., U_n$ , 会在它们之間以及两端, 严格地定義出 $n+1$ 個不同的、可识别的“空隙”位置.

\_ 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$ 個来放置要打開的灯.這是一個纯粹的组合問題，方法數為

\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$ .

将所有可能情况相加，得到总的開法數為

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$ 如下：

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$ . 這种選择的方法數即為组合數

\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$ .

总的開法总數為

N = 36 + 56 + 35 + 6 = 133

所以，符合要求的開法总數是133.

2014 重庆理

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

[label=\Alph*.]

\end{multicols}

解

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

首先，我们假定所有6個节目都是独一无二的. 总的排列數（没有任何限制）為

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!$ 种排列.

|A| = 5! \times 2! = 120 \times 2 = 240

直接计算“至少有2個歌舞相邻”比较複杂，我们计算其补集，即“3個歌舞节目互不相邻”（记作 $B^c$ ）. 為此，我们使用插空法.先排列非歌舞节目{小品1, 小品2, 相声}，有 $3!$ 种方法. 這3個节目形成了4個空隙.将3個不同的歌舞节目插入這4個空隙中，有 $A(4,3)$ 种方法.

|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!$ 种方法.

|A \cap B^c| = (2! \times 2!) \times 3! = 4 \times 6 = 24

所以, $|A \cap B| = |A| - |A \cap B^c| = 240 - 24 = 216$ .

不符合要求的排列总數為

|A \cup B| = |A| + |B| - |A \cap B| = 240 + 576 - 216 = 600

因此，符合要求的排列种數為

N = |U| - |A \cup B| = 720 - 600 = 120

故選B.

定序問題與倍缩策略

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

面對這類問題，一個極其强大的思想是倍缩策略，其本質是“先放后缩”.我们首先忽略定序的约束，對所有相關元素進行全排列，得到一個总數.然后，我们分析在這個总數中，我们所關注的、被定了序的元素有多少种排列方式.由于題目只允许其中的一种特定顺序，我们原来的计數就“夸大”或“重複”了，其倍數恰好是被定序元素的全排列數.因此，我们用总排列數除以這個“重複倍數”，即可得到最终答案.

這個思想并非全新.事实上，组合數的公式本身就是倍缩策略最經典的體現.

\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}$ 中的任意一個排列.我们可以通過一個两步過程来唯一地生成每一個排列：

選择一個“骨架”排列. 我们從符合定序条件的集合 $\mathcal{A}$ 中任意選择一個排列. 在這個排列中, 那 $m$ 個特殊元素的相對顺序是正确的.完成這一步, 我们有 $N$ 种選择.
對特殊元素進行“内部重排”. 在上一步選出的“骨架”排列中，那 $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}$ ” 的一一對應關係.因此，它们的大小必然相等：

|\mathcal{U}| = N \times m!

我们已知 $|\mathcal{U}| = n!$ ，所以

n! = N \times m!

由此解出我们最初的目標 $N$ :

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$ ，就等于這個分组的數量. 根据除法原理，分组的數量為：

N = \frac{\text{总元素數}}{\text{每组的元素數}} = \frac{n!}{m!}

這两种视角都严谨地證明了倍缩策略的正确性.它将一個带有複杂“相對顺序”约束的問題，转化為一個结構清晰的、關于等价類的计數問題.

倍缩策略

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

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

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

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

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

[label=\Alph*.]

\end{multicols}

解

此問題的核心在于，一旦确定了哪些同學在前排、哪些同學在后排，那么由于“身高依次递增”的严格约束，每一排的站位顺序就唯一确定了.因此，問題的本質從一個排列問題，退化為了一個分组或组合問題.

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

我们可以通過确定“前排组”的人選来完成這個任务.從8名同學中選出4名到前排，這是一個组合問題，其方法數為

\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!$ 倍.

根据倍缩策略，我们将总排列數除以這两個重複的倍數，得到符合条件的排法數：

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*.]

$C_8^2 A_3^2$
$C_8^2 A_6^6$
$C_8^2 A_6^2$
$C_8^2 A_5^2$

\end{multicols}

解

此問題可以分解為两個独立且连續的步骤：首先是“選人”，然后是“排位”.

第一步是選人. 摄影师需要從后排的8名同學中選出2人调到前排.這是一個组合問題，因為此时我们只關心選出的是哪两個人，而不涉及他们的顺序. 選人的方法數為

\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個選择. 由于這两位新同學是不同的個體，他们的顺序是重要的. 因此，為這两位新同學安排位置的方法數是一個排列問題，共有

A(6,2) = 6 \times 5 = 30

一旦這两位新同學的位置确定，剩下的4個位置将由4名“旧”同學按他们原有的相對顺序依次填入，方法只有1种.

或者，我们也可以运用倍缩策略来思考排位問題. 如果不考虑任何顺序限制，将這6名同學（4旧2新）排在前排6個位置上，共有 $6!$ 种方法. 但是，題目要求4名“旧”同學的相對顺序不變.在這 $6!$ 种排列中, 這4名“旧”同學自身有 $4!$ 种排列方式，而我们只接受其中的1种. 因此，符合条件的排法數為

\frac{6!}{4!} = \frac{720}{24} = 30 = A(6,2)

最后，根据乘法原理，将“選人”和“排位”两個步骤的方法數相乘，得到总的调整方式种數：

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.

直接應用排列公式是行不通的，因為它要求所有元素都是可区分的. 然而，我们可以借助倍缩策略，通過一個思想实验来解决此問題.

首先，我们假想所有的字母都是可区分的. 我们可以给相同的字母加上下標来区分它们，例如：

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!$ 倍.

根据倍缩策略，我们将总的假想排列數，除以由每种重複元素内部排列所产生的重複倍數.

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$ ），其不同的排列數為

\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)$ ， “弯曲”成一個圓圈，使其首尾相连. 考虑這個線性排列通過“旋转”可以得到哪些其他的線性排列？

\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$ ，即可得到圓排列的數目.

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!$ 倍.

我们将总的假想排列數除以由重複元素产生的倍數，得到最终的路径數：

N = \frac{(m+n)!}{m!n!}

我们立刻认出，這個结果就是组合數 $\binom{m+n}{m}$ 或 $\binom{m+n}{n}$ . 這為组合數提供了一個全新的、極其重要的组合解释：

\binom{m+n}{m} = \text{從 (0,0) 到 (m,n) 的格路數}

另一种组合视角： 我们也可以直接用组合的定義来解决. 一条路径总共需要 $m+n$ 步. 我们只需要在這 $m+n$ 步中，决定哪几步是向右移动（R），剩下的就自动是向上移动（U）. 從 $m+n$ 個总步數中, 選出 $m$ 步来执行向右移动，方法數為

\binom{m+n}{m}

這與倍缩策略得到的结果完全一致，再次印證了倍缩策略與组合定義的内在统一性. 這种将排列問題转化為序列編码，再利用倍缩策略求解的方法，是组合數學中一种非常强大的通用技巧.

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

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

[label=\Alph*.]

\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個不同的节目進行全排列. 总的排列方法數為

12!

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

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

符合条件的排法种數為

N = \frac{12!}{10!} = \frac{12 \times 11 \times (10!)}{10!} = 12 \times 11 = 132

法二：選位法 (插空思想的變體)

我们也可以從構造的角度来思考這個問題. 总共有12個节目位置需要安排. 問題的本質可以转化為：先為2個新节目選择位置，剩下的位置自然就由10個旧节目按照它们固有的顺序填充.

第一步：為2個新节目選择位置. 我们需要從12個可用的时間槽中，為2個不同的新节目選定它们的表演位置. 這相当于從12個位置中選出2個進行排列. 方法數為

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*.]

\end{multicols}

解

這個問題與原題的核心区别在于，新增的2個节目從“可区分”變為了“不可区分”. 這個變化直接影响了我们计數的方式.

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

总共有12個节目位置. 我们的任务是為2個相同的新节目選择位置. 由于新节目是相同的，我们選择 {第3位, 第8位} 和選择 {第8位, 第3位} 最终产生的节目單是完全一样的. 因此，這不再是一個排列問題，而是一個纯粹的组合問題.

我们需要從12個可用的位置中，選出2個位置来安放這两個相同的新节目. 方法數為

\binom{12}{2} = \frac{12 \times 11}{2 \times 1} = 66

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

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

我们從12個节目全排列出發，总數為 $12!$ .

首先，應用第一個约束：10個旧节目的相對顺序不變. 這意味着我们将总數除以 $10!$ 来消除這10個节目内部顺序的重複计數.

N_1 = \frac{12!}{10!}

接着，應用第二個约束：2個新节目是完全相同的. 這意味着在上述结果中，我们仍然将這两個新节目视為可区分的，從而對它们自身的 $2!$ 种排列進行了重複计數. 因此, 我们必须再次應用倍缩策略, 除以 $2!$ .

最终的排法种數為

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*.]

\end{multicols}

解

這個問題在原題的基礎上，增加了一個“不相邻”的约束. 這种“定序”與“不相邻”的複合约束，是插空法與倍缩思想结合的經典场景.

法一：插空法

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

第一步：排列骨架. 我们要先安排10個旧节目. 由于它们的相對顺序是固定的，因此排列它们的方法只有一种.

O_1, O_2, O_3, O_4, O_5, O_6, O_7, O_8, O_9, O_{10}

第二步：创造空隙. 這10個排好的节目，形成了11個可供插入的空隙 (包括最前和最后).

\_ O_1 \_ O_2 \_ ... \_ O_{10} \_

第三步：插入元素. 我们需要将2個不同的新节目插入到這11個空隙中，每個空隙至多放一個节目，以保證它们不相邻. 這相当于從11個空隙中選出2個，并将2個不同的节目排列進去. 這是一個排列問題. 方法數為

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$ 种.

因此，“新节目相邻”的排法數為

N_{\text{相邻}} = (\text{内部排列}) \times (\text{外部插入}) = 2! \times \binom{11}{1} = 2 \times 11 = 22

最后，用总數减去相邻數：

N_{\text{不相邻}} = N_{\text{总}} - N_{\text{相邻}} = 132 - 22 = 110

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

分组問題

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

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

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

\begin{figure}[htbp]

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

\begin{figure}[htbp]

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

有序分组

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

计算這類問題的過程是一個连續的组合决策：

首先，從6本書中為甲選出2本，方法數為 $\binom{6}{2}$ .
接着，從剩下的4本書中為乙選出2本，方法數為 $\binom{4}{2}$ .
最后，剩下的2本書自动归丙所有，方法數為 $\binom{2}{2}$ .

根据乘法原理，总的分配方法數為

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

我们将這個结果用階乘形式展開，可以观察到其本質：

\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$ )，其总方法數為

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$ 個. 根据组合數的定義，完成這一步的方法數為

\binom{n}{k_1}

在确定了 $G_1$ 的成员后, 集合 $S$ 中还剩下 $n-k_1$ 個元素可供分配. 接下来, 我们為第二個组 $G_2$ 選择成员. 我们需要從這 $n-k_1$ 個剩余元素中, 選出 $k_2$ 個. 方法數為

\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$ 是每一步方法數的乘積.

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}

這便證明了公式的第一個等式.

為了推導其更為簡洁的階乘形式，我们将每一個组合數用其階乘定義展開.

\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!$ .

N = \frac{n!}{k_1!k_2!\cdots k_m!}

這與多項式係數的形式完全吻合.

例

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

解

此問題要求将9名不同的成员分配到三個可区分的中心，且每個中心所需的人數已經确定. 這構成了一個有序分组問題. 我们可以将分配過程视為一個连續的决策步骤.

首先，為 A 中心從9名成员中選派2人. 這是一個组合問題，因為成员在此步骤中僅被選中，其顺序无關紧要. 方法數為

\binom{9}{2}

接着，需從余下的 $9-2=7$ 名成员中，為 B 中心選派3人. 方法數為

\binom{7}{3}

最后，剩下的 $7-3=4$ 名成员将全部被派往 C 中心，這是一种必然的结果. 方法數為

\binom{4}{4}

根据乘法原理，完成整個分配任务的总方案數是上述所有步骤方法數的乘積.

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$ 的可区分的三组，其方法數由多項式係數给出. (為何這個公式是适用的？)

\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人. 方法數為

\binom{5}{1} = 5

接着，為項目B從剩下的4名员工中選定2人. 方法數為

\binom{4}{2} = \frac{4 \times 3}{2} = 6

最后，剩下的2名员工自动被分配到項目C. 方法數為

\binom{2}{2} = 1

依据乘法原理，总的分配方案數為

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$ 的三组，其方法數為

\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张. 方法數為

\binom{52}{13}

接着，為“南”這位玩家從剩下的 $52-13=39$ 张牌中發出13张. 方法數為

\binom{39}{13}

然后，為“西”這位玩家從剩下的 $39-13=26$ 张牌中發出13张. 方法數為

\binom{26}{13}

最后，剩下的13张牌全部發给“北”這位玩家. 方法數為

\binom{13}{13}

根据乘法原理，总的發牌结果數為

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$ 的四個可区分的组. 其总方法數由以下公式直接给出：

N = \frac{52!}{13!13!13!13!} = \frac{52!}{(13!)^4}

我们有必要验證這两种表达方式的等价性，這有助于加深對公式本質的理解.

\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!$ 次.

因此，根据倍缩策略，我们必须用有序分组的结果除以這個重複的倍數.

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$ 個不同元素分组.

各组大小均不相同: 若各组大小為 $k_1, k_2, ..., k_m$ 且彼此不等, 则无序分组與有序分组的结果相同, 為 $\dfrac{n!}{k_1!k_2!\cdots k_m!}$ . (因為组的大小本身就成為了它们的天然“標签”)
部分组大小相同: 若其中有 $m_1$ 個组的大小為 $k_1$ , $m_2$ 個组的大小為 $k_2$ , ..., 则总方法數為

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*.]

\end{multicols}

\begin{figure}[htbp]

\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}$ 种方法.

根据乘法原理，形成這三组的方法數為

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}$ 种方法.

根据乘法原理，总方案數為

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!$ 来消除它们的顺序.

分组的方法數為

N_{\text{分组}} = \frac{\binom{10}{3}\binom{7}{3}\binom{4}{4}}{2!} = \frac{4200}{2} = 2100

第二步：分配. 現在我们有了三组确定的人员（两個3人组，一個4人组）. 我们需要将這三组分配到三個不同的城市. 這三组因為人數不同（3人 vs 4人）或人员構成不同而一定是可区分的. 将這三组分配给三個城市，是一個全排列問題. 分配的方法數為 $3! = 6$ .

根据乘法原理，总的派遣方案數為

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$ .

根据加法原理，总方案數為

N = 4200 + 4200 + 4200 = 3 \times 4200 = 12600

两种方法的结果完全一致. 法一“先分后配”的思路在面對更複杂問題时通常更為清晰和係统. 它揭示了一個深刻的联係：

\left( \frac{\binom{10}{3}\binom{7}{3}\binom{4}{4}}{2!} \right) \times 3! = 3 \times \binom{10}{4}\binom{6}{3}

這展示了如何通過不同的计數路径验證结果的正确性.

加法原理與乘法原理​

加法原理​

乘法原理​

原理的辨析與應用​

组合與排列​

组合​

排列​

二項式定理​

杨辉三角​

從三項式定理到多項式定理*​

多項式定理​

排列组合​

相邻與不相邻問題​

相邻問題與捆绑法​

不相邻問題與插空法​

為何捆绑法與插空法有效？​

捆绑法​

插空法​

定序問題與倍缩策略​

分组問題​

有序分组​

无序分组​

留言

加法原理與乘法原理

加法原理

乘法原理

原理的辨析與應用

组合與排列

组合

排列

二項式定理

杨辉三角

從三項式定理到多項式定理*

多項式定理

排列组合

相邻與不相邻問題

相邻問題與捆绑法

不相邻問題與插空法

為何捆绑法與插空法有效？

捆绑法

插空法

定序問題與倍缩策略

分组問題

有序分组

无序分组