范德蒙德卷积学习
定义
范德蒙德卷积的基本公式是:
用于计算组合数的和
组合数的关键点,感觉就是对称性,二项式逆过程,然后令x为特殊值
组合数基本概念
对称性
二项式定理
其中,当x=1时,式子为标准二项式公式,证明时会用到这个式子的逆过程
基本公式的证明
考虑倒着证明,即证明右边等于左边
第一步转移的依据就是二项式定理的逆过程,这里带上了k,方便逆过程的理解(实际上x=1)
接下来的关键点就是改变求和方式了,改为枚举$x^k$,变为求这一项的系数
因为x的次数需要是k,而每一项都是前面和后面乘积乘出来的,所以当前面选择的次数是r时,这一项是:
而r是一个变化的范围,从0-k,所以$x^k$的系数就是这么一系列的求和
所以:
注意里面的系数,$x^k$的系数相同,所以:
直观理解
要从N个物品中选出k个,相当于分成两部分,每部分各自选择再合起来,两者的方案数一样
推论
推论的证明非常简单,别用上面那个啥笔证明方法,直接换元凑上面的形式就行,总结下来就是:只要下面两个的和是一个常数,直接上下分别求和就行(不然你以为证明上面那个的作用是什么)
推论1
推论2
这里把其中一个组合数对称一下,就能使用前面的公式了
推论3
依旧使用到对称性
推论4
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 ZestfulYK的Blog!