范德蒙德卷积

引入

范德蒙德卷积是一种合并组合数的式子，主要应用于组合数学的公式推导。

范德蒙德卷积公式

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

证明

考虑用二项式定理证明：

\begin{aligned} \sum_{k = 0}^{n + m} (\binom{n + m}{k}) x^{k} & = (x + 1)^{n + m} \\ = (x + 1)^{n} (x + 1)^{m} \\ = \sum_{r = 0}^{n} (\binom{n}{r}) x^{r} \sum_{s = 0}^{m} (\binom{m}{s}) x^{s} \\ = \sum_{k = 0}^{n + m} \sum_{r = 0}^{k} (\binom{n}{r}) (\binom{m}{k - r}) x^{k} \end{aligned}

即有：

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

若考虑其组合意义证明：

在一个大小为 $n + m$ 的集合中取出 $k$ 个数，可以等于把大小为 $n + m$ 的集合拆成两个集合，大小分别为 $n$ 与 $m$ ，然后从 $n$ 中取出 $i$ 个数，从 $m$ 中取出 $k - i$ 个数的方案数。由于我们有了对于 $i$ 的枚举，于是只需要考虑一种拆法，因为不同的拆法之间是等价的。

推论

推论 1 及证明

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

证明与原公式证明相似。

推论 2 及证明

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

根据基础的组合数学知识推导，有：

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

推论 3 及证明

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

根据基础的组合数学知识推导，有：

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

推论 4 及证明

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

根据基础的组合数学知识推导，有：

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

其中 $(\binom{n + m}{m})$ 是我们较为熟悉的网格图路径计数的方案数。所以我们可以考虑其组合意义的证明。

在一张网格图中，从 $(0, 0)$ 走到 $(n, m)$ 共走 $n + m$ 步。规定 $(0, 0)$ 位于网格图左上角，其中向下走了 $n$ 步，向右走了 $m$ 步，方案数为 $(\binom{n + m}{m})$ 。

换个视角，我们将 $n + m$ 步拆成两部分走，先走 $n$ 步，再走 $m$ 步，那么 $n$ 步中若有 $i$ 步向右，则 $m$ 步中就有 $m - i$ 步向右，故得证。

习题

参考资料与注释

Vandermonde's Convolution Formula

本页面最近更新：2023/2/18 07:57:07，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Tiphereth-A, ChungZH, tidongCrazy
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用