PYTHON LESSON 113
计数原理与排列组合
掌握加法原理与乘法原理，会用组合数 C(n, m) 和排列数 A(n, m) 编程求解计数问题。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- from math import comb, perm 导入计数函数
- comb(n, m) 组合数：选出 m 个不分顺序
- perm(n, m) 排列数：选出 m 个要排顺序
01 · 核心概念
加法原理、乘法原理与 C(n, m)、A(n, m)
加法原理、乘法原理与 C(n, m)、A(n, m)：计数问题的两大法宝：分类用加法原理（选法互斥，加起来）；分步用乘法原理（一步接一步，乘起来）。穿衣搭配是“先选上衣、再选裤子”两步，所以 3 × 2 = 6 种。判断用加还是乘，是解题第一步。
GESP Python 8 级 · 计数原理GESP Python 8 级 · 排列与组合概率需要在计数结果上再建立样本空间，不等同于组合数本身。
02 · 语法与规则
先记住这 3 条，再开始写程序
from math import comb, perm 导入计数函数先准确读出这条写法的结构与作用。
comb(n, m) 组合数：选出 m 个不分顺序换一组最小数据，手工推演一次结果。
perm(n, m) 排列数：选出 m 个要排顺序再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 计数原理实战：握手问题与班委选举
from math import comb, perm
# 场景一：全班 30 人，每两人握一次手，共握几次？
n = 30
print("全班", n, "人，共握手", comb(n, 2), "次")
# 场景二：从 5 名候选人中选班长、副班长各 1 人（分工不同，要讲顺序）
print("5 人中选正、副班长，共", perm(5, 2), "种选法")
# 场景三：从 5 人中选 3 人参加值日（不分岗位，不讲顺序）
print("5 人中选 3 人值日，共", comb(5, 3), "种选法")
# 乘法原理：3 件上衣和 2 条裤子，穿衣搭配有几种？
print("3 件上衣配 2 条裤子，共", 3 * 2, "种搭配")全班 30 人，共握手 435 次 5 人中选正、副班长，共 20 种选法 5 人中选 3 人值日，共 10 种选法 3 件上衣配 2 条裤子，共 6 种搭配
comb 与 perm 来自 math 库（Python 3.8+）；本题所有结果都不超整数范围，直接输出即可。
04 · 逐步理解
每一步只解决一个问题
- 01
先分清“分类”还是“分步”
计数问题的两大法宝：分类用加法原理（选法互斥，加起来）；分步用乘法原理（一步接一步，乘起来）。穿衣搭配是“先选上衣、再选裤子”两步，所以 3 × 2 = 6 种。判断用加还是乘，是解题第一步。
total = 3 * 2 # 上衣 3 种 × 裤子 2 种 - 02
握手问题：从 n 个人里选 2 个
每两人握一次手，等同于“从 30 人中任选 2 人组成一对”，共有 C(30, 2) = 30 × 29 ÷ 2 = 435 对。注意这里握手不分先后，小明和小红握手与小红和小明握手是同一次。
comb(30, 2) # = 435 - 03
组合 comb：选出就行，不排队
comb(n, m) 表示从 n 个不同元素中选出 m 个的方案数，选出来的元素不分顺序。选 3 人值日，谁先被选中都一样，所以用 comb(5, 3) = 10。
from math import comb print(comb(5, 3)) # 10 - 04
排列 perm：选出还要分工
选班长和副班长不一样：小明当班长、小红当副班长，与反过来是两种结果。要讲顺序就用排列数 perm(5, 2) = 5 × 4 = 20。记忆口诀：分工讲顺序用 A，只挑人不管岗位用 C。
from math import perm print(perm(5, 2)) # 20 - 05
公式也要会推导
C(n, m) = n! ÷ (m! × (n−m)!)，A(n, m) = n! ÷ (n−m)!。竞赛中若没有 math 库可用，就用循环手写：A(n, m) 是从 n 开始连乘 m 个数；C(n, m) = A(n, m) ÷ m!。
def my_perm(n, m): ans = 1 for i in range(m): ans *= n - i return ans - 06
大数取模的赛场习惯
计数结果常常大得惊人（C(100, 50) 有 29 位），竞赛题目常要求“对 10^9+7 取模”。Python 整数不溢出是巨大优势，但取模规则要记牢：加、减、乘可以随时取模，除法不行。
MOD = 10**9 + 7 print(comb(100, 50) % MOD)
05 · 练习与检验
自己写出来，才算真正学会
- 1运行计数器，核对握手次数 435
- 2把全班人数改成 40 再算一次
- 3分清除 perm 与 comb 的使用场景
- 4用乘法原理解释 3 件上衣 2 条裤子的搭配数
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
数学基础计数原理、组合数与计算几何基础明确有序/无序、互斥/分步与几何退化边界，再把公式转为稳定程序。＋
正式定义
加法原理用于互斥方案分类求和，乘法原理用于依次完成步骤求积；排列关心顺序，组合不关心顺序。计算几何用坐标、向量、距离和方向关系把图形条件转成数值判定。
必须掌握
- A(n,m)=n!/(n-m)!，C(n,m)=n!/(m!(n-m)!)，并有 C(n,m)=C(n,n-m)。
- 杨辉三角递推 C(n,m)=C(n-1,m-1)+C(n-1,m)，边界 C(n,0)=C(n,n)=1。
- 取模下的组合数算法取决于 n、模数是否为质数、查询次数和是否允许预处理。
- 距离比较应优先比较平方，避免不必要的 sqrt 和浮点误差。
- 三角形必须满足任意两边之和大于第三边；共线、重合、零长度是几何边界。
- 浮点比较应按题目误差使用容差；整数坐标能用叉积时优先保持整数计算。
常见误区
- 未判断顺序是否重要就套排列组合公式
- 模意义下直接做普通除法
- 浮点数直接用 ==
- 漏掉共线或退化图形
适用边界
- 概率需要在计数结果上再建立样本空间，不等同于组合数本身。
- 复杂计算几何涉及方向、相交、凸包等更多主题，本章只覆盖课程实际使用的基础判定。
程序组织模块、导入与常用标准库正确导入模块，并按用途查找 math、random、statistics、collections、heapq、bisect 等标准工具。＋
正式定义
模块是可导入的 Python 代码单元，包把模块组织成层次。import 先加载模块并创建模块对象，再把名字绑定到当前命名空间；标准库随 Python 分发，不等于第三方包。
必须掌握
- import module 保留清晰命名空间；from module import name 只导入指定名字；避免 from module import *。
- math 提供 sqrt、floor、ceil、gcd、log、sin 等数学函数和 pi、e 等常量。
- random 用于伪随机模拟，不适合密码安全；需要安全随机时使用 secrets。
- collections.deque 适合双端队列，Counter 适合计数，defaultdict 可按工厂创建缺省值。
- heapq 实现最小堆，bisect 在已排序序列中二分定位，itertools 提供高效迭代组合工具。
- if __name__ == '__main__': 用来区分文件被直接运行还是被导入。
常见误区
- 文件名写成 math.py 导致遮蔽标准库
- import * 污染命名空间
- 把 random 当成加密随机数
- 没有理解工具的数据复杂度就盲目调用
适用边界
- 标准库非常大，本章覆盖课程会实际依赖的入口；具体函数签名应结合本站条目与运行时帮助查询。
- Turtle 需要图形窗口，本站文本判题环境不伪造其画布。
算法方法质数、约数、最大公因数与筛法建立整数整除体系，掌握试除、欧几里得算法、唯一分解和筛法的条件与复杂度。＋
正式定义
若整数 a 能被非零整数 b 整除，则 b 是 a 的约数。大于 1 且只有 1 和自身两个正约数的整数是质数；每个大于 1 的整数都能唯一分解为质数幂的乘积（忽略次序）。
必须掌握
- 0 和 1 都不是质数；判定 n 是否为质数只需试除到 floor(sqrt(n))。
- gcd(a,b)=gcd(b,a mod b) 构成欧几里得算法；lcm(a,b)=abs(a//gcd(a,b)*b) 并要处理 0。
- 约数成对出现，可枚举到平方根；完全平方数的平方根只计一次。
- 埃氏筛从 p² 开始标记质数 p 的倍数，总体 O(n log log n)；线性筛保证每个合数被最小质因子筛一次。
- 分解质因数后，约数个数与约数和可以由各质因数指数公式计算。
- 模运算支持加减乘分配；模除法不能直接用整数除法，需满足可逆条件并求逆元。
常见误区
- 把 1 判成质数
- 试除上界漏掉平方根
- 完全平方数的约数重复统计
- 取模后直接做普通除法
适用边界
- 大整数质性测试和密码学分解需要更高级算法，不应把试除法扩展到任意规模。
- 题目若涉及负数约数、0 的约数或模数非质数，必须先明确数学定义。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
完成检查