组合数学
容斥原理
(tot=sum_{i=1}^{n}(-1)^{i+1}*p(i))
排列
全排列公式：(f(n)=n!)
有重复元素的排列公式：(frac{(sum p(i))!}{prod_{i=1}^{n}p(i)!})
组合数
组合数通项公式：(C_n^k=frac{n!}{(n-k)!k!})
组合数递推公式：(C_n^k=C_{n-1}^k+C_{n-1}^{k-1})
组合数递推公式②：(C_n^{k+1}=C_{n}^{k}*frac{n-k}{k+1})
组合数恒等式：
(sum_{i=0}^n C_n^i = 2^n)
(C_n^m=C_n^{n-m})
(sum_{i=0}^{n} (-1)^i*C_n^i=0)
(sum_{i=0}^n C_n^i*[i\%2=1]=sum_{i=0}^n C_n^i * [i\%2=0] = 2^{n-1})
(sum_{i=0}^n (C_n^i)^2=C_{2n}^{n})
((x+y)^n = sum_{i=0}^n C_n^i*x^i*y^{n-i}) 即二项式定理
斐波那契数列
(f(n)=f(n-1)+f(n-2))
(f(n)=sum_{i=0}^{i<=n-i-1} C_{n-i-1}^{i}) 用2*n方格的多米诺骨牌覆盖问题可证
卡特兰数
(Cat_n=C_{2n}^{n}*frac{1}{n+1})
(Cat_n=C_{2n}^n-C_{2n}^{n-1})
(Cat_{n+1}=Cat_{n}*frac{2(2n+1)}{n+2})