组合数学 – 期中复习

二项式定理推论

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

$$\sum_{k\ge 0}\binom{n}{k}kx^{k}=nx(1+x)^{n-1}$$

$$\sum_{k\ge 0}\binom{n}{k}\frac{x^k}{k}=\int_0^x\frac{(1+x)^n}{x}~\mathbf{d}x$$

Vandermonde 恒等式

$$\sum_{0\le i\le l}\binom{n}{i}\binom{m}{l-i}=\binom{n+m}{l}$$

$$k=n\text{时，}\binom{2n}{n}=\sum_{0\le i\le n}\binom{n}{i}^2$$

杨辉三角

$$\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$$

朱世杰恒等式

$$\sum_{0\le l\le n}\binom{l}{k}=\binom{n+1}{k+1}$$

应用

$$\begin{aligned}\sum_{0\le m\le n}m^2&=\sum\binom{m}{1}+2\sum\binom{m}{2}\\ &=\binom{n+1}{2}+2\binom{n+2}{3}\end{aligned}$$

$$\begin{aligned}\sum_{0\le m\le n}m^3&=6\sum\binom{m}{3}+3\sum m^2-2\sum m\\ &=6\binom{n+1}{4}+6\binom{n+1}{3}+\binom{n+1}{2}\end{aligned}$$

广义组合数

$$\binom{p+q+r}{p,q,r}:=\frac{(p+q+r)!}{p!\cdot q!\cdot r!}$$

$$(a_1+a_2+\cdots+a_m)^n=\sum_{\begin{gathered}i_1+i_2+\cdots+i_m=n\\i_1,i_2,\cdots,i_m\ge0\end{gathered}}a_1^{i_1}a_2^{i_2}\cdots a_m^{i_m}\frac{n!}{i_1!i_2!\cdots i_m!}$$

斯特林公式

$$n!\sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$$

思路

$$\int_k^{k+1}\ln{x}~\mathbf{d}x-\ln{k}=(k+1)\ln\left(1+\frac{1}{k}\right)-1\sim\frac{1}{2k}+O(\frac{1}{k^2})$$

$$\begin{aligned}\sum\left(\int_k^{k+1}\ln{x}~\mathbf{d}x-\ln{k}\right)&=(n+1)\ln(n+1)-(n+1)-\ln(n!)\\&\sim\sum\left(\frac{1}{2k}+O\left(\frac{1}{k^2}\right)\right)=\frac{1}{2}\ln{n}+O\left(1\right)\end{aligned}$$

$$\Rightarrow \ln{n!}=\left(n+\frac{1}{2}\right)\ln{n}-n+O(1)$$

集系

递推

$$h(n)=a_nh(n-1)+\cdots$$

$$\Rightarrow\frac{h(n)}{\prod_{i=1}^na_i}=\frac{h(n-1)}{\prod_{i=1}^{n-1}a_i}+\frac{\cdots}{\prod_{i=1}^na_i}$$

Catalan Number

模型：进栈出栈问题、二叉树括号匹配

$$C_0=1\quad C_1=1\quad C_2=2\quad C_3=5\quad C_4=14$$

$$C_n=\sum_{k=1}^nC_{k-1}C_{n-k}$$

根据生成函数求通项

$$C(x)=1+xC(x)^2$$

$$C_n=\frac{1}{n+1}\binom{2n}{n}$$

根据格点图求通项

$$\begin{aligned}C_n&=|\{在主对角线之上的道路\}|\\&=\binom{2n}{n}-|\{所有经过次对角线的道路\}|\\&=\binom{2n}{n}-|\{出发点关于次对角线的对称点出发的道路\}|\\&=\binom{2n}{n}-\binom{2n}{n+1}=\frac{1}{n+1}\binom{2n}{n}\end{aligned}$$

随机游走

容斥原理

错排

错排概率趋于$\frac{1}{e}$

送对信封期望$E(X)=1$

Stirling Number

1st kind

n个数的置换中恰有m个圈的个数

$$S_1(n,m)\quad or\quad {n\brack m}$$

$$S_1(n,m)=S_1(n-1,m-1)+(n-1)S_1(n-1,m)$$

$$x^{\overline{n}}=\sum_{m=0}^nS_1(n,m)x^m$$

$$x^{\underline{n}}=\sum_{m=0}^n(-1)^{n+m}S_1(n,m)x^m$$

2nd kind

n个不同球放到m个相同盒，满足所有盒子不空的方法数

$$S_2(n,m)\quad or\quad {n\brace m}$$

$$S_2(n,m)=S_2(n-1,m-1)+mS_2(n-1,m)$$

$$x^n=\sum_{m=0}^nS_2(n,m)x^{\underline{m}}$$

$$x^n=\sum_{m=0}^n(-1)^{n+m}S_2(n,m)x^{\overline{m}}$$

球盒问题

n个球，m个盒