组合数学学习笔记

· · 个人记录

加法原理 & 乘法原理

当状态 S 可以由若干种不同方案 T 得到，那么：

CNT(S)=\sum_{T} CNT(T)

当一个方案 S 可以划分成若干个步骤 T 组成 S 时，那么：

CNT(S)=\prod_{T} CNT(T)

排列

对于一个集合 S，若给这个集合每个元素一个序号，构成序列的方案数就是这个集合的排列数。

除了把它看作 n 个子事件，还有一种类似于递推的思考方式：

设 |S| = n，假设前 n - 1 个数已经选好了，那么这个数就有 n 个插入位置，计 |S| = n 排列数为 s_n，则：

s_n =ns_{n-1}

而显然，s_1 = 1 ，所以：

s_n=n!

下降幂与上升

n^{\underline{m}}=\prod_{i=0}^{m-1} (n-i) = \frac {n!}{(n-m)!} n^{\overline{m}} = \prod_{i=0}^{m-1} (n+i) = \frac{(n+m-1)!}{(n-1)!}

普通排列组合

求在 n 个有标号的数里选出 m 个做排列，得到不同排列的个数。

设答案为 P_n^n，把组合过程拆分成 m 次选择，可得：

P_n^m= \prod_{i=0}^{m-1} (n-i)= \frac {n!}{(n-m)!}=n^{\underline{m}}

求在 n 个有标号的数里选出 m 个，得到不同组合的个数。

设答案为 \binom n m，考虑把 P_{n}^m 的意义看成两步：选数、排列，根据乘法原理有：

P_{n}^m = \binom{n}{m}\times {m!}

化一下式子则有：

\binom{n}{m}=\frac {P_{n}^m}{m!} = \frac {n!}{m!(n-m)!} =\frac {n^{\underline m}}{m!}

组合的递推式

\binom n m = \binom {n-1} m + \binom {n - 1} {m-1}

从组合意义来说，考虑第 n 项选不选，如果选则前 n - 1 个选了 m - 1 个，否则选了 m 个，根据加法原则加起来即可。

从归纳法的角度也可以证明，此处略去。

二项式定理

(x+y)^n = \sum_{i=0}^n \binom n i x^iy^{n-i}

从组合意义来说，每一项相当于是 n 个 x 里面选了 i 个 x，剩下的选了 y，其系数就是方案数，即为 \binom n i。

从归纳法的角度也很好证明：

(x+y)^{n+1} &= (x+y) ^ {n} (x+y) \\ &=(\sum_{i=0}^n \binom n i x^iy^{n-i})(x+y) \\ &=\sum_{i=0}^n \binom n {i} x^{i+1}y^{n-i} + \sum_{i=0}^n \binom n i x^iy^{n-i+1}\\ &= \sum_{i=0}^{n+1} \bigg[\binom {n} {i-1} + \binom n i \bigg] x^i\\ &= \sum_{i=0}^{n+1} \binom {n+1} i x^iy^{n+1-i}\\ \end{aligned}

不相邻的排列

从 1-n 里选 k 个不相邻的数字，求方案种数。

设方案种数为 f(n,k)，那么则易得组合意义上的递推式子：

f(x,y) = f(x - 2, y - 1) + f(x - 1, y)

我们发现每次选数对剩下可选数个数的贡献不一定，尝试枚举贡献为 2 的数的个数这个数就相当于连续段数，然后使用隔板法，在计算时需要考虑边缘，可得到：

\sum_{i=0}^k \bigg[ \binom {n - k - 2i+2}{k} + 2\binom {n - k - 2i + 1}{k-1} +\binom {n - k - 2i}{k-2}\bigg]

这个方法可以最后用下降幂差分的性质推出答案，但过于复杂。考虑把问题转化为：

把长 n 的线段化成 k 段，每段长度至少为 2，求划分种数

我们假设每个区间选的数就是这个区间的第二个数，可以发现是等价于之前的问题的，那么用隔板法可算出：

f(n,k)=\binom{n-k+1}{k}

错排数

求 1-n 的排列 p 使得：

\forall 1 \leq i \leq n, p_i \neq i

设答案为 f(x)，考虑 n 一定会跟前面的任意一个 i 交换，且交换时 p_i 一共有两种状态，枚举状态计算方案数即可。

$$f(x)=(x-1)[f(x-1)+f(x-2)]$$ 设 $f(x)$ 数列的生成函数为 $F(x)$，易得： $$\begin{aligned} F(x)&=x^2[xF(x) + F(x)]' + 1\\ \frac {F(x) - 1}{x^2} &= [xF(x) + F(x)]' \end{aligned}$$ 解得： $$\begin{aligned} F(x)&=\frac 1 {x-x^2-2x^3}\\ \\ \end{aligned}$$ **卡特兰数** 设卡特兰数列的第 $n$ 项为 $H(n)$，则有转移： $$H(n)=\sum_{i=1}^{n-1} H(i-1)H(n-i)$$ 特别的，$H(0) = H(1) = 0

上面的转移只能使用 O(n^2) 的暴力递推求得，但我们还有通项公式：

H(n) = \frac {\binom {2n} n} {n+1}=\binom {2n} {n} - \binom {2n}{n-1}

显然可以用归纳法证得，但是我们考虑使用 GF 正推：

设卡特兰数列的 OGF 为 G(x)，观察到转移是一个卷积的形式，列出转移式：

xH^2(x)+1&=H(x)\\ xH^2(x)-H(x)+1&=0\\ H(x) &= \frac {1-\sqrt{1-4x}} {2x} \end{aligned}

把根号用广义二项式定理展开：

H(x) &= \frac {1-\sqrt{1-4x}} {2x}\\ &= \frac {1-(1-4x)^{\frac 1 2}} {2x}\\ &= \frac {-\sum_{i\geq 1} {\binom {\frac 1 2} {i}(-4x)^i}} {2x} \\ &= \frac {-\sum_{i\geq 1} \frac {({\frac 1 2})^ { \underline i}}{i!}(-4x)^i} {2x} \\ \end{aligned}

把那部分拿出来化：

(\frac 1 2)^{\underline{n}}&=\prod_{i=0}^{n-1}\frac {1-2i}{2}\\ &=(-1)^{n-1}\frac {\prod_{i=1}^{n-1} {(2i-1)}}{2^n}\\ &=(-1)^{n-1}\frac {(2n-2)!}{2^{2n-1}(n-1)!}\\ \end{aligned}

代回原式，得：

H(x) &= \frac 1 {2x} \bigg[{\sum_{i\geq 1} \frac {(2i-2)!}{2^{2i-1}(i-1)!i!}(4x)^i}\bigg] \\ &= {\sum_{i\geq 1} \frac {(2i-2)!}{(i-1)!i!}x^{i-1}}\\ &= {\sum_{i\geq 1} \frac {(2i)!}{i!(i+1)!}x^{i}}\\ &= {\sum_{i\geq 1} \frac {1}{i+1}\frac {(2i)!}{(i!)^2}x^{i}}\\ &= {\sum_{i\geq 1} \frac {\binom {2i}{i}} {i+1} x^{i}}\\ \end{aligned}