Double Counting
如果数同一个东西有两种不同的数法，那么两种数法的表达式对应的结果必然相等。这样的组合证明方法叫做Double Counting。
\(\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}\)（杨辉三角的递推式）
等式左边表示从\(n\)个不同的元素里选\(k\)个。也可以这么讨论：讨论第\(n\)个元素有没有被选。如果被选了，那么对应的方案数等价于从前\(n-1\)个里选剩下的\(k-1\)个；如果没有被选，那么对应的方案数等价于从\(n-1\)个里面选\(k\)个。所以等式两边只是同一个问题的两种不同看法而已。
\(\left(\left(\begin{array}{l}n \\k\end{array}\right)\right)=\left(\left(\begin{array}{c}n \\ k-1\end{array}\right)\right)+\left(\left(\begin{array}{c}n-1 \\ k\end{array}\right)\right)\)
等式左边表示从\(n\)个不同的元素里可重复地选\(k\)个，选的结果是忽略顺序的。也可以这么讨论：讨论第\(n\)个元素有没有被选。如果被选了，那么它可以继承所有从\(n\)个里选\(k-1\)次的结果；如果没有被选，那么只能继承所有从\(n-1\)个元素里面选\(k\)次的方案了。
\(\sum_{j=0}^{k}\left(\begin{array}{c} m \\ j \end{array}\right)\left(\begin{array}{c} n \\ k-j \end{array}\right)=\left(\begin{array}{c} m+n \\ k \end{array}\right)\)（范德蒙德卷积）。
这个式子说明，从\(m+n\)个元素里选\(k\)个，可以分类讨论从前\(m\)个里选\(j\)个，从后\(n\)个里选\(k-j\)个。
标签：begin,right,end,组合,元素,证明,array,left From： https://www.cnblogs.com/qixingzhi/p/17157502.html