笔记13-《程序员的数学》排列组合

2026.10.30 15:00 下午

排列组合
用 Ruby 验证
这一章真正在讲什么

排列组合

计数的基本手法
- 将计数对象与整数对应起来
  - 典型做法：选出一张还没数的牌，说「3」，重复直到数完
  - 只要与整数正确对应，计数的结果就是正确的
- 计数时必须注意遗漏和重复
  - 遗漏 = 没有数全（明明还有没数到的，却错认为数过了）
  - 重复 = 已经数了的又多数了一次
  - 有遗漏或重复就不能正确计数；没有两者就能正确计数
- 牌少的时候可以用手指着数；牌多到几千几万张时手数不过来
  - 这时需要找到计数对象与整数之间的**「对应规则」**
  - 为此必须理解计数对象具有怎么样的特性和结构
植树问题（不要忘记 0）
- 思考题：在 10 米长的路上，从路的一端起每隔 1 米种一棵树，需要种多少棵？
- 解答：距离路的一端 0、1、2、3、4、5、6、7、8、9、10 米的位置种树
- 答案：11 棵
- 归纳总结：通常将 n 个数据从 0 开始编号，最后的数据为 n-1 号
  - 碰到这样的思考题很少有人答错，实际编程时面对同样的问题却有很多人出错
  - 只要把「第 k 个数据是 k-1 号」作为普遍规则掌握，就不容易出错
- 更进一步：棵数少时用手指数还不够，更要用变量 n 把问题抽象出来
加法法则
- 思考题：10 张红桃数字牌（A 到 10）+ 3 张红桃花牌（J、Q、K），红桃共多少张？
- 答案：13 张
- 加法法则：将无「重复」元素的两个集合 A、B 相加，得到 $A \cup B$ 的元素数
  $|A \cup B| = |A| + |B|$
- 只在集合中没有重复元素的条件下成立
容斥原理
- 思考题：2 的倍数和 3 的倍数（6 的倍数是重复部分）
- 容斥原理 = 「考虑了重复元素的加法法则」
  $|A \cup B| = |A| + |B| - |A \cap B|$
- 使用时必须弄清「重复的元素数有多少」 —— 这也是「认清计数对象性质」的一个例子
乘法法则
- 思考题：4 种花色，每种 13 个级别，共多少张牌？
- 从集合 A 和集合 B 中各取出一个元素作为一组，所有这种组合的集合即 $A \times B$
  $|A \times B| = |A| \times |B|$
- $A = \{$ 红桃, 黑桃, 方片, 梅花 $\}$ ， $B = \{$ A, 2, 3, …, 10, J, Q, K $\}$
- $A \times B$ 列举出来就是 52 个配对
- 扑克牌只有 52 张，可以画图确认；但只要理解计数对象的性质，遇到难以图示的大数也能正确计算
- 思考题：3 个写有 1 到 6 的骰子并列组成 3 位数，共能形成多少个数字？
置换
- 思考题：A、B、C 三张牌按顺序排列，共有多少种排法？
- 答案：6 种（ABC、ACB、BAC、BCA、CAB、CBA）
- 推导步骤
  - 第 1 张牌从 3 张中选 → 3 种
  - 第 2 张牌从已选的第 1 张以外的 2 张中选 → 2 种
  - 第 3 张牌从已选的前两张以外的 1 张中选 → 1 种
  - 总数 = $3 \times 2 \times 1 = 6$
- n 个事物按顺序排列称为置换（substitution），总数
  $n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$
- 关于 $0! = 1$
  - 学生：为什么 0! 是 1 呢？
  - 老师：这是定义。
  - 学生：这个理由难以接受啊！总觉得 0! 应该是 0 才对。
  - 老师：这样的话可是推倒不了第一张多米诺骨牌的喔！
排列
- 从 n 个事物中取出一部分进行排列
- 思考题：从 A、B、C、D、E 共 5 张牌中取 3 张排列，有多少种排法？
- 答案：60 种
- 书上列出了全部 60 个排列
- 注意排列与置换相同，都要考虑顺序 —— ABD 和 ADB 元素相同但顺序不同，是不同的排列
- 排列总数记作 $P$ ，用阶乘形式表示： $\dfrac{n!}{(n-k)!}$
组合
- 置换和排列都考虑顺序，组合不考虑顺序
- 思考题：从 5 张牌中取 3 张，ABE 和 BAE 视为同一组
- 答案：10 种（ABC、ABD、ABE、ACD、ACE、ADE、BCD、BCE、BDE、CDE）
- 计算方法（先按顺序数，再除重复）
  - 首先和排列一样「考虑顺序」进行计数
  - 按排列计数时 ABC、ACB、BAC、BCA、CAB、CBA 这 6 种在组合中算 1 组 → 产生 6 倍的重复计数
  - 重复度 6 就是 3 张牌的置换总数 $3 \times 2 \times 1$
  - 所以组合总数 = 排列总数 ÷ 重复度
    $C_n^k = \frac{P_n^k}{k!} = \frac{n!}{k!(n-k)!}$
- 归纳抽象：从 n 张牌取 k 张的组合总数
  - 先按顺序取出 k 张（排列总数）
  - 除以 $k!$ 这个重复度

用 Ruby 验证

def fact(n)
  n <= 1 ? 1 : n * fact(n - 1)
end

def perm(n, k)
  (0...k).inject(1) { |acc, i| acc * (n - i) }
end

def comb(n, k)
  perm(n, k) / fact(k)
end

# 植树问题：10 米路，每 1 米一棵，从 0 米处开始
n = 10
puts "植树问题 = #{n + 1} 棵"          # 植树问题 = 11 棵

# 加法法则：红桃 10 数字牌 + 3 花牌
puts "红桃总数 = #{10 + 3}"             # 红桃总数 = 13

# 乘法法则：4 花色 x 13 级别
puts "扑克牌总数 = #{4 * 13}"           # 扑克牌总数 = 52

# 3 个骰子组成 3 位数
puts "3个骰子组成3位数 = #{6 ** 3}"     # 3个骰子组成3位数 = 216

# 置换：3 张牌
puts "3张牌置换 = #{3 * 2 * 1}"          # 3张牌置换 = 6

puts "5! = #{fact(5)}"                  # 5! = 120
puts "52! = #{fact(52)}"                # 52! = 80658175170943878571660636856403766975289505440883277824000000000000

# 排列与组合
puts "5P3 = #{perm(5, 3)}"              # 5P3 = 60
puts "5C3 = #{comb(5, 3)}"              # 5C3 = 10

输出的 52! 与书上给的那个 74 位整数逐字一致。

这一章真正在讲什么

这一章有三个公式，但更值得记的是把它们串起来的那条链：

把对象与整数对应  →  找到对应规则  →  抽象成变量 n  →  用法则压缩
   （植树问题）      （第k个是k-1号）    （不靠手数）    （加法/乘法/容斥）

作者反复强调的那句「认清计数对象的性质」，就是这条链的枢纽：先看清对象的结构，公式才能套上去。

而 $0! = 1$ 那个课前对话，是整章最有意思的地方 —— 一个纯定义，却非如此不可：

$0! = 1$ 让递推能往下推（ $n! = n \times (n-1)!$ 在 $n=1$ 时给出 $1! = 1 \times 0!$ ，要成立必须 $0! = 1$ ）
老师的比喻是「推倒不了第一张多米诺骨牌」—— 定义不是为了凑公式，是为了让链条能启动

这一点在下一章（递归）会变成完整的故事：递归的终止条件必须自己定义，而这个定义往往没有「自然」的理由，只能选一个能让整条链跑通的值。

学习 :分类
排列组合, 计数 :标签