范德蒙德卷积

引入

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

范德蒙德卷积公式

证明

考虑用二项式定理证明:

即有:

若考虑其组合意义证明:

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

推论

推论 1 及证明

证明与原公式证明相似。

推论 2 及证明

根据基础的组合数学知识推导,有:

推论 3 及证明

根据基础的组合数学知识推导,有:

推论 4 及证明

根据基础的组合数学知识推导,有:

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

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

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

习题

参考资料与注释

  1. Vandermonde's Convolution Formula