排列与组合

引入

从 $5$ 个人里选 $3$ 个排队，和选 $3$ 个组成小组，答案为什么差 $6$ 倍？

什么时候用加法原理，什么时候用乘法原理？

为什么”至少有一个”这类问题，往往倒过来算更快？

排列与组合是计数的两条基本路线：排列关心顺序，组合不关心顺序。两者的差别只在一个除法，但用错会导致答案相差一个阶乘。

正文

定义

• 分类加法计数原理：完成一件事有 $n$ 类办法，第 $i$ 类有 $m_i$ 种方法，则总数为 $m_1+m_2+\cdots +m_n$。
• 分步乘法计数原理：完成一件事需要 $n$ 个步骤，第 $i$ 步有 $m_i$ 种方法，则总数为 $m_1\times m_2\times \cdots \times m_n$。

加法与乘法的区分

原理	关键词	结构
加法	”或”、“分类”	各类互斥，任选一类即可完成
乘法	”且”、“分步”	每步都必做，全部完成才算完成

判断标准不是文字，而是**“能否只做其中一项就完成任务”**。能则加法，不能则乘法。

排列

定义

从 $n$ 个不同元素中取出 $m$ 个（$m\le n$），按照一定顺序排成一列，称为排列，其个数记为 $A_n^m=n(n-1)(n-2)\cdots (n-m+1)=\frac{n!}{(n-m)!}$

全排列 $A_n^n=n!$。

组合

定义

从 $n$ 个不同元素中取出 $m$ 个（$m\le n$），不考虑顺序，称为组合，其个数记为 $C_n^m=\frac{A_n^m}{A_m^m}=\frac{n!}{m!(n-m)!}$

除以 $A_m^m=m!$ 的原因：每一组 $m$ 个元素都能排出 $m!$ 种不同顺序，在排列中它们被算作不同结果，在组合中应合并为一种。

排列与组合的对照

项目	排列	组合
是否看顺序	看	不看
符号	$A_n^m$	$C_n^m$
例：$5$ 选 $3$	$A_5^3=60$	$C_5^3=10$
关系	$A_n^m=C_n^m\cdot m!$

组合数的性质

性质	式子	意义
对称性	$C_n^m=C_n^{n-m}$	选出的与剩下的等价
递推	$C_{n+1}^m=C_n^m+C_n^{m-1}$	分类：含某个元素 / 不含
边界	$C_n^0=C_n^n=1$	全不选与全选各一种

递推公式是杨辉三角的来源，也是 数学归纳法 证明组合恒等式的常用起点。

常见题型

题型	方法
相邻问题	捆绑法：把相邻元素看作一个整体
不相邻问题	插空法：先排其他元素，再插入
定序问题	除以定序元素的排列数
至少 / 至多	间接法：总数减去对立情况
分组分配	先分组（注意均分要除），再分配
相同元素分配	隔板法

为什么”至少一个”常用间接法？ 因为”至少一个”包含多种情况，直接分类要讨论 $1$ 个、$2$ 个、……，而它的对立面”一个都没有”只有一种情况。

二项式定理的联系

$(a+b{)}^n={\sum }_{k=0}^n{C}_n^k{a}^{n-k}{b}^k$

展开式的第 $k+1$ 项系数就是 $C_n^k$。这说明组合数不只是计数工具，也是代数展开的系数，两种解释互相印证。

常见误区

错误说法	问题
”排列组合是一回事”	差一个 $m!$
“看到’选’就用组合”	若选出后还要排序，则是排列
”分类和分步可以混用”	加法与乘法的适用条件不同
”均分问题不用除”	均分成 $k$ 组要除以 $k!$
”$C_n^m$ 中 $m$ 必须小于 $n/2$“	由对称性可转化为小于 $n/2$，但不是限制

引出

为什么组合数的递推公式恰好对应杨辉三角？

隔板法为什么能处理”相同元素分配”？

排列组合与概率中的古典概型是什么关系？

• 二项式定理：组合数作为展开系数
• 数学归纳法：证明组合恒等式
• 集合：子集个数与组合数
• 应用数学：古典概型的计数基础
• 离散数学：离散数学的整体框架
• 数学：数学学科入口