课程：组合计数 第一讲 排列组合入门

概念

加法原理与乘法原理

若将问题划分为若干两两互斥的情形 ，则总数为 （加法原理）。
若一个构造过程分成相继的若干步，且“每条合法方案”可由各步的选择唯一确定，则总数为各步可选数目的乘积（乘法原理）。

要点

• “互斥”= 不重不漏；“相乘”要求“路径唯一性”（不同步的选择拼起来不会重复/漏计）。
• “或”用加法，“且”用乘法；分类不互斥或步骤不独立会导致重/漏计。
• 和本讲探究对齐：在例题一中“车牌格式为两类”是互斥分类，用加法；类内每位字符独立选择，用乘法。

例子

• 例 1：解锁密码是“4 位数字”或“6 位数字”，总数 。
• 例 2：编号三位：首位 26 个大写字母，后两位各 10 个数字，总数 。
• 例 3：从两所学校各选一名代表参赛：第一所 种选法，第二所 种，总数 。

理解

• 把“问题空间”画成若干不相交的块（分类），块大小相加；
  把“构造路径”看作多步决策树，每前进一步分叉，整条路径唯一决定一个结果，路径数相乘。

---

排列与组合

从 个互异元素中“按顺序”选 个的方案数为 。
从 个互异元素中“无顺序”选 个的方案数为 。

要点

• 有序/角色区分 → 排列；无序/不分角色 → 组合。
• ；。

例子

• 例 1：从 人中选班长/副班长/学习委员（不同角色）：。
• 例 2：从 人中选 3 人组队（不分角色）：。
• 例 3：先选 4 人再指定其中两人担任“组长/副组长”（有序指派）：。

理解

• “组合”先选集合，“排列”在集合内再排位置；
  把“角色”视为“位置”，角色越多越偏向排列。

---

二项式系数

从 个互异元素中“无顺序”选取 个的方案数

要点

• “无序/角色不分”用组合；“选出来再打乱顺序”会重复计数。
• 对称性：（选 个等价于“弃掉 个”）。

例子 1

从 人中选 人组成小组：。小组内无职位区分。

---

定理

帕斯卡恒等式

对 ，

要点

• 固定某元素 ：不选 的方案数 ；选 的方案数 ；互斥相加。

例子

• 例 1：从 人中选 人，按“是否选到小明”分类。
• 例 2： 的系数递推可由该恒等式导出。
• 例 3：杨辉三角相邻两数之和等于下一行对应数。

理解

• “是否包含某元素”的二分，是最基本的互斥分类；该恒等式是这种分类的代数化。

---

• 二项式定理

  对任意实数 与整数 ，

  要点

  • 把 个括号中的每个选择 或 ，恰选 次 的方案数为 。
  • 常见推论：；（见“奇偶配对”理解）。

  例子

  • 例 1： 时总子集数为 。
  • 例 2： 时交错和为 （）。
  • 例 3：系数恒等式来自不同取值的代入（如 ）。

  理解

  • 01 选择的组合模型：每个括号“选/不选 ”，等价于从 个位置里选 个位置放 。合并同类项就把“无序选择”的本质暴露为组合数。

---

Vandermonde 恒等式

设 为非负整数，

要点

• 把 个元素分成两组：前 与后 ；从总共 个的选择等价于“在前组取 ，后组取 ”，对 求和。

 与探究对齐：你提出的“固定 个人”的推广，正确形式应是乘积 的求和，并包含 情形。

例子

• 例 1：从两所学校共 人中选 人，按两校人数切分计数。
• 例 2： 的 系数比较。
• 例 3：取 的对称情形可给出中心二项式的分拆。

理解

• “分块—卷积”：把整体的选择拆解为各子块上的选择，求和即系数卷积；与多项式乘法的系数卷积直觉一致。

---

加权恒等式（标记法）— 例：

对 ，

要点

• 计数“带一个标记元素的 人组”：先选组再标记 vs. 先定标记再补齐，二者计数相同。

例子

• 例 1：带“队长”的 人小队；
• 例 2：从 个点选 个并指定一个特殊点；
• 例 3：抽签时“抽到某人”的概率按两种方式计算一致。

理解

• “标记”把组合问题与线性因子连接：标记数 替代为 与规模降一的组合数，体现“先标记再自由选择”的思维。

---

例题

例题 1｜分类与步骤的边界感

题目：车牌样式有两类，互斥。

• A 类：2 个大写字母 + 4 个数字（如 AB1234）；
• B 类：3 个大写字母 + 3 个数字（如 ABC123）。
  字母和数字均可重复。问共有多少种车牌？

解：

• A 类：；B 类：。
• 两类互斥，用加法原理：
  
  要点：若把“先选类”与“填位”混淆成乘法，会误算；必须先辨析“或/且”。

---

例题 2｜排列还是组合？

题目：从 人中选出 3 人组成“班长、学习委员、生活委员”三职；
以及，从 人中选出 3 人组成“学习小组”。两问各有多少种方案？

解：

• 职位：有序（角色区分），。
• 小组：无序（角色不分），。

要点：若把小组当成排列，会把同一组的 种排法重复计数。

---

例题 3｜二项式定理的组合解释

题目：解释 与 的意义。

解：

• ：从 个元素中选任意子集（每个元素选/不选），总数 ；按子集大小分层，层大小为 ，相加得 。
• （当 ）：用加权计数（选 个记 权重），正负抵消到 。

---

探究

Round 1【疑问】回复

关于帕斯卡恒等式，我们说“固定一个人 P，考虑包含和不包含 P 的情况”，这个是否可以推广到固定 x 个人：

表示，对于 x 个人中，考虑每次选取 i 个，每次就有 个情况，每个情况的贡献就是括号内的那么多，这个对吗？

• 正确的推广是 Vandermonde 恒等式（你已经走在正确方向上了），应写成
  
• 组合意义：把 人分成“固定的 人集合 S”和“其余 人”。从 人里选 人，等价于“从 S 里选 人、从其余里选 人”，对 求和。
• 你的式子里“”会重复计数；应是乘积 。另外还需要包含 的项（不选 S 中的人）。
• 边界写法：可将求和写作 到 ，并按约定令 （当 或 ）以免专门处理越界。
• 特例 就是帕斯卡恒等式：
  

Round 2【理解】回应

二项式定理本质上就是由于 选取的 01 性质以及合并同类项的“无序/不分角色”性质，成为了组合数的直接体现。那些常见恒等式我觉得还需要多见一见，当作例子罗列一下。

完全同意。给你一份“常见恒等式速览”（都可用组合法或代数法证明）：

• 总数与奇偶分裂
  
• 加权求和（标记法）
  
  （推得 ）
• Hockey-stick（冰球杆）
  
• Vandermonde（你刚用到的）
  

Round 3【例题】讲评

例题一

你已定位错误来源。这里“车牌格式”两类互斥，每类内部“位次固定（字母位、数字位）”，不需要再乘 。
正确答案：

例题二

两种方法一致：

前者“按位填人”，后者“先选人再排位”，路径唯一所以不重不漏。

例题三

解释到位：

• 是按子集大小分层求和；
• （）来自“选择 的位置数目为 ，权重 的加权抵消”。

练习

训练

T1

设密码由 6 位字符组成。每位可为数字或大写字母，但必须至少包含 1 个字母。你如何用“先全计再容斥一个集合”的思路避免分类重叠？写出表达式（不必化简）。

考虑先计算出全部情况，然后减去一个字母都不包含的情况。

T2

从 人中选 4 人排成一行并指定其中两人为组长和副组长，与“先选 4 人再在其中指派组长和副组长”的乘法拆分是否一致？给出等式并说明为何无重复。

一样的，，在公式上还是理解上都一样的。
因为排成一行本身就是选取和分职两个动作的结合。
不过这个应该和这种选法也是等价的：直接从 n 个人里选两个当组长，再从 n-2 里选两个当副组长，也就是 。

T3

用组合解释说明 成立（提示：两种方式计数“带一个标记的 人组”）。

组合意义解释不出来。但是公式上是这样的：

T4

用 的二项式定理给出 的理由。

的二项式定理：

我不能证明。

批改与讲评（T1–T4）

T1 正确

设密码由 6 位字符组成。每位可为数字或大写字母，但必须至少包含 1 个字母。

你的容斥表达式无误：

T2 需订正与补齐

从 n 人中选 4 人排成一行并指定其中两人为组长和副组长，与“先选 4 人再在其中指派组长和副组长”的乘法拆分是否一致？

• 若不考虑队形，只做“先选 4 人，再指派组长/副组长（有序）”，应为
  
  你写成了 ，少乘了角色的次序 。

• 若题目真的包含“排成一行”（队形有序），则
  
  两者等价，因为 。

• 你提出的“先选两位组长、再选两位副组长”的想法要改成“先选组长，再选副组长，再选两名普通成员”，表达为
  
  它与上式等价，因为
  

T3 组合解释补上（代数推导里有小括号/阶乘笔误）

说明

• 组合意义：计数“带一个标记元素的 人组”。
  先选组再标记：；先标记再补全：。二者计同一对象，故相等。

• 代数式：
  

T4 给出两种证明“偶项和 = 奇项和”

证明 （）

代数法（用二项式定理）：

把两式相加/相减可得奇偶两部分各为 ，因此相等。

组合法

一、总子集数是

• 对于一个有 个元素的集合，每个元素都有两种独立选择：选/不选。
• 用乘法原理， 种选择，对应所有子集的总数。

二、总子集数也等于

• 按“子集大小”分层统计：大小为 的子集有 个。
• 把各层相加，就得到“所有子集”的总数：
  

三、为什么“偶数大小的子集数 = 奇数大小的子集数 = ”

• 设定一个固定元素 。定义配对映射
  
  即“把 的状态在 里翻转”（对称差：如果 就删掉，否则就加入）。

这个映射有三个关键性质：

• 双射（可逆）：，所以它把所有子集配成不相交的二元对。
• 改变奇偶：，因此“偶 ↔ 奇”。
• 无不动点：不存在 使 （因为总在翻转 ）。

是自反双射且无不动点，并且把“偶大小子集”双射到“奇大小子集”。于是两类子集数量相等。再用总数 ，得各为
（这里要求 ；当 时只有空集，偶类为 1，奇类为 0）。

于是“偶大小子集”和“奇大小子集”一一对应，数量相等。两类合在一起是 ，所以各自都是 ：

四、直观例子（，全集 ，取 ）

子集与配对：

• （大小 0 ↔ 1）
• （1 ↔ 2）
• （1 ↔ 2）
• （2 ↔ 3）

偶与奇严格成对，所以偶数大小有 4 个，奇数大小也有 4 个，各为 。

五、反转-配对模板（aka 符号翻转/反演套路）

• 选一个可“翻转”的局部属性（比如是否包含固定元素 P，或是否左乘一个固定换位 τ）。
• 定义映射 φ：执行一次翻转。证明两点：
  • 自反：φ(φ(x))=x（于是天然成“成对”结构）。
  • 无不动点：φ(x)≠x（确保不会把某个元素配到自己）。
• 说明翻转会改变你关心的“二值属性”（奇↔偶、正↔负、含 P ↔ 不含 P）。
• 结论：
  • 不带权计数：两类元素“成双成对”，所以数量相等。
  • 带符号权重：一对里的权重相反，求和彼此抵消为 0。

六、扩展例题

1. 子集奇偶对半

• 取全集 [n] 与固定元素 P，φ(S)=S△{P}。大小 ±1，奇偶互换；双射配对 ⇒ 奇偶各 2^{n-1}。

2. 置换的偶奇对半

• 在 S_n 里取固定换位 τ（如交换 1 与 2），φ(π)=τ∘π。换位改变置换的奇偶性；且 φ 的平方是恒等。因此偶置换与奇置换数量相同。

【回答】第一个问题：

的含义为选取所有大小为 的全集 的大小为 的子集个数。

那么在求和的过程中，偶数大小子集为正，奇数为负；

考虑定义关于元素 函数 表示取 ，那么具有以下性质：

这代表构成了奇子集和偶子集的双射，他们个数相等。

所以

证毕。

复习

• 两大原则
  • 加法原理：互斥分类相加；乘法原理：路径唯一性相乘。
• 排列与组合
  • 有序/分角色； 无序/不分角色；。
• 经典恒等式与理解
  • 帕斯卡：按“是否含某元素”分类。
  • 二项式：01 选择 + 合并同类项。
  • Vandermonde：分块选择 + 卷积。
  • 奇偶各半：翻转固定元素的配对双射。
  • 标记法：，先选组再标记 vs 先标记再补齐。