组合 — C(n,r)

组合回答的问题是：从 n 个不同物品中，选 r 个（不考虑顺序），有多少种方法？

C(n,r) = n!r! × (n−r)! = P(n,r)r!

为什么 C(n,r) = P(n,r) / r!？

推导

P(n,r) 计算了"选 r 个并排列"的方案数。

但组合只关心"选了谁"，不关心顺序。

同一组 r 个物品有 r! 种排列方式。

所以组合数 = 排列数 / r! = P(n,r) / r! = n! / (r!(n-r)!)

例：从 5 人中选 2 人组队

n = 5, r = 2

C(5,2) = 5! / (2! × 3!) = 120 / (2 × 6) = 10

10 种选法：

{1,2} {1,3} {1,4} {1,5}

{2,3} {2,4} {2,5}

{3,4} {3,5}

{4,5}

帕斯卡三角 (杨辉三角)

帕斯卡三角是组合数的一个优美的几何表示，满足递推关系：

C(n,r) = C(n−1, r−1) + C(n−1, r)

为什么？考虑第 n 个物品：要么选它（对应 C(n-1, r-1)，即从剩余 n-1 个中再选 r-1 个），要么不选它（对应 C(n-1, r)，即从剩余 n-1 个中选够 r 个）。这两种情况互斥且穷尽。

1

11

121

1331

14641

15101051

1615201561

第 n 行第 r 列 = C(n,r)。例如高亮的 6 = C(4,2)。

历史：不叫"帕斯卡三角"更公平

虽然西方称之为"帕斯卡三角"（Pascal's Triangle, 1654），但这个结构在更早的东方文献中就已出现：

贾宪（约 1050 年，北宋）：在《释锁算术》中首次给出此三角，用于开高次方。

杨辉（1261 年，南宋）：在《详解九章算法》中引用贾宪的三角，因此中文世界称之为"杨辉三角"。

Omar Khayyam（约 1100 年，波斯）：也独立发现了此结构。

Blaise Pascal（1654 年，法国）：系统研究了这个三角的数学性质，并将其与概率论联系起来。

有重复组合 — Stars and Bars

如果允许重复选取，从 n 种物品中选 r 个的方案数为：

C(n+r−1, r)

这个公式也叫"隔板法"或 Stars and Bars（由美国概率学家 William Feller 在 1950 年的经典教材中推广）。

直觉理解：想象 r 颗星星（★）和 n−1 个隔板（|）排成一排，隔板把星星分成 n 组，每组代表某种物品被选了几个。例如从 3 种水果中选 4 个：★★|★|★ 表示"2 个苹果、1 个橙子、1 个香蕉"。总共 r + n − 1 个位置中选 r 个放星星（或 n−1 个放隔板），方案数 = C(n+r−1, r)。