定义

范德蒙德卷积的基本公式是:

用于计算组合数的和

组合数的关键点,感觉就是对称性,二项式逆过程,然后令x为特殊值

组合数基本概念

对称性

二项式定理

其中,当x=1时,式子为标准二项式公式,证明时会用到这个式子的逆过程

基本公式的证明

考虑倒着证明,即证明右边等于左边

第一步转移的依据就是二项式定理的逆过程,这里带上了k,方便逆过程的理解(实际上x=1)

接下来的关键点就是改变求和方式了,改为枚举$x^k$,变为求这一项的系数

因为x的次数需要是k,而每一项都是前面和后面乘积乘出来的,所以当前面选择的次数是r时,这一项是:

而r是一个变化的范围,从0-k,所以$x^k$的系数就是这么一系列的求和

所以:

注意里面的系数,$x^k$的系数相同,所以:

直观理解

要从N个物品中选出k个,相当于分成两部分,每部分各自选择再合起来,两者的方案数一样

推论

推论的证明非常简单,别用上面那个啥笔证明方法,直接换元凑上面的形式就行,总结下来就是:只要下面两个的和是一个常数,直接上下分别求和就行(不然你以为证明上面那个的作用是什么)

推论1

推论2

这里把其中一个组合数对称一下,就能使用前面的公式了

推论3

依旧使用到对称性

推论4