00:00:00

Garbage fish2026-09-22数论

范德蒙德卷积相关化简方法笔记

谁能想到这是个五级算法，因为数学选必三上有，【5】代数（高中部分）。

范德蒙德卷积的变化通常由 换元法 和 组合数的对称性 操作，详细见下。

定理

\sum_{i = 0}^{k} (\binom{n}{i}) (\binom{m}{k - i}) = (\binom{n + m}{k})

先在 $n$ 个里面选 $i$ 个，再在另外 $m$ 个里面取 $(k - i)$ 个，由于 $i \in [0, k]$ ，所以是任取，因此组合意义等价于在 $(n + m)$ 个中选 $k$ 个。

推论 1

\sum_{i = l}^{r} (\binom{n}{i - l}) (\binom{m}{r - i}) = (\binom{n + m}{r - l})

利用 换元法，设 $i - l = t$ ，变为 $\sum_{t = 0}^{r - l}$ 容易证明。

推论 2

\sum_{i = 1}^{n} (\binom{n}{i}) (\binom{n}{i - 1}) = (\binom{2 n}{n - 1})

这里首先利用换元法变成

\sum_{i = 0}^{n - 1} (\binom{n}{i + 1}) (\binom{n}{i})

但是两个 $i$ 不好消去，考虑用 组合数的对称性 即可消去，由于 $(\binom{n}{i + 1})$ 表示不能在这一部任意选（ $i + 1$ 取不到 $0$ ），所以考虑对其进行操作。

\sum_{i = 0}^{n - 1} (\binom{n}{n - (i + 1)}) (\binom{n}{i}) = (\binom{2 n}{n - 1})

20260929A 翻转2026-09-29 16:30:00
期望转换笔记2026-09-27 15:10:00
20260923B 灯带笔记2026-09-23 15:55:00
更多文章 >