若集合 (或多重集) `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)`.
o 放进 6 个不同的盒子,
只需在它们之间插入 5 个隔板:
o|oo|ooo|o|o|oo
需要注意, 和物体一样, 这里的隔板是不可区分的对象.
由于每个盒子不空, 问题转化为在 `m-1` 个空隙中插入 `n-1`
个隔板的方法数, 于是
`|S_2| = (m-1;n-1)`.
`|S_2|` 还是:
o 放进 6 个不同的盒子的一种方法是:
o||oo|||ooooooo
问题转化为将 `n-1` 个隔板与 `m` 件物体排成一行的组合数.
注意隔板与物体都不可区分, 这相当于在
`m+n-1` 个位置上选出 `m` 个物体, 即
`|F_2| = (m+n-1;m)`.
`|F_2|` 还是:
我们推导组合数的一些简单性质. 下面所推导的恒等式, 有些没有给出参数 `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
如, 为了将括号中的数字相加, 将右上角的 1 换成方括号中的 1,
就可以反复应用 Pascal 恒等式: 1 + 2 = 3, 3 + 3 = 6 ...,
最后得到所求的和 15. 为此得到启发,
反复用 Pascal 恒等式:
右边 `= (n+1;n+1) + sum_(i=1)^m (n+i;n)`
`= (n+2;n+1) + sum_(i=2)^m (n+i;n)`
`= cdots =` 左边.
设 `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`.
[来自 卡尔・夏洛克] 证明 `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`.
多重指标 是一个整数向量 `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`. 证毕.