01先把问题说具体
从 5 个互异元素中选 2 个,不考虑顺序,一共有多少种?
02一步步得到方法
组合按集合计数
先选 A 后选 B 与先选 B 后选 A 是同一个组合;若顺序重要则是排列。组合数 C(n,k) 可以按是否包含最后一个元素分成两类:不含它有 C(n−1,k),含它后还需从前 n−1 个选 k−1 个。
得到 C(n,k)=C(n−1,k)+C(n−1,k−1)。边界 C(n,0)=1 表示空集合,k>n 为 0。这个推导不需要先记阶乘公式。
滚动更新与 0/1 选择一致
dp[j] 表示当前已处理元素中选 j 个的方法数。每加入一个新元素,倒序 dp[j]+=dp[j−1],确保同一元素只加入一次;正序会让它在一轮中被反复使用。
阶乘式 n!/(k!(n−k)!) 可用于推导,但直接计算会产生巨大中间数。模数下求逆仅在分母可逆时合法,不能把普通整数除法照搬到任意模数。
计数定义先区分顺序是否重要
从 n 个不同元素中选 k 个、不计顺序,数量为 C(n,k)。若先按顺序选得到排列数,还需除以 k!,因为同一集合有 k! 种排列。抽样允许重复时又是不同计数模型。
Pascal 递推按某个指定元素是否被选择分两类,得到 C(n,k)=C(n−1,k−1)+C(n−1,k)。两类不重叠且覆盖全部情况,所以没有重复计数,也自然给出边界 C(n,0)=1。
03把一个小例子完全算清楚
从 5 个中选 2 个,只保留 j=0,1,2。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 初始 | [1,0,0] | 只存在空集合 |
| 处理 1、2 个 | [1,1,0] → [1,2,1] | 第二个元素可选可不选 |
| 处理 3、4、5 个 | [1,3,3] → [1,4,6] → [1,5,10] | 最后答案 10 |
窄屏可左右滑动表格,阅读完整计算与理由。
每个组合按是否含最新元素唯一分类,因此不会重复计数。
04为什么这个方法成立
- 空选择边界为 1。
- 含与不含最后元素两类互斥且覆盖所有组合。
- 倒序使来源仍为旧一层,逐元素归纳保持正确计数。
05把推导翻译成代码
Python · 可独立运行的教学实现
def choose(n,k):
if k < 0 or k > n:
return 0
k = min(k,n-k)
dp = [1]+[0]*k
for i in range(1,n+1):
for j in range(min(i,k),0,-1):
dp[j] += dp[j-1]
return dp[k]逐个理解关键决定
k = min(k,n-k)- 选择 k 个与排除 n−k 个一一对应,利用对称性减少状态。
range(min(i,k),0,-1)- 倒序且不更新 dp[0],保留唯一空集合。
06时间、空间与实现范围
时间 O(n·min(k,n−k)),空间 O(min(k,n−k)),整数位数增长的算术成本另计。
本方法可在每次加法后对任意正模数取模,不需要除法或逆元。
07改变条件,检查哪里会出错
C(n,0) 初始化为 0
空集合只有一种,不是没有方法;错误初值会使整表全零。
取模后直接用普通除法除阶乘
模除法需要逆元及互素条件,合数模数下尤其不能直接照搬实数公式。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
C(4,1) 与 C(4,3) 分别多少?
需要一点提示
选一个与排除一个。
查看解析与答案
都为 4。
从 3 个选 5 个呢?
需要一点提示
候选不足。
查看解析与答案
0。
模 6 下能用 3! 的逆元吗?
需要一点提示
3!=6 与模数不互质。
查看解析与答案
不能,逆元不存在;加法递推仍可正常计算模 6 的组合数。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
CP-Algorithms · 欧几里得与最小公倍数CP-Algorithms · 二进制快速幂