16.1 分类加法计数原理与分步乘法计数原理
完成一件事有 n 类独立方案，第 i 类有 mi 种不同的方法，那么完成这件事共有：
种不同的方法。
关键词："或者"、"分类" -- 各类方案相互独立，任选一类即可完成。
完成一件事需 n 个步骤，第 i 步有 mi 种不同的方法，那么完成这件事共有：
种不同的方法。
关键词："且"、"分步" -- 各步骤缺一不可，依次完成。
| 比较项目 | 分类加法原理 | 分步乘法原理 |
|---|---|---|
| 核心判断 | 能否一步完成 | 需多步才能完成 |
| 方案关系 | 各类方案相互独立 | 各步骤相互依存 |
| 运算方式 | 各类方法数相加 | 各步方法数相乘 |
| 关键词 | "或者"、"分类" | "且"、"分步"、"依次" |
| 任一类/步 | 任选一类即可完成任务 | 每一步都必须完成 |
从甲地到乙地，可以乘火车（3 班）、汽车（2 班）或飞机（1 班），共有多少种不同的走法？
解：这是一个分类问题，选择火车、汽车或飞机三种交通方式中的一种即可到达。
由分类加法计数原理：N = 3 + 2 + 1 = 6 种
从甲地经丙地到乙地，甲到丙有 3 种方式，丙到乙有 4 种方式，共有多少种不同的走法？
解：需先从甲到丙（第一步），再从丙到乙（第二步），两步缺一不可。
由分步乘法计数原理：N = 3 × 4 = 12 种
用 0, 1, 2, 3, 4 五个数字，可以组成多少个没有重复数字的三位数？
解：
分类讨论（按百位数字是否为 0 分类）：
情况一：百位不为 0
第一步：百位从 {1, 2, 3, 4} 中选 1 个，有 4 种
第二步：十位从剩余 4 个数字中选 1 个，有 4 种
第三步：个位从剩余 3 个数字中选 1 个，有 3 种
由乘法原理：4 × 4 × 3 = 48
情况二：百位为 0 → 不构成三位数
共可组成 48 个没有重复数字的三位数。
16.2 排列
从 n 个不同元素中取出 m (m ≤ n) 个元素，按照一定的顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列。
排列的特点：有序性 -- 元素相同但顺序不同视为不同的排列。
从 n 个不同元素中取出 m 个元素的排列数记为 A(n, m) 或 P(n, m)：
特别地：
- 全排列：
A(n, n) = n! A(n, 1) = n- 规定：
0! = 1
站队问题
n 个人站成一排的不同排法：A(n, n) = n!
排数字问题
用若干数字组成多位数，需注意 0 不能作首位
定位问题
指定某些元素在特定位置，先排特殊位置
计算 A(5, 3) 和 A(6, 6)。
解：
A(5, 3) = 5! / (5-3)! = 5! / 2! = 120 / 2 = 60
或 A(5, 3) = 5 × 4 × 3 = 60
A(6, 6) = 6! = 720
16.3 组合
从 n 个不同元素中取出 m (m ≤ n) 个元素组成一组，叫做从 n 个不同元素中取出 m 个元素的一个组合。
组合的特点：无序性 -- 只关心选出哪些元素，不关心顺序。
从 n 个不同元素中取出 m 个元素的组合数记为 C(n, m) 或 (nm)：
即组合数 = 排列数 / m 的全排列（消除顺序的影响）。
互补性
从 n 个元素中选 m 个，等价于选出剩下的 n-m 个。
递推关系（杨辉三角）
第 n 行第 m 个数 = 上一行左上方 + 上一行正上方。
C(n, 0) = C(n, n) = 1C(n, 1) = n
| 比较项目 | 排列 | 组合 |
|---|---|---|
| 定义 | 取出元素并排列 | 取出元素组成一组 |
| 是否有序 | 有序 | 无序 |
| 符号 | A(n, m) 或 P(n, m) | C(n, m) |
| 关系 | A(n, m) = C(n, m) · m! | |
从 10 名同学中选出 3 人参加数学竞赛，有多少种不同的选法？如果还需从中选出一人担任队长呢？
解：
（1）只选人（组合）：
C(10, 3) = 10! / (3! · 7!) = (10 × 9 × 8) / (3 × 2 × 1) = 120 种
（2）选人并指定队长（排列）：
方法一：先选 3 人再定队长，C(10, 3) × 3 = 120 × 3 = 360
方法二：直接用排列，A(10, 3) = 10 × 9 × 8 = 720 种
（注：第二种理解为从 10 人中选 3 人并排第一、第二、第三，方法不同。）
16.4 排列组合的综合应用
优先处理有限制条件的元素或位置，先安排特殊元素，再安排其他元素。
将必须相邻的元素"捆绑"在一起视为一个整体，先排列整体，再排列整体内部。
先排列没有限制的元素，再将不相邻的元素插入空隙中。
当正面计算复杂时，用总数减去不符合条件的情况数。
将 n 个相同元素分成 m 组（每组至少 1 个），用 m-1 个"隔板"插入 n-1 个空隙中：
适用条件：元素相同、每组至少一个。
- 分组分配问题：先分组（组合），再分配（排列）。注意等额分组要除以组数的阶乘。
- 涂色问题：按区域依次涂色，注意相邻区域不同色的限制。
- 路径问题：网格中从一点到另一点的最短路径数，用组合数计算。
5 个人站成一排，其中甲、乙两人必须相邻，有多少种排法？
解：
将甲、乙"捆绑"为一个整体，与其余 3 人共 4 个元素排列：
A(4, 4) = 4! = 24
甲、乙内部可互换：A(2, 2) = 2! = 2
由乘法原理：24 × 2 = 48 种
5 个人站成一排，其中甲、乙两人不相邻，有多少种排法？
解：
方法一（间接法）：
5 人全排列：A(5, 5) = 120
甲、乙相邻的排法（捆绑法）：48
不相邻的排法：120 - 48 = 72 种
方法二（插空法）：
先排其余 3 人：A(3, 3) = 3! = 6
3 人形成 4 个空位（两端 + 中间），将甲、乙插入 2 个空位：
A(4, 2) = 4 × 3 = 12
由乘法原理：6 × 12 = 72 种
将 10 个相同的小球放入 3 个不同的盒子，每个盒子至少放 1 个，有多少种放法？
解：
10 个相同球排成一排，有 9 个空隙。在 9 个空隙中插入 2 个隔板分成 3 份：
C(9, 2) = 9! / (2! · 7!) = (9 × 8) / 2 = 36 种
将 6 本不同的书分成 3 组（每组 2 本），分别送给甲、乙、丙三人，有多少种分法？
解：
方法一（先分组后分配）：
先将 6 本书分成 3 组（每组 2 本）：
分组数 = C(6,2) × C(4,2) × C(2,2) / 3! = (15 × 6 × 1) / 6 = 15
（除以 3! 是因为三组等额，组间无序）
再将 3 组分给甲、乙、丙（全排列）：A(3, 3) = 3! = 6
总数：15 × 6 = 90 种
方法二（直接分步）：
甲从 6 本中选 2 本：C(6, 2) = 15
乙从剩余 4 本中选 2 本：C(4, 2) = 6
丙拿剩下的 2 本：C(2, 2) = 1
总数：15 × 6 × 1 = 90 种
16.5 二项式定理
对任意正整数 n：
其中 C(n, r) 称为二项式系数。
注意：第 r+1 项的二项式系数是 C(n, r)，而不是 C(n, r+1)。
对称性
二项式系数关于中间项对称。
系数之和
令 a = b = 1 代入二项式定理。
交错和为零
令 a = 1, b = -1 代入二项式定理。
最大值
n 为偶数时，中间一项 C(n, n/2) 最大。
n 为奇数时，中间两项 C(n, (n-1)/2) 和 C(n, (n+1)/2) 最大且相等。
二项式系数排列成的三角形称为杨辉三角（西方称帕斯卡三角），其规律如下：
第 0 行： 1
第 1 行： 1 1
第 2 行： 1 2 1
第 3 行： 1 3 3 1
第 4 行： 1 4 6 4 1
第 5 行： 1 5 10 10 5 1
- 每一行的两端都是 1
- 每个数等于它上方两个数之和
- 第 n 行共有 n+1 个数
- 第 n 行各数之和为 2n
设 f(x) = (a + bx)n，则：
- 所有项系数之和：令 x = 1，得 f(1) = (a + b)n
- 奇数项系数之和：[f(1) + f(-1)] / 2
- 偶数项系数之和：[f(1) - f(-1)] / 2
求 (x + 1/x)6 展开式中的常数项。
解：
通项 Tr+1 = C(6, r) · x6-r · (1/x)r = C(6, r) · x6-2r
常数项要求 x 的指数为 0：6 - 2r = 0，得 r = 3
常数项 = C(6, 3) = 6! / (3! · 3!) = 20
求 (2x - 1)5 展开式中 x3 的系数。
解：
通项 Tr+1 = C(5, r) · (2x)5-r · (-1)r
= C(5, r) · 25-r · (-1)r · x5-r
令 5 - r = 3，得 r = 2
x3 的系数 = C(5, 2) · 23 · (-1)2
= 10 × 8 × 1 = 80
求 (1 + 2x)6 展开式中各项系数之和、奇数项系数之和与偶数项系数之和。
解：设 f(x) = (1 + 2x)6
各项系数之和：令 x = 1
f(1) = (1 + 2)6 = 36 = 729
令 x = -1：f(-1) = (1 - 2)6 = (-1)6 = 1
奇数项系数之和：[f(1) + f(-1)] / 2 = (729 + 1) / 2 = 365
偶数项系数之和：[f(1) - f(-1)] / 2 = (729 - 1) / 2 = 364
证明：C(n,0) + C(n,1) + C(n,2) + ... + C(n,n) = 2n
证明：
由二项式定理：(a + b)n = C(n,0)an + C(n,1)an-1b + ... + C(n,n)bn
令 a = 1, b = 1：
(1 + 1)n = C(n,0) + C(n,1) + C(n,2) + ... + C(n,n)
即 2n = C(n,0) + C(n,1) + ... + C(n,n)。证毕。
本章知识总结
计数原理
- 加法原理 分类计数，各类独立，方法相加
- 乘法原理 分步计数，各步依存，方法相乘
排列与组合
- 排列 有序，A(n,m) = n!/(n-m)!
- 组合 无序，C(n,m) = n!/[m!(n-m)!]
- 关系 A(n,m) = C(n,m) · m!
解题方法
- 特殊优先 先处理有限制的元素/位置
- 捆绑法 相邻问题，先绑后排
- 插空法 不相邻问题，先排后插
- 隔板法 相同元素分组
- 间接法 正难则反，用总数减去
二项式定理
- 通项公式 Tr+1 = C(n,r)an-rbr
- 系数和 令变量 = 1 或 -1
- 杨辉三角 每数等于上方两数之和
- 最大系数 中间项最大