专题进阶 · 数学算法推荐总顺序 · 第 99 / 148 课

从是否选最后一个元素推导 Pascal 递推,区分组合与排列以及模逆元条件。

先学会这些,再进入本课 一维 DP 0/1 背包
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 数学算法

组合数Binomial Coefficients

用 Pascal 递推或阶乘与逆元计算;模数与分母可逆性决定公式能否直接使用。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

从是否选最后一个元素推导 Pascal 递推,区分组合与排列以及模逆元条件。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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. 空选择边界为 1。
  2. 含与不含最后元素两类互斥且覆盖所有组合。
  3. 倒序使来源仍为旧一层,逐元素归纳保持正确计数。

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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

C(4,1) 与 C(4,3) 分别多少?

需要一点提示

选一个与排除一个。

查看解析与答案

都为 4。

练习 2 · 边界与辨析

从 3 个选 5 个呢?

需要一点提示

候选不足。

查看解析与答案

0。

练习 3 · 变式与迁移

模 6 下能用 3! 的逆元吗?

需要一点提示

3!=6 与模数不互质。

查看解析与答案

不能,逆元不存在;加法递推仍可正常计算模 6 的组合数。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

CP-Algorithms · 欧几里得与最小公倍数CP-Algorithms · 二进制快速幂

理解之后,继续递进

继续当前专题:矩阵快速幂 →。跨专题先修要求会在下一课顶部提示。

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。