范德蒙德卷积

形似:

[sum_{i=0}^kinom niinom m{k-i}=inom {n+m}k ]

可以理解为在大小为 (n)(m) 的两个堆中选择 (k) 个物品。

好像是)推论:

[sum_{i=1}^ninom niinom {n}{i-1}=inom {2n}{n-1} ]

证明:

(k=n-1) ,则由第一个式子可得:

[sum_{i=0}^{n-1}inom niinom n{n-1-i}=inom {2n}{n-1}\ sum_{i=0}^{n-1}inom niinom n{n-1-i}=sum_{i=0}^{n-1}inom niinom n{i+1}=sum_{i=1}^{n}inom niinom n{i-1}\ Rightarrowsum_{i=1}^ninom niinom {n}{i-1}=inom {2n}{n-1} ]

其他的推论:

[sum_{i=0}^ninom ni^2=sum_{i=0}^ninom niinom n{n-i}=inom {2n}n\sum_{i=0}^minom niinom mi=sum_{i=0}^minom niinom m{m-i}=inom {n+m}m ]

原文地址:https://www.cnblogs.com/jasony/p/13955298.html