数学全部都去4吧！

1.欧拉错排

题目背景：有$n$个小球，编号分别是$1->n$，要求把小球放在编号为$1->$的盒子中且小球编号与盒子编号不同(每个盒子各放一个)

递推式：$f[n]=(n-1) \times (f[n-1]+f[n-2])$

推导过程：

在考虑放第$n$个数时，考虑两种情况

$$\begin{aligned} &<1>前面的数全部放错，可以拿第n个数任意和前面的数交换，情况数为(n-1) \times f[n-1]\\ &<2>前面的数恰有一个没放错，只能拿第n个与未错数交换，又因为每个数都能成为未错数，情况数为(n-1) \times f[n-2]\\ \end{aligned}$$

综上所述，$f[n]=(n-1) \times f[n-1]+(n-1) \times f[n-2]=(n-1) \times (f[n-1]+f[n-2])$

边界情况：$f[0]=1，f[1]=0$，具体为什么是这样呢

$$\begin{aligned} &f[0]=1，既没有盒子也没有球，这就是一种情况(其实这个理解挺玄幻的)\\ &f[1]=0，只有一个盒子和一个球，球一只能放在盒一里，不存在满足条件的解\\ \end{aligned}$$

---

2.Catalan数

题目背景：将$n$个$0$和$n$个$1$排成一个序列，满足任意前缀中$0$的数量不小于$1$的数量

封闭形式：$Cat_n=C_{2n}^{n}-C_{2n}^{n-1}$

递推式：$Cat_n=\frac{4n-2}{n+1}Cat_{n-1}=\sum_{p=1}^{n}Cat_{p-1} \times Cat_{n-p}，Cat_1=1$

推导过程：

<1>

不受限制的排列数：$C_{2n}^{n}$

对于任意一个不合法的排列$S$，$S$中存在一个最靠前的位置$2p+1\in [1,2n]$，使得$S$中有$p$个$0$，$p+1$个$1$

我们从$2p+2$开始，将后面序列中的$01$相互交换，这样，我们得到了一个长度为$2n$的排列，并且该排列中有$n-1$个$0$，$n+1$个$1$，即任意一个非法的排列$S$都可以与一个$n-1$个$0$，$n+1$个$1$得到的排列对应

反过来，任意一个$n-1$个$0$，$n+1$个$1$得到的排列，我们找到最小的位置$2p+1$，满足该位置处第一次出现$1$的个数多余$0$的个数（该位置一定存在），然后将$2p+2$到$2n$位置上的$01$相互交换，这样，我们得到了一个长度为$2n$，$n$个$0$，$n$个$1$的排列，故任意一个$n-1$个$0$，$n+1$个$1$得到的排列，都对应了一种$n$个$0$，$n$个$1$的排列，且该排列满足某个位置$1$出现的个数比$0$出现的个数多

由以上两点可知，这两种排列一一对应，故非法的排列数量为$C_{2n}^{n-1}$，容斥便可得到封闭式

将封闭式变形合并即可得到递推式$Cat_n=\frac{4n-2}{n+1}Cat_{n-1}$

<2>

对于任意一个合法的排列，一定存在某个最靠前的位置$2p$，满足到该位置为止，$0$出现的次数刚好等于$1$出现的次数

从$2p+1->2n$，始终满足$0$的个数不少于$1$的个数，所以这部分的排列数依然是卡特兰数

从$1->2p$呢？

因为直到$2p$才满足$0$的个数和$1$的个数相等，又因为$2p$处肯定为$1$, 这意味这$1->2p-1$始终满足$0$的个数多余$1$的个数，去掉第一个位置的$0$，从 $2->2p-1$, 始终满足$0$的个数大于等于$1$的个数，所以我们去掉头部的$0$，$2p$处的$1$，中间的部分就是一个满足卡特兰数的排列，

所以，当$2p$是第一个$0$，$1$个数相等的位置时，方案数为$Cat_{p-1} \times Cat_{n-p}$

因为$1 \leq p \leq n$，所以$Cat_n=\sum_{p=1}^{n}Cat_{p-1} \times Cat_{n-p}$

---

3.Stirling数

斯特林数分为两类

<1>第一类斯特林数

题目背景：把$n$个互不相同的小球构成$r$个圆排列

递推式：$Sti_{r}^{n}=(n-1) \times Sti_{r}^{n-1} \times Sti_{r-1}^{n-1}$

推导过程：在考虑$Sti_{r}^{n}$($n$个球构成$r$个圆排列)时，考虑两种情况

如果将第$n$个数单独构成一个圆排列，则方案数就变为了$Sti_{r-1}^{n-1}$

否则考虑将第$n$个数放在已构好的圆排列中，即$Sti_{r}^{n-1}$

因为是圆排列，只关心相对位置，所以有$n-1$种可能(可以想象成把$n$和另一个数合并得到一个新数)，方案数就是$(n-1) \times Sti_{r}^{n-1}$

由乘法原理就可算得递推式

边界情况：$Sti_{n}^{n}=1$，恰好每个圆内放一个数才满足条件

$Sti_{n}^{0}=0$，至少要一个圆放数才能满足条件

<2>第二类斯特林数

题目背景：把$n$个互不相同的小球放进$r$个相同的盒子，每个盒子至少一个球

递推式：$Sti_{r}^{n}=r \times Sti_{r}^{n-1} \times Sti_{r-1}^{n-1}$

推导过程：第二类斯特林数和第一类很像，这里不过多赘述

唯一的区别在于在第二类斯特林数中，元素在哪些集合并不重要，唯一重要的是各集合里装的是什么，而不管哪个集合装了什么

所以我们的选择就变成了$r$种每个盒子中讨论放入