排列组合

$$A(n,r) = \frac {n!}{(n-r)!}$$

$$C(n,r) = \frac {n!}{(n-r)!r!}$$

$$C(n,r) = C(n,n-r)$$

$$C(n,k) = C(n-1,k)+C(n-1,k-1)$$

$$C(n+r+1,r) = \sum_{i=0}^{r} C(n+r-i,r-i)$$

$$C(n,k)C(k,r) = C(n,r)C(n-r,k-r) \quad (k \ge r)$$

特殊排列组合

可重复n选r组合数：$C(n+r-1,r)$

圆周n选r排列数：$Q(n,r)=A(n,r)/r$

排列Hash函数

对于排列$a_1,a_2,a_3....a_n$，设

$$b_i=\sum_{k=i+1}^n [a_i>a_k]$$

则

$$Hash=\sum_{i=1}^n b_i*(n-i)!$$

要恢复也很简单

整数拆分

整数$n$拆分成一些重复次数不超过$k$的整数的拆分数，等于整数$n$拆分成不被$k+1$除尽的整数的拆分数（允许重复）

整数$n$拆分成$k$个数的拆分数，等于整数$n$拆分成最大数为$k$的拆分数

整数$n$拆分成不超过$k$个数的拆分数，等于整数$n$拆分成最大数不超过$k$的拆分数

整数$n$拆分成互不相同的若干奇数的拆分数，等于整数$n$拆分成自共轭的Ferrers图像的拆分数

整数$n$拆分成不超过$k$个数的拆分数，等于整数$n+k$拆分成恰好$k$个数的拆分数

Stirling数

①（n个元素分作k个环排列的方案树）

$$s(n,0)=0$$

$$s(1,1)=1$$

$$s(n+1,k)=s(n,k-1)+ns(n,k)$$

②（n个元素分作k个非空集合的方案树）

$$S(n,k)=0 ~ (n<k ~or~ k=0)$$

$$S(n,n)=S(n,1)=1$$

$$S(n,k)=S(n-1,k-1)+kS(n-1,k)$$

③（可以用此式进行FFT）

$$\begin{align} S(n,k)&=\frac{1}{k!}\sum_{j=1}^{k}(-1)^{k-j}C(k,j)j^n \\ &=\sum_{j=1}^{k}\frac{(-1)^{k-j}}{(k-j)!}\frac{j^n}{j!} \end{align}$$

Catalan数

$$h(0)=1,h(1)=1,h(n)=h(0)h(n-1)+h(1)h(n-2)+...+h(n-1)h(0) ~ (n>1)$$

$$h(n)=h(n-1)\frac {4n-2}{n+1}$$

$$h(n)=\frac {C(2n,n)}{n+1}$$

错排公式

$$D_n=n!(\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+\frac{(-1)^n}{n!})=(n-1)(D_{n-1}+D_{n-2})$$

组合公式

$$\sum_{k=1}^n (2k-1)^2=\frac {n(4n^2-1)}{3}$$

$$\sum_{k=1}^n (2k-1)^3=n^2(2n^2-1)$$

$$\sum_{k=1}^n k=\frac {n(n+1)}{2}$$

$$\sum_{k=1}^n k^2=\frac {n(n+1)(2n+1)}{6}$$

$$\sum_{k=1}^n k^3=(\frac {n(n+1)}{2})^2$$

$$\sum_{k=1}^n k^4=\frac {n(n+1)(2n+1)(3n^2+3n-1)}{30}$$

$$\sum_{k=1}^n k^5=\frac {n^2(n+1)^2(2n^2+2n-1)}{12}$$

$$\sum_{k=1}^n k(k+1)=\frac {n(n+1)(n+2)}{3}$$

$$\sum_{k=1}^n k(k+1)(k+2)=\frac {n(n+1)(n+2)(n+3)}{4}$$

$$\sum_{k=1}^n k(k+1)(k+2)(k+3)=\frac {n(n+1)(n+2)(n+3)(n+4)}{5}$$

$$\sum_{k=1}^n \prod_{i=0}^{g-1} (k+i)=\frac {\prod_{i=0}^{g}(n+i)}{g+1}$$

Burnside引理

设$G$是一个有限群，作用在集合$X$上。对每个$g$属于$G$令$X^g$表示$X$中在$g$作用下的不动元素。

伯恩赛德引理断言轨道数（记作$|X/G|$）由如下公式给出：

$$|X/G| = \frac{1}{|G|}\sum_{g \in G}|X^g|$$

说人话，就是有m个置换k种颜色，所有本质不同的染色方案数就是每种置换下的不变染色方案数的平均数。

Lucas定理

$$C(n,m) \equiv C(n/p,m/p)C(n\%p,m\%p) \pmod p$$

默慈金数

$n$ 个数，可以为 $+1,0,-1$，保证 $\sum_i^a k_i(1\le a \le n)$ 非负且所有数总和为0的方案数

$$M_{n+1}=M_n+ \sum_{i=0}^{n-1}M_i M_{n-1-i} = \frac{(2n+3)M_n+3nM_{n-1}}{n+3}$$