19.4
组合
研究从不同元素中选取而不计顺序的计数问题。
本文章目录
01 · 出发点
只关心选了谁，不关心排列顺序
从若干同学中选出一个三人小组时，小组成员写成甲乙丙或丙甲乙表示同一个集合。组合问题只关心选取的对象，不把同一批对象的不同排列当成新结果。
从 n 个不同元素中取出 m 个合成一组，称为一个组合。每个组合内部的 m 个元素可以有 m! 种排列，因此组合数等于相应排列数除以 m!。
02 · 概念
组合数与对称性
组合数 C_n^m 表示从 n 个不同元素中任选 m 个的方法数。选出 m 个与留下 n-m 个一一对应，所以 C_n^m=C_n^{n-m}。
组合数满足递推关系 C_n^m=C_{n-1}^m+C_{n-1}^{m-1}：按某个指定元素是否被选，把全部组合分成互斥的两类。
03 · 方法
组合问题的识别与计算
- 01
明确选择结果是无序集合，还是带有角色、位置的有序安排。
- 02
根据“选中”或“未选中”哪一侧数量更小，利用对称性简化计算。
- 03
遇到至少、至多或分类限制时，先按选取数量分类，再相加。
04 · 例题
把方法落到具体问题
从 8 名同学中选 3 人组成学习小组，共有多少种选法？
解
- 1
学习小组没有组内顺序，同样三人只算一种选法。
- 2
问题等价于从 8 个不同元素中选出 3 个元素的组合。
- 3
使用组合数公式 C₈³=8×7×6÷(3×2×1)。
05 · 辨析
容易忽略的条件与边界
回看
本节小结
- 组合只关心选取对象，不关心内部顺序。
- 组合数等于相应排列数除以所选元素的全排列数。
- 对称性和递推关系都可以用选取方案的一一对应解释。