组合数学

排列

$A^m_n=n(n-1)(n-2)\cdots(n-m+1)=\frac{m!}{(n-m)!}\\ C_n^m=\frac{A^m_n}{m!}=\frac{n(n-1)(n-2)\cdots(n-m+1)}{m(m-1)(m-2)\cdots3\times2\times1}\\ A^m_{n+1}=A^m_n+mA_n^{m-1},A^m_n=(n-m+1)A^{m-1}_n, A^m_n=\frac{n}{n-m}A^m_{n-1}\\$

组合

$C_n^m=C_n^{n-m}\\ C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\\ \sum_{i=0}^nC_n^i=2^n\\\text{Vandermonde} 恒等式\\ C^k_{m+n}=\sum_{i=0}^kC_m^iC_n^{k-i} \\C_{2n}^n=\sum_{i=0}^k(C_n^i)^2\\ H_n^m=C_{m+n-1}^m=\sum_{i=1}^mC_{m-1}^{m-i}C_n^i\\(x+y)^n=\sum_{i=0}^nC_n^ix^{n-i}y^{i}\\ (1+x)^n=\sum_{i=0}^nC_n^ix^{i}\\D_{n}=n !\left(\frac{1}{2 !}+\ldots+(-1)^{n} \frac{1}{n !}\right)$

赋值法

$(ax^p+bx^q)^n=a_0+a_1x+a_2x^2+\cdots+a_nx^n=f(x)$ $\sum_{i=0}^na_i=f(1)\\ a_0=f(0)$

多项式定理

$C_{n}^{n_{1}} C_{n-n_{1}}^{n_{2}} \ldots C_{n-n_{1}-\ldots-n_{k-1}}^{n_{k}}=\frac{n !}{n_{1} ! n_{2} ! \ldots n_{k} !}$ $\left(x_{1}+\ldots+x_{k}\right)^{n}=\sum_{n_{1}+\ldots+n_{k}=n}\left(\begin{array}{ccc} & n & \\ n_{1} & \ldots & n_{k} \end{array}\right) x_{1}^{n_{1}} x_{2}^{n_{2}} \ldots x_{k}^{n_{k}}$

n次方差

$x^{n}-1=(x-1)\left(x^{n-1}+x^{n-2}+\cdots+x+1\right)$ $\begin{aligned} a^{n}-b^{n} &=b^{n}\left(\left(\frac{a}{b}\right)^{n}-1\right) \\ &=b^{n}\left(\frac{a}{b}-1\right)\left(\left(\frac{a}{b}\right)^{n-1}+\left(\frac{a}{b}\right)^{n-2}+\cdots+\frac{a}{b}+1\right) \\ &=(a-b)\left(a^{n-1}+a^{n-2} b+\cdots+a b^{n-2}+b^{n-1}\right) \end{aligned}$