组合

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 · 方法

组合问题的识别与计算

1. 01

   明确选择结果是无序集合，还是带有角色、位置的有序安排。

2. 02

   根据“选中”或“未选中”哪一侧数量更小，利用对称性简化计算。

3. 03

   遇到至少、至多或分类限制时，先按选取数量分类，再相加。

04 · 例题

把方法落到具体问题

05 · 辨析

容易忽略的条件与边界