组合数

定义与例子

若集合 (或多重集) `Y sube X`, 且 `|Y| = m`, 则称 `Y` 是 `X` 的一个 `bm m`-子集. 设 `n, m` 是非负整数, `m le n`, 定义 `n` 选 `m` 的组合数为集合 `X_n = {1, 2, cdots, n}` 的 `m`-子集数, 记为 `(n;m) = C(n, m) = C_n^m`. 这里的字母 C 可理解为 choice 或 combination. 特别地, `(n;0) -= 1`, 因为大小为 0 的子集只有空集; `(n;n) -= 1`, 因为大小为 `n` 的子集只能是 `X_n` 自身. 组合数最直观的解释是, 从 `n` 件不同物品中选出 (无序的) `m` 件的方法数.

有了组合数的概念, 第二类计数问题 `F_2, I_2, S_2` 就都得到了解决.

考虑十二重计数问题之 `I_2`, 即将 `m` 件相同物体放入 `n` 个不同盒子, 且使得每个盒子的物体数只能是 0 或 1 的方法数. 显然只需从 `n` 个盒子选出物体数为 1 的盒子即可. 故 `|I_2| = (n;m)`.

考虑十二重计数问题之 `S_2`, 即将 `m` 件相同物体放入 `n` 个不同盒子, 且使得每个盒子不空的方法数. 换个角度来看, 要将物体分为有序的 `n` 份, 只需在物体间插入 `n-1` 个隔板即可. 比如, 将 10 个 o 放进 6 个不同的盒子, 只需在它们之间插入 5 个隔板: o|oo|ooo|o|o|oo 需要注意, 和物体一样, 这里的隔板是不可区分的对象. 由于每个盒子不空, 问题转化为在 `m-1` 个空隙中插入 `n-1` 个隔板的方法数, 于是 `|S_2| = (m-1;n-1)`. `|S_2|` 还是:
1. 方程 `sum_(i=1)^n x_i = m` 的正整数解的个数;
2. 用数字 `1~n` 组成的长度为 `m` 的严格递增序列数.

考虑十二重计数问题之 `F_2`, 即将 `m` 件相同物体放入 `n` 个不同盒子的总方法数. 考虑 `n-1` 个隔板, 由于盒子可以为空, 这些隔板和物体之间的次序也是任意的. 比如将 10 个 o 放进 6 个不同的盒子的一种方法是: o||oo|||ooooooo 问题转化为将 `n-1` 个隔板与 `m` 件物体排成一行的组合数. 注意隔板与物体都不可区分, 这相当于在 `m+n-1` 个位置上选出 `m` 个物体, 即 `|F_2| = (m+n-1;m)`. `|F_2|` 还是:
1. 方程 `sum_(i=1)^n x_i = m` 的非负整数解的个数;
2. 多重集 `{oo * 1, oo * 2, cdots, oo * n}` 的 `m`-子集数;
3. 用数字 `1~n` 组成的长度为 `m` 的 (不严格的) 递增序列数.

[来自群友 灰色答案] 一天之中共有 6 节课, 语文和数学课各 3 节; 现要求任意两节数学课不能相邻, 问有几种排课方法?

我们将这天的第 0 节和第 7 节课固定为语文课, 问题就化为在 5 节语文课间插入 3 个隔板, 因此有 `(4;3) = 4` 种排课方法.

组合数的计算, Pascal (杨辉) 三角

我们推导组合数的一些简单性质. 下面所推导的恒等式, 有些没有给出参数 `n, m, k` 等的取值范围, 这时按照组合数的定义考虑它们的范围即可.

对称性 `(n;k) = (n;n-k)`.

组合证明: 设 `|X| = n`, 因为 `X` 的每个子集 `Y` 和它的余集 `X \\ Y` 一一对应, 所以选出 `k`-子集的方法数等于选出 `n-k`-子集的方法数.

选班长恒等式 `(n;k) = n/k (n-1;k-1)`.

[来自 widcardw] 组合证明: 在 `n` 个人中选出 `k` 个班委, 再从班委中选出一个班长, 方法数为 `(n;k) k`; 另一方面, 在 `n` 个人中选出一个班长, 再从剩下 `n-1` 人中选出 `k-1` 个班委, 方法数为 `n (n-1;k-1)`.

Pascal 恒等式 `(n+1;k) = (n;k-1) + (n;k)`.

组合证明: 事先将 `n+1` 件物品标号为 `1, 2, cdots, n+1`. 现从 `n+1` 件物品中选取 `k` 件, 如果其中含有第一件物品, 则需要从剩下 `n` 件中再选取 `k-1` 件, 有 `(n;k-1)` 种选法; 如果其中不含第一件物品, 则需要从剩下 `n` 件中选取 `k` 件, 有 `(n;k)` 种选法.

Pascal (杨辉) 三角 利用 `(n;0) = (n;n) = 1` 和 Pascal 恒等式, 将组合数列成一个等腰三角形数表: `(0;0)`
`(1;0) quad (1;1)`
`(2;0) quad (2;1) quad (2;2)`
`(3;0) quad (3;1) quad (3;2) quad (3;3)`
`(4;0) quad (4;1) quad (4;2) quad (4;3) quad (4;4)`
`(5;0) quad (5;1) quad (5;2) quad (5;3) quad (5;4) quad (5;5)`
`cdots` 即 `1`
`1 quad 1`
`1 quad 2 quad 1`
`1 quad 3 quad 3 quad 1`
`1 quad 4 quad 6 quad 4 quad 1`
`1 quad 5 quad 10 quad 10 quad 5 quad 1`
`cdots` 其中三角形两腰上的数都等于 1, 数表中任意其它数都等于它的直接左上和直接右上方的数字之和.

组合恒等式

这里收集一些关于组合数 `(n;m)` 的恒等式. 约定 `0^0 = 1`, `sum_(i=k)^(k-1) = 0`, `prod_(i=k)^(k-1) = 1`.

二项式定理 `n` 为非负整数, `x, y` 为任意实数, 则 `(x+y)^n = sum_(k=0)^n (n;k) x^k y^(n-k)`. 因此组合数 `(n;k)` 也称为二项式系数.

在二项式定理中取 `x = y = 1` 有 `2^n = sum_(k=0)^n (n;k)`. 取 `x = 1`, `y = -1` 有 `0 = sum_(k=0)^n (n;k) (-1)^k`, 即 `sum_(k" is odd") (n;k) = sum_(k" is even") (n;k)`.

Vandermonde 恒等式 `m, n` 为非负整数, 则 `(m+n;k) = sum_(i=0)^k (m;i)(n;k-i)`.

在 Vandermonde 恒等式中令 `m = n = k` 有 `(2n;n) = sum_(i=0)^n (n;i)^2`.

朱世杰恒等式 (元代) 设 `m, n` 为非负整数, 则 `(m+n+1;n+1) = sum_(i=0)^m (n+i;n)`. 令 `n = k`, `m = n-k`, 得左斜公式: `(n+1;k+1) = sum_(i=0)^(n-k) (k+i;k)` `= sum_(i=k)^n (i;k)`. 令 `m = k`, `n = m-k`, 得右斜公式: `(m+1;k) = sum_(i=0)^k (m-k+i;i)` `= sum_(i=0)^k (m-i;k-i)`.

            1
		  1  (1)
		1  (2) [1]
	  1  (3)  3   1
	1  (4)  6   4   1
  1  (5)  10  10  5   1

设 `m, n` 是非负整数, `m gt n`, 则 `sum_(i=0)^n {:(n;i):}/{:(m;i):} = (m+1)/(m+1-n)`.

应用右斜公式: 左边 `= 1/{:(m;n):} sum_(i=0)^n (m-i;n-i)` `= {:(m+1;n):}/{:(m;n):} =` 右边.

[来自 概率论课本] 关于 Pascal 分布的恒等式 `sum_(k ge n) (m+k-1; k) p^k q^m` `= sum_(k=0)^(m-1) (n+m-1; k) p^(n+m-1-k) q^k` `= sum_(k=0)^(m-1) (n+k-1; k) p^n q^k`. 其中 `p+q = 1`.

上式记为 (1) = (2) = (3).
1. 先证 (2) = (3). 将 `p^(m-1-k) = (1-q)^(m-1-k)` 二项展开得 `(2) // p^n` `= sum_(k=0)^(m-1) (n+m-1; k) p^(m-1-k) q^k` `= sum_(k=0)^(m-1) (n+m-1; k) q^k sum_(j=0)^(m-1-k) (m-1-k; j) (-q)^j` 令 `t = j+k`, 利用负二项系数 `(m-1-k; j) (-1)^j = (j+k-m; j)`, 上式等于 `sum_(t=0)^(m-1) q^t sum_(j=0)^t (n+m-1; t-j) (t-m; j)`. 最后利用 Vandermonde 恒等式, 上式等于 `sum_(t=0)^(m-1) q^t (n-1+t; t) = (3) // p^n`.
2. 再证 (1) = (2). 注意到 `(1) = sum_(k ge n) (-m; k) (-p)^k q^m` `= (1-p)^-m q^m - sum_(k=0)^(n-1) (-m; k) (-p)^k q^m` `= 1 - sum_(k=0)^(n-1) (m+k-1; k) p^k q^m`,
   `(2) = (p+q)^(n+m-1) - sum_(k=m)^(n+m-1) (n+m-1; k) p^(n+m-1-k) q^k` `= 1 - sum_(k=0)^(n-1) (n+m-1; k) p^k q^(n+m-1-k)`. 再由 (2) = (3) 即知 (1) = (2).

[来自 卡尔・夏洛克] 证明 `sum_(k=0)^n 1/(n-k)! sum_(i=0)^k (-1)^i/i! = 1`.

先倒序求和 `k mapsto n-k`, 再令 `j = i+k`: 原式等于 `sum_(k=0)^n 1/k! sum_(i=0)^(n-k) (-1)^i/i!` `= sum_(j=0)^n sum_(i=0)^j (-1)^i/((j-i)!i!)` `= sum_(j=0)^n 1/j! sum_(i=0)^j (j;i) (-1)^i` `= 1 + sum_(j=1)^n 1/j! (1-1)^j` `= 1`.

[来自群友 幂零群] 组合数的估计
1. `sum_(k=0)^m (n;k) le n^n/(m^m(n-m)^(n-m))`, `m le n//2`.
2. `(n;k)^-1 le k!/n^k "e"^(k^2//n)`.

1. 将 `x = m/(n-m)` 代入二项展开 `sum_(k=0)^n (n;k) x^k = (1+x)^n` 得到 `sum_(k=0)^n (n;k) (m/(n-m))^k = (n/(n-m))^n`. 于是 `(n/(n-m))^n ((n-m)/m)^m` `= sum_(k=0)^n (n;k) ((n-m)/m)^(m-k)` `ge sum_(k=0)^m (n;k)`.
2. `(n;k)^-1` `= k!/(n(n-1) cdots (n-k+1))` `= k!/n^k exp(-sum_(i=1)^(k-1) ln(1-i/n))`. 由于函数 `-ln(1-x)` 单调增, 上式 `exp` 内的和式小于等于积分 `n int_0^(k//n) -ln (1-x) dx` `= n [x + (1-x)ln(1-x)]_0^(k//n)` `le n [x - x (1-x)]_0^(k//n)` `= k^2/n`. 在估计积分的时候又用到切线不等式 `ln(1-x) le -x`.

多重指标运算与多项展开

多重指标 是一个整数向量 `alpha = (alpha_1, alpha_2, cdots, alpha_n)`, 它的运算规则如下: `alpha +- beta` 就是一般向量的加减法,
`alpha le beta` `iff alpha_i le beta_i`, `AA i`,
`|alpha| = sum alpha_i`,
`alpha! = prod alpha_i!`, `quad alpha ge 0`,
`(alpha; beta) = (alpha!)/(beta!(alpha-beta)!)` `= prod (alpha_i; beta_i)`, `quad alpha ge beta ge 0`. 在多元微分学中, 设 `x = (x_1, cdots, x_m)`, 可以定义 `x^alpha = prod x_i^(alpha_i)`,
`D^alpha = prod D_i^(alpha_i)`, `quad D_i^j = del^j/(del x_i^j)`.

设 `n, k` 为多重指标, 则 `D^k x^n // n! = { x^(n-k) // (n-k)!, k le n; 0, "otherwise"; :}`

多项展开 `(sum_(i=1)^m x_i)^n = sum_(|alpha| = n) (n!)/(alpha!) bm x^alpha`. 对 `bm x` 的维数 `m` 作归纳, 并使用二项式定理即可证明此公式. 其中 `(n!)/(alpha!)` 称为多项式系数. 此公式的项数是方程 `|alpha| = n` 的非负整数解数, 等于 `(n+m-1;n)`.

多项展开公式中的组合学 `m = n = 3` 时, 多项展开有 10 项: `(a+b+c)^3` `= a^3+b^3+c^3` `+ 3a^2 b + 3b^2 c + 3c^2 a + 3a b^2 + 3b c^2 + 3c a^2` `+ 6a b c`. 利用对称求和, 简写为 `(a+b+c)^3 = sum_(sym) a^3 + 3 sum_(sym) a^2 b + 6 a b c`. 展开式中的次数 `3 = 2 + 1 = 1+1+1` 穷举了 3 的分拆. `sum_(sym) a^3 b^0 c^0` 中各次数出现的次数为 `1, 2` (次数 3 出现 1 次, 次数 0 出现 2 次), 因此它包含 `(3; 1","2) = 3` 项; `sum_(sym) a^2 b^1 c^0` 中各次数出现的次数为 `1, 1, 1`, 因此它包含 `(3; 1"," 1"," 1) = 6` 项. 同理 `(a+b+c+d)^4` `= sum_(sym) a^4 + 4 sum_(sym) a^3 b + 6 sum_(sym) a^2 b^2 + 12 sum_(sym) a^2 b c + 24 a b c d` 4 的分拆为 `4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1`. 两边的项数为 `(7;3) = (4; 1"," 3) + (4; 1"," 1"," 2) + (4; 2"," 2) + (4; 1"," 2"," 1) + (4; 4)`.

Carlson 不等式 设 `x_1, cdots, x_n` 为非负整数, 则 `sum_(j=1)^m (prod_(k=1)^n x_(j k))^(1/n)` `le prod_(k=1)^n (sum_(j=1)^m x_(j k))^(1/n)`. `n = 2` 时, 即为 Cauchy 不等式.

令 `y_j = (prod_(k=1)^n x_(j k))^(1/n)`, `lambda_(j k) = x_(j k)//y_j`, 原不等式化为 `(sum_(j=1)^m y_j)^n le prod_(k=1)^n sum_(j=1)^m lambda_(j k) y_j`. 使用多项展开, 左边为 `sum_(|alpha|=n) n!/alpha! y^alpha`, 右边为 `sum_(|alpha|=n) k_alpha y^alpha`. 为了确定其中系数 `k_alpha`, 考虑乘积 `(sum_(j_1) lambda_(j_1 1) y_(j_1)) cdots (sum_(j_n) lambda_(j_n n) y_(j_n))` 中 `y_1^1 y_2^6 y_3^5` 项的系数. 这个系数形如 `sum lambda_(j_1 1) cdots lambda_(j_n n)`, 因为 `y_1` 的次数是 1, 所以下标 `j_1, cdots, j_n` 中, `y_1` 的下标 "1" 出现的次数是 1. 同理 "2" 出现的次数是 6, "3" 出现的次数是 5. 总之, `k_alpha = sum lambda_(j_1 1) cdots lambda_(j_n n)`, 其中下标 `j_1, cdots, j_n` 中, `1` 出现的次数为 `alpha_1`, ..., `m` 出现的次数为 `alpha_m`. 且求和的总项数为 `n!/alpha!`. 下证 `n!/alpha! le k_alpha`, 从而原不等式成立. 事实上, 记 `N = n!/alpha!`. 由均值不等式 `1/N sum lambda_(j_1 1) cdots lambda_(j_n n)` `ge (prod lambda_(j_1 1) cdots lambda_(j_n n))^(1/N)`. 上式右边所有系数 `lambda` 恰好各出现一次, 取 `N` 次方后, 等于 `prod_(j k) lambda_(j k)` `= prod_(j=1)^m prod_(k=1)^n x_(j k)/y_j` `= prod_(j=1)^m y_j^n/y_j^n = 1`. 证毕.

[群友 影织辅线] 假设每次抽奖会等概率地抽出字母 a 到 g 之中的一个. 连续抽取 9 次, 问抽出的 9 个字母中集齐 a 到 g 全部字母的概率?

考虑多项式 `(a+b+c+d+e+f+g)^9` 的展开式系数, 集齐全部 7 个字母的情况共两种:
1. 有 3 个相同字母, 形如 `a^3 bcdefg`. 此时系数为 `(7;1) (9!)/(3!)`.
2. 有两组相同字母, 每组两个, 形如 `a^2 b^2 cdefg`. 此时系数为 `(7;2) (9!)/(2! 2!)`.
将两个系数相加, 再除以所有可能的结果数, 得到最终答案 `2328480 // 7^9` `~~ 0.0577`.

排列与组合的算法