排列组合学习总结

· · 算法·理论

第二类斯特林数

定义

### 递推公式 $\begin{Bmatrix}n\\k\end{Bmatrix} =\begin{cases}[n==0] & k=0 \\ 0 & n=0\\ \begin{Bmatrix}n-1\\k-1\end{Bmatrix} + k \times\begin{Bmatrix}n-1\\k\end{Bmatrix}& \text{otherwise} \end{cases}

递推公式证明

### 数学公式 $\begin{Bmatrix}n\\k\end{Bmatrix} = \dfrac{1}{k!}\times \sum\limits_{i=0}^{k} \ (-1)^{i}\times C_{k}^i\times (k-i)^{n}

数学公式证明

容斥原理证明：我们可以先考虑集合互相区分的情况，然后 \times \dfrac{1}{k!} 就是第二类斯特林数，我们可以用所有的方案减去不合法的方案，显然，所有方案数为 k^n，然后减去至少有一个集合为空的情况，就是 C_{k}^1\times (k-1)^n，此时多减去了至少有 2 个集合为空的情况，再加上 C_{k}^2\times (k-2)^n，又多加了至少有 3 个集合为空的情况，减去 C_{k}^3\times (k-3)^n，以此类推。

卡特兰数

定义

### 递推公式 $H_{n}=\begin{cases} 1 & n=0,1 \\\sum\limits_{i=1}^{n} H_{i-1}\times H_{n-i} & \text{otherwise}\\ \end{cases}

递推公式证明

枚举第一个走到的 (i,i)，因为从 (0,0) 出发只能往右走走到 (1,0)，(i,i) 只能从 (i,i-1) 走过来，所以从 (0,0) 走到 (i,i) 经过的点 (x,y) 满足 x>y （(i,i) 是第一次走到的，前面不能有 x=y）相当于从 (1,0) 走到 (i,i-1) 满足 x \ge y+1，其实就是 H_{i-1}，从 (i,i) 走到 (n,n) 就是 H_{n-i} 根据乘法原理可得就是 H_{i-1}\times H_{n-i}，然后根据加法原理把所有的加起来就是 \sum\limits_{i=1}^{n} H_{i-1}\times H_{n-i}，可以看图好好理解一下。

其他公式

H_{n}=C_{2n}^n-C_{2n}^{n-1}=\dfrac{C_{2n}^n}{n+1}=\dfrac{(4n-2)H_{n-1}}{n+1}

其他公式证明

先证 H_{n}=C_{2n}^n-C_{2n}^{n-1}，从 (0,0) 到 (n,n) 其实就是从 2n 条边中选出 n 条向上的，就是 C_{2n}^n，要扣掉不合法的情况，如图，将所有不合法的路径与 y=x+1 的交点之前的路径全部沿 y=x+1 翻折，所有不合法的情况就相当于从 (-1,1) 到 (n,n) 的所有路径数，就是从 2n 条边中选出 n-1 条向上的边，就是 C_{2n}^{n-1}。

然后证 C_{2n}^n-C_{2n}^{n-1}=\dfrac{C_{2n}^n}{n+1}，这个直接展开证明即可。

\begin{aligned} C_{2n}^n-C_{2n}^{n-1} &= \dfrac{(2n)!}{(n!)^2}-\dfrac{(2n)!}{(n-1)!(n+1)!} \\ &=\dfrac{(n+1)(2n)!-n(2n!)}{n!(n+1)!} \\&= \dfrac{(2n)!}{n!(n+1)!} \\&= \dfrac{(2n)!}{n!n!(n+1)} \\&= \dfrac{C_{2n}^{n}}{n+1}\end{aligned}

最后证明 H_{n}=\dfrac{(4n-2)H_{n-1}}{n+1}

由上得 H_{n}=\dfrac{C_{2n}^n}{n+1},H_{n-1}=\dfrac{C_{2n-2}^{n-1}}{n}，所以：

\begin{aligned} \dfrac{(4n-2)H_{n-1}}{n+1}&=\dfrac{(4n-2)\frac{C_{2n-2}^{n-1}}{n}}{n+1} \\&= \dfrac{\frac{(4n-2)(2n-2)!}{n(n-1)!(n-1)!}}{n+1}\\&=\dfrac{\frac{n(4n-2)(2n-2)!}{n!n!}}{n+1}\\&=\dfrac{\frac{2n(2n-1)(2n-2)!}{n!n!}}{n+1}\\&=\dfrac{\frac{(2n)!}{n!n!}}{n+1}\\&=\dfrac{C_{2n}^n}{n+1}\\&=H_{n}\end{aligned}

排列组合基本公式

经典问题：把 n 个球放入 k 个盒子，共有多少种情况？（严谨表述：将 n 个元素划分为 k 个集合共有多少种情况？）

序号 球是否标号(有标号就是区分球)（选取元素有序还是无序） 盒子是否有标号(有标号就是区分盒子)（集合是否互相区分） 盒子是否允许空（是否允许存在空集） 公式/递推式 证明
1 否 否 否 B1(n,k) 见下证明 1
2 否 否 是 B2(n,k) 见下证明 2
3 否 是 否 C_{n-1}^{k-1} 见下证明 3
4 否 是 是 C_{n+k-1}^{k-1} 见下证明 4
5 是 否 否 \begin{Bmatrix}n\\k\end{Bmatrix} 由第二类斯特林数定义得
6 是 否 是 {\textstyle \sum\limits_{i=0}^{k-1}}\begin{Bmatrix}n\\k- i\end{Bmatrix} 见下证明 6
7 是 是 否 \begin{Bmatrix}n\\k\end{Bmatrix}\times k! 见上第二类斯特林的数学公式证明
8 是 是 是 k^n 显然，证明略

注：

0 & n<k \\ B2(n-k,k) & n\ge k \end{cases} 1 & n=0 \\ 0 & k=0 \\ B2(n,n) & k>n \\ B2(n-k,k)+B2(n,k-1) & \text{otherwise} \end{cases}

证明 1

当 n < k 时，显然一定会有盒子是空的，就不满足要求了，所以方案数为 0 。

当 n \ge k 时，我们可以让每个盒子先都放 1 个球，这样就转换为公式 2 了，计算 B2(n-k,k) 即可。

证明 2

当 n=0 时，显然只剩一种情况：不放球，所以方案数为 1。

当 k=0 时，显然没盒子就不能放，所以方案数为 0。

当 k > n 时，显然一定有盒子是空的，因为盒子不标号，所以空哪个都一样，所以可以直接把多余的盒子去掉，计算 B2(n,n)。

剩下的我们可以分 2 种情况考虑放球：

考虑去掉一个盒子使得它保持现在的数量不变,计算 B2(n,k-1)。

否则，就给所有的盒子一个球，计算 B2(n-k,k)。

证明 3

考虑隔板法， n 个球有 n-1 个空隙，要插入 k-1 个隔板将球分成 k 份，就是 C_{n-1}^{k-1}。

证明 4

考虑先给每个盒子里放一个球，这样转化成了 n+k 个球放入 k 个盒子，盒子不能为空，根据公式 3 可得答案为 C_{n+k-1}^{k-1}。

证明 6

显然我们可以枚举空盒子的个数，然后就是第二类斯特林数了。