排列组合
约 1028 字大约 3 分钟
Python数学
2025-06-25
排列组合
一、基本概念区分
排列与组合
排列(Permutation)
指从 n 个不同元素中取出 m 个元素,按照一定顺序排列的方式数。
特点:元素顺序不同视为不同排列。
组合(Combination)
指从 n 个不同元素中取出 m 个元素,不考虑顺序的方式数。
特点:元素顺序不同视为相同组合。
二、核心公式 (需要重点记忆部分)
核心公式
1. 排列数公式(重要 需重点记忆)
- 全排列(m = n):从 n 个元素中取出 n 个全排列的方式数,记为 n!(n 的阶乘)。
n!=n×(n−1)×(n−2)×⋯×2×1
例如:5!=5×4×3×2×1=120。
- 选排列(m < n):从 n 个元素中取出 m 个排列的方式数,记为 P(n,m) 或 A(n,m)。
P(n,m)=n×(n−1)×⋯×(n−m+1)=(n−m)!n!
计算过程结合阶乘公式转化:
- 阶乘的定义是:对于正整数 n ,n!=n×(n−1)×(n−2)×⋯×2×1 ,并且规定 0!=1 。 观察 P(n,m)=n×(n−1)×(n−2)×⋯×(n−m+1) ,分子分母同时乘以 (n−m)! ,即:
P(n,m)=(n−m)![n×(n−1)×(n−2)×⋯×(n−m+1)]×(n−m)!=(n−m)!n×(n−1)×(n−2)×⋯×(n−m+1)×(n−m)×⋯×2×1=(n−m)!n!
例如:从 5 个元素中选 3 个排列,P(5,3)=5×4×3=60。
2. 组合数公式 (重要 需重点记忆)
从 n 个元素中取出 m 个的组合方式数,记为 C(n,m) 或 (mn)。
C(n,m)=m!P(n,m)=m!(n−m)!n!
例如:从 5 个元素中选 3 个组合,C(5,3)=3!2!5!=10。
三、重要性质与推论 (暂时不用记忆)
重要性质与推论
- 组合数的对称性
C(n,m)=C(n,n−m)
例:C(7,2)=C(7,5)=21。
- 组合数的递推公式(杨辉三角性质)
C(n,m)=C(n−1,m−1)+C(n−1,m)
适用于通过前一行组合数推导后一行(如杨辉三角第 n 行对应 C(n,0) 到 C(n,n))。
全组合数之和
从 n 个元素中取 0 个到 n 个的组合数之和等于 2n,即:
m=0∑nC(n,m)=2n
例:n=3 时,C(3,0)+C(3,1)+C(3,2)+C(3,3)=1+3+3+1=8=23。
排列与组合的关系
排列数可看作先选组合再排列:
P(n,m)=C(n,m)×m!
四、应用场景举例
案例
- 排列应用
排队问题:5 人排成一列,有 5!=120 种排法。
密码设置:4 位不同数字的密码,有 P(10,4)=5040 种可能。
- 组合应用
选小组:从 10 人中选 3 人组成小组,有 C(10,3)=120 种选法。
扑克牌问题:从 52 张牌中选 5 张,有 C(52,5)=2598960 种组合。
- 综合应用
- 分配问题:将 5 本书分给 3 人,每人至少 1 本,需结合排列与组合(先分组再分配)。
五、扩展:重复元素的排列与组合
扩展知识
- 重复排列
- n 个元素中有重复元素时,全排列数为:若有 n1,n2,…,nk 个相同元素(n1+n2+⋯+nk=n),则排列数为
n1!n2!…nk!n!
例:单词 “BOOK” 中字母的排列数为 2!4!=12(O 重复 2 次)。
- 重复组合(可重复选取)
- 从 n 个元素中可重复地取 m 个,组合数为
C(n+m−1,m)
例:买 3 种水果(可重复),共 5 种水果可选,方案数为 C(5+3−1,3)=C(7,3)=35。
六、公式记忆技巧
公式记忆技巧
排列:先选后排序,分母为 (n−m)!。
组合:仅选不排序,需除以 m!(消除顺序影响)。
核心关系:组合是排列的 “去序” 版本,即 C(n,m)=m!P(n,m)。