跳转至

# 范德蒙德卷积

## 引入

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

## 范德蒙德卷积公式

𝑘∑𝑖=0(𝑛 𝑖)(𝑚 𝑘−𝑖)=(𝑛+𝑚 𝑘)∑i=0 k(n i)(m k−i)=(n+m k)

### 证明

考虑用二项式定理证明：

𝑛+𝑚∑𝑘=0(𝑛+𝑚 𝑘)𝑥 𝑘=(𝑥+1)𝑛+𝑚=(𝑥+1)𝑛(𝑥+1)𝑚=𝑛∑𝑟=0(𝑛 𝑟)𝑥 𝑟 𝑚∑𝑠=0(𝑚 𝑠)𝑥 𝑠=𝑛+𝑚∑𝑘=0 𝑘∑𝑟=0(𝑛 𝑟)(𝑚 𝑘−𝑟)𝑥 𝑘∑k=0 n+m(n+m k)x k=(x+1)n+m=(x+1)n(x+1)m=∑r=0 n(n r)x r∑s=0 m(m s)x s=∑k=0 n+m∑r=0 k(n r)(m k−r)x k

即有：

(𝑛+𝑚 𝑘)=𝑘∑𝑟=0(𝑛 𝑟)(𝑚 𝑘−𝑟)(n+m k)=∑r=0 k(n r)(m k−r)

若考虑其组合意义证明：

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

## 推论

### 推论 1 及证明

𝑠∑𝑖=−𝑟(𝑛 𝑟+𝑖)(𝑚 𝑠−𝑖)=(𝑛+𝑚 𝑟+𝑠)∑i=−r s(n r+i)(m s−i)=(n+m r+s)

证明与原公式证明相似．

### 推论 2 及证明

𝑛∑𝑖=1(𝑛 𝑖)(𝑛 𝑖−1)=(2 𝑛 𝑛−1)∑i=1 n(n i)(n i−1)=(2 n n−1)

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

𝑛∑𝑖=1(𝑛 𝑖)(𝑛 𝑖−1)=𝑛−1∑𝑖=0(𝑛 𝑖+1)(𝑛 𝑖)=𝑛−1∑𝑖=0(𝑛 𝑛−1−𝑖)(𝑛 𝑖)=(2 𝑛 𝑛−1)∑i=1 n(n i)(n i−1)=∑i=0 n−1(n i+1)(n i)=∑i=0 n−1(n n−1−i)(n i)=(2 n n−1)

### 推论 3 及证明

𝑛∑𝑖=0(𝑛 𝑖)2=(2 𝑛 𝑛)∑i=0 n(n i)2=(2 n n)

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

𝑛∑𝑖=0(𝑛 𝑖)2=𝑛∑𝑖=0(𝑛 𝑖)(𝑛 𝑛−𝑖)=(2 𝑛 𝑛)∑i=0 n(n i)2=∑i=0 n(n i)(n n−i)=(2 n n)

### 推论 4 及证明

𝑚∑𝑖=0(𝑛 𝑖)(𝑚 𝑖)=(𝑛+𝑚 𝑚)∑i=0 m(n i)(m i)=(n+m m)

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

𝑚∑𝑖=0(𝑛 𝑖)(𝑚 𝑖)=𝑚∑𝑖=0(𝑛 𝑖)(𝑚 𝑚−𝑖)=(𝑛+𝑚 𝑚)∑i=0 m(n i)(m i)=∑i=0 m(n i)(m m−i)=(n+m m)

其中 (𝑛+𝑚 𝑚)(n+m m) 是我们较为熟悉的网格图路径计数的方案数．所以我们可以考虑其组合意义的证明．

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

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

## 习题

- CF785D Anton and School - 2

- 洛谷 P2791 幼儿园篮球题

## 参考资料与注释

1. Vandermonde's Convolution Formula

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