范德蒙德卷积

引入

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

范德蒙德卷积公式

证明

考虑用二项式定理证明：

即有：

若考虑其组合意义证明：

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

推论

推论 1 及证明

证明与原公式证明相似。

推论 2 及证明

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

推论 3 及证明

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

推论 4 及证明

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

其中 是我们较为熟悉的网格图路径计数的方案数。所以我们可以考虑其组合意义的证明。

在一张网格图中，从 走到 共走 步。规定 位于网格图左上角，其中向下走了 步，向右走了 步，方案数为 。

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

习题

• CF785D Anton and School - 2

• 洛谷 P2791 幼儿园篮球题

参考资料与注释

1. Vandermonde's Convolution Formula