组合恒等式的推导证明一般可以考虑等号两边的组合意义、杨辉三角、二项式定理或者直接硬上组合定义式。
(mn)=(mn−1)+(m−1n−1)
考虑最后一个元素有没有选。
i=0∑n(in)=2n
枚举在 n 个元素的集合中选多少个元素,再枚举选出的是那些元素,等于枚举每个元素有没有选。
i=0∑n(−1)i(in)=0
二项式定理:
(−1+1)n=i=0∑n(−1)i1i(in)=i=0∑n(−1)i(in)=0
i=n∑m(ni)=(n+1m+1)
考虑杨辉三角:
i=0∑m(in+i)=(n+mm+1)
依旧是考虑杨辉三角:
(mn)=mn−m+1(m−1n)
(mn)=k(m−1n)
k=(m−1n)(mn)=(m−1)!(n−m+1)!n!m!(n−m)!n!=m!(n−m)!(m−1)!(n−m+1)!=mn−m+1
i=0∑k(in)(k−im)=(kn+m)
著名的范德蒙德卷积,组合意义是从两个没有重复元素的集合中选择 k 个元素可以通过枚举每个集合中选了几个来计算。
xy=(2x+y)−(2x)−(2y)
从 x 个各不相同的小球中选出一个,再从 y 个各不相同的小球中选出一个的方案数,等于从这 x+y 个小球中选出 2 个的方案数减去两个球都是从某一边选出的方案数。
i=k∑n2n−i(m+km+i)=i=m+k+1∑m+n+1(im+n+1)