组合数公式
递推式
[Cn,m)=Cn-1,m-1)+Cn-1,m)
]
组合数完全累和
[sum_{i=0}^n Cn,i) =2^n
]
奇偶累和
[sum_0^n -1)^i Cn,i)=[n=0]
]
$sumcdotssum ightarrow C) $型
我们熟知的有
[sum_{i=1}^{n}1=n = Cn,1)
]
[sum _{i=1}^{n} sum_{j=i+1}^{n} 1= frac{nn-1)}{2}
]
更一般的
[underbrace {sum sum … sum} 1 =Cn,k)
]
[k个sum)
]
$ … cdot Cn,i)$型
$ sum i cdot Cn,i) $
$ = sum {i cdot frac{n!}{i! cdot n-i)!}}$
$ = sum { frac{n!}{i-1)! cdot n-i)!}}$
=sum {n cdot frac {n-1)!} {i-1)! cdot n-i)!}})
=ncdot sum Cn-1,i-1))
同理的
[sum icdot i-1)cdot Cn,i)=n cdot n-1) cdot sum Cn-2,i-2)
]
带入还能得到
[sum i^2 cdot Cn,i) = n cdot n-1) cdot sum Cn-2,i-2)+n cdot sum Cn-1,i-1)
]
更一般的，可以表示成
[sum Ci,k) cdot Cn,i) =Cn,k) cdot sum Cn-k,i-k)
]
多组合数相乘型
sum_{i=0}^{k} Cn,i)cdot Cm,k-i) = Cn+m,k))
其实就是两个组合问题的组合，可以直接通过实际意义得到
Lucas定理
$ Cn,m) mod p = Cn mod p,m mod p) cdot Clfloorfrac{n} {p}floor, lfloor frac{m} {p}floor) mod p$
预处理阶乘逆元后，可以用于解决模数较小而n,m)较大的组合数问题
组合数前缀和
令 Sn,m)=sum_{i=0}^{m} Cn,i))
Sn,m)+Sn,m+1))
=sum_{i=0}^{m}Cn,i)+Cn,i+1))+Cn,0))
=sum Cn+1,i+1)+Cn,0)) 带入递推公式)
=Sn+1,m+1))
又ecause Sn,m)+Sn,m+1)=2Sn,m+1)-Cn,m+1))
herefore Sn,m)=2Sn-1,m)-Cn-1,m))
待补。。。)