排列组合

· · 个人记录

pre

排列 A

P^m_n=A^m_n=n(n-1)(n-2)...(n-m+1)=\frac{n!}{(n-m)!}

组合 C

C^m_n=\frac{A_n^m}{A_m^m}=\frac{n!}{m!(n-m)!}

二项式定理

(x+y)^n=\begin{pmatrix}n\\0\\\end{pmatrix}x^ny^0+\begin{pmatrix}n\\1\\\end{pmatrix}x^{n-1}y^1+\begin{pmatrix}n\\2\\\end{pmatrix}x^{n-2}y^2+...+\begin{pmatrix}n\\n-1\\\end{pmatrix}x^1y^{n-1}+\begin{pmatrix}n\\n\\\end{pmatrix}x^0y^{n}

错排列

D(n)=n!(\frac{(-1)^2}{2!}+\frac{(-1)^3}{3!}+...\frac{(-1)^n}{n!})=n!\sum^n_{k=2}\frac{(-1)^k}{k!}

二项式反演

正向：

f(n) = \sum_{k=n}^{m} \binom{k}{n} g(k)

反向：

g(n) = \sum_{k=n}^{m} (-1)^{k-n} \binom{k}{n} f(k)

第一类斯特林树