组合恒等式抽出因子

两条恒等式

吸收律（把因子 $k$ 吃进组合数）：

证明只需展开阶乘：$k\cdot\dfrac{n!}{k!(n-k)!}=\dfrac{n!}{(k-1)!(n-k)!}=n\cdot\dfrac{(n-1)!}{(k-1)!(n-k)!}$。 组合意义更好记：“从 $n$ 个里选 $k$ 个再指定其中一个当队长”， 两种数法——先选队伍再选队长（左），或先选队长再从剩下 $n-1$ 个里选 $k-1$ 个队员（右）。

范德蒙德恒等式（把两个组合数的卷积和坍成一个）：

组合意义：$a$ 男 $b$ 女里选 $m$ 人，按”选了几个男的”分类计数。

解题套路

1. 看见求和号里带一个 $k$（或 $k^2$、$k(k-1)$），先用吸收律把它吃掉。 $k(k-1)C_{n}^{k}=n(n-1)C_{n-2}^{k-2}$ 是它的二阶版本，处理 $k^2$ 时把 $k^2=k(k-1)+k$ 拆开再各用一次。
2. 常数提到外面，求和号里只剩两个组合数的乘积。
3. 对齐上下标：让两个组合数的上标之和是个定值、下标之和是个定值， 就能套范德蒙德。
4. 算出结果，再把提出去的常数乘回来。

用起来长什么样

袋中 $4$ 白 $5$ 黑，不放回取 $3$ 个，$W$ 为白球数，求 $E(W)$。

令 $i=k-1$，求和变成 $\sum_{i=0}^{2}C_{3}^{i}C_{5}^{2-i}=C_{8}^{2}=28$，于是

这正是课本推导超几何分布均值 $E(X)=n\frac{M}{N}$ 的那两步—— 把 $M$ 提出来、再用范德蒙德把 $\sum C_{M-1}^{k-1}C_{N-M}^{n-k}$ 换成 $C_{N-1}^{n-1}$。 一般式：

常见失手

1. 忘了改求和下界。 吸收律要求 $k\ge1$，$k=0$ 那一项本来就是 $0$， 可以放心丢掉——但换元后新的下界要跟着挪，别把 $\sum_{k=1}$ 写成 $\sum_{i=1}$。
2. 上下标各差一位。 $k\,C_{n}^{k}=n\,C_{n-1}^{k-1}$ 是上下标同时减一， 只减一个就全错。写完代 $n=4,k=2$ 验一次：$2\cdot 6=12=4\cdot 3$。
3. 范德蒙德对不齐就硬用。 两个组合数的上标之和必须是那个固定的 $m$； 换元之后先核一遍 $i+(2-i)=2$ 这类关系再套。
4. 绕远路。 只求期望时，能用平移或指示变量一行拿到的，就别做这套求和—— 这条套路的价值在于它能证明那个公式，以及在没有现成公式时兜底。