在本文开始前，读者需要知道以下两种组合数学基本计数原理：

加法原理

当事件 $S$ 可以由若干种不同方案 $T$ 得到，那么 $S$ 的方案数等于每种 $T$ 方案数之和，形式化的有：

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

乘法原理

当事件 $S$ 可以划分成若干个步骤 $T$，那么 $S$ 的方案数等于每个步骤 $T$ 方案数之积，形式化的有：

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

---

排列计数是一类很经典的问题。

从一个最基本的问题入手：

求出 $n$ 个数的排列个数 $f_n$。

这是一个经典的组合入门问题，后文我们称这样的排列为 $n$ 位的排列。

如果我们钦定从第一位开始往后依次给每一位填数，则第 $i$ 位有 $n-i+1$ 种选法，由乘法原理易得：

$$f_n = \prod _{i=1}^n (n-i+1) = \prod _{i=1}^n i = n! $$

或者我们考虑删去 $p_i = n$ 的那一位 $i$，那么得到的一定是唯一的一个 $(n-1)$ 位的排列，而一个 $(n-1)$ 位的排列有 $n$ 个位置加入 $p_i = n$ 那一位，所以可以得到递推方程：

$$f_1 = 1,f_i = nf_{n-1}$$

易得同样的结果：

$$f_n=n!$$

另外一种视角是：我们先钦定第 $n$ 位选谁，共 $n$ 种选法，而又因为这 $n$ 个数在排列中是本质相同的，所以前 $(n-1)$ 位仍是一个 $(n-1)$ 位的排列，和上面得到的递推式相同，其实本质大同小异。

---

求 $n$ 个数中选出 $m$ 个数排列的方案数 $A_{n}^m$。

$n$ 位的排列显然是这个问题的一个特殊情况，仿照上面的易得：

$$A_n^m=\prod_{i=1}^m (n-i+1)$$

这个东西显然不能像原来那么写了，不过可以拆分：

$$A_n^m=\frac{\prod_{i=1}^n (n-i+1)}{\prod_{i=m+1}^n (n-i+1)} =\frac {n!}{(n-m)!} $$

转换一下视角，我们可以把这个问题的拆分成两个步骤：选 $m$ 个数和把这排列，设 $n$ 个数中选出 $m$ 个数的方案数为 $\binom n m$，把这 $m$ 个数排列的方案数显然为 $m!$，由乘法原理得：

$$A_n^m = \binom n m m!$$

推得：

$$\binom n m = \frac{A_n^m}{m!}=\frac{n!}{(n-m)!m!}$$

至此我们得到了排列组合的通项公式

---

要求排列 $p$ 满足 $p_i\neq i$，求这样的 $n$ 位的排列 $p$ 的个数 $f_n$。

我们称这样的排列 $p$ 为错排。

显然这样的排列无法再次按位一个一个选，因为选到第 $i$ 位时，前 $(i-1)$ 位有没有选到 $i$ 是不一定的，所以第 $i$ 位的方案数也是不一定的。

考虑按递推的视角再次看待这个问题：

对于一个 $n$ 位的错排，我们交换 $p_i = n$ 的第 $i$ 位与第 $n$ 位，并删去最后一位得到新排列 $p'$，那么 $p'$ 显然是一个 $(n-1)$ 位的排列，$p'$ 有什么性质呢？

• $p_n \neq i$，则 $p'_i \neq i$，$p'$ 是一个 $(n-1)$ 位的错排；
• $p_n = i$，则 $p'_i = i$，去掉第 $i$ 位是一个 $(n-2)$ 位的错排。

依据加法原理，$f_n$ 即为上面两种情况方案数之和。

第一种情况下，对于每一种 $p'$，都有 $(n-1)$ 种 $i$ 可以选择，由乘法原理得这部分的方案数为

$$cnt(p')\times (n-1) = (n-1)f_{n-1}$$

对于第二种情况，类似的，我们钦定 $p_i = i$ 的那一位，共有 $(n-1)$ 种选择，剩下的部分是一个 $(n-2)$ 位的错排，由乘法原理得，这部分的方案数为：$(n-1)f_{n-2}$。

综上，有：

$$f_0 =1,f_1=0, f_n = (n-1)(f_{n-1}+f_{n-2})$$

这个式子的形式看起来不太好展开，进行一些尝试：

$$\begin{aligned} f_n -f_{n-1}&= (n-1) f_{n-1} + (n-1)f_{n-2} - (n-2)f_{n-2} -(n-2)f_{n-3}\\ &= (n-1)f_{n-1} + f_{n-2} - (n-2)f_{n-3}\\ \end{aligned} $$

拆掉左边的那项 $f_{n-1}$ 只会还原出和原来一样的式子，尝试保留，拆掉 $f_{n-2}$：

$$\begin{aligned} f_n &= nf_{n-1} + f_{n-2} - (n-2)f_{n-3}\\ &= nf_{n-1}+(n-3)f_{n-3} + (n-3) f_{n-4} -(n-2)f_{n-3}\\ &= nf_{n-1}- f_{n-3} + (n-3) f_{n-4} \end{aligned} $$

看起来似乎有规律了，我们展开 $n-3$ 次，此时后面那项 $f_{1} = 0$，前面那项是 $f_2=1$，正负与奇偶相关，写出来是：

$$f_n=nf_{n-1}+(-1)^n$$

前面那项即为普通排列的递推公式，那我们把后面那个东西提出来，贡献单独计算即可。

第 $i$ 位上的 $(-1)^i$ 对 $f_n$ 有什么贡献呢？显然它是藏在 $nf_{n-1}$ 那项往后做贡献的，系数自然也要乘上，易得路过系数的积为 $\frac {n!}{i!}$，那么我们可以得到：

$$f_n = n! +\sum_{i=0}^{n-1} \frac {n!}{i!}(-1)^i=\sum_{i=0}^{n} \frac {n!}{i!}(-1)^i $$

这样我们就得到了 $f_n$ 的展开式，到这里为止我们没有涉及任何进阶一点的组合数学知识，而是直接把它当做数列题来做，这也不失为一种推式子的好方法。

还有一种更具有组合意义一点的解释：我们发现让一些位满足条件是困难的，但是让一些位不满足条件是简单的，考虑做这样的容斥，我们钦定 $c$ 个位 $i$ 上满足 $p_{i} =i$，剩下的位我们随意摆放，这样就得到了至少有 $c$ 个位不满足条件的方案数，记为 $cnt_c$，则有：

$$cnt_c =\binom n c (n-c)!=\frac{n!}{c!}$$

式子的意义即为选出 $c$ 个数，剩下 $(n-c)$ 个数随意排列，得到的方案数。

那么我们需要拿至少有 $c$ 个位不满足条件的方案数 $cnt_c$ 容斥出没有位不满足条件的方案数 $f_n$，可以写出这样一个式子：

$$f_n = \sum_{c=0}^{n} r(c)cnt_c$$

这里，我们称 $r(c)$ 为容斥系数。

上面的推导告诉我们 $r(c) = (-1)^c$，怎么证明呢？

考虑我们对于每一种排列 $p$，计算其在式中对 $f_n$ 的贡献 $W_p$，如果 $W_p$ 在 $p$ 为错排时为 1，否则为 0，则答案正确。

如果 $p$ 有 $k$ 个不满足条件的位置，其在 $cnt_c$ 会被计算 $k$ 个不满足条件位置中，选 $c$ 个出来被钦定的方案数次，即为 $\binom k c$ 次，那么有：

$$W_p = \sum_{c=0}^k \binom k c r(c) = \sum_{c=0}^k \binom k c (-1)^c $$

看起来像二项式，补全成二项式定理的形式：

$$W_p = \sum_{c=0}^k \binom k c (-1)^c 1^{k-c} = (1-1)^k=0^k $$

通常情况下，$W_p$ 常为 0，但是 $k=0$ 时，虽然 $0^0$ 是未定义的，但是带入进去发现此时 $W_p = 1$。

我们发现 $W_p$ 当且仅当 $k=0$ 时才为 1，否则为 0，正对应着我们要求的没有位置不满足条件时，即为 $p$ 为错排时才会对答案做 1 的贡献，证毕。

那么有没有更进一步的做法呢？答案是有的。

设数列 $f_n$ 的生成函数为 $F(x)$，由数列的第一个递推式易得：

$$F= F'x^2 +F'x^3 + Fx^2 + 1$$

整理一下，得到：

$$F'(1+x)x^2 +F(x-1)(1+x) + 1=0$$

左右同除 $(1+x)$ 就可以得到第二个递推式写出来的关系式：

$$F'x^2+F(x-1)+\frac 1 {1+x}=0$$

那么进一步的，再次同除以 $(x-1)$ 呢？

$$F=\frac {F'x^2}{1-x}+\frac {1}{1-x^2}$$

这个东西看起来也很有意义，转化为递推形式有：

$$f_n =\sum _{i=1}^{n-1} if_i +[n \bmod 2=0]$$

这个式子的组合意义后面会有提及。

那么这个方程是不是可解的呢？答案是可以的，但是需要不俗的微积分水平，此处不再提及。

为了更本质的了解排列，我们思考这样一个问题：

对于一个 $n$ 位的错排，构造一张 $n$ 个点的图，对于第 $i$ 位构造一条从 $i$ 指向 $p_i$ 的边，所有 $n$ 位错排的生成图联通块个数之和。

考虑生成的图是什么样子呢？有 $n$ 个点 $n$ 条边，每个点的入度和出度都为 1，那么一个连通块一定是环的形式，我们称这一的一个环为一个置换环。

设 $g_n$ 是 $n$ 位错排的置换环总数，与上面类似的，我们考虑同种形式的转移，什么情况会生成新的置换环呢？

对于 $p_i = n, p_n \neq i$ 的情况，这种情况从 $p'$ 到 $p$ 并没有产生新的置换环，只是把 $n$ 加入了进去罢了，我们直接继承 $p'$ 的置换环大小即可。

而对于 $p_i = n, p_n= i$ 的情况，显然我们比原先多出了一个单独的二元置换环，$p$ 的置换环个数即为原来的 $n-2$ 位错排的置换环个数加一。

那么我们即可写出：

$$g_n = g_{n-1}+g_{n-2}+(n-1)f_{n-2}$$

原先有的置换环数直接继承，剩下每一种第二种情况生成的错排都会多出一个置换环。

我们发现类似原来的展开方法，依次讨论每一个 $(i+1)f_{i}$ 对 $g_n$ 的贡献，每一项的贡献次数递推都是一个斐波那契的形式，设斐波那契数列第 $i$ 项为 $z_i$，有：

$$g_n=\sum_{i=2}^{n-2}(i+1)f_iz_{n-2-i}$$

发现那个 $(i+1)f_i$ 很眼熟，发现上文中有：

$$f_n = nf_{n-1}+(-1)^i$$

那么有：

$$g_n=\sum_{i=3}^{n-1}(f_{i}-(-1)^i)z_{n-1-i}$$

可以拆成卷积处理，设 $z$ 的生成函数为 $Z$，$g$ 的生成函数为 $G$，则有：

$$G=(F-1-x^2 -\frac 1{1+x})Zx$$

同样的，因为 $F$ 并未得到确切的解，本文不再讨论。

我们发现在递推视角下再难发现新东西，考虑切换视角：

对于一个排列，我们可以将其划分为若干个置换环，而对于一个错排，我们可以将其划分为若干个大小大于 1 的置换环。而我们发现，一种置换环划分对应着唯一的一种排列，形成了双射，那么我们何尝不能去对置换环划分进行计数呢？

而对于一个置换环划分来说，置换环之间是互相没有影响的，所以我们既可以从置换环的角度进行计数。

如果我们选定了一个大小为 $c$ 的置换环，那么包含这个 $n$ 位错排有多少个呢？答案是显然的，其他位置共有 $f_{n-c}$ 种方法满足最终划分出来的是错排。而大小为 $c$ 的置换环有多少呢？

从 $n$ 位里面选 $c$ 位组成置换环有 $\binom n c$ 种选法，而这 $c$ 个位会组成出 $(c-1)!$ 种不同的置换环，又因为我们要求置换环大小大于 1，那么有：

$$g_n = \sum_{c=2}^n \binom n c (c-1)! f_{n-c}$$

分解一下，得到：

$$\frac{g_n}{n!}=\sum_{c=2}^n \frac {1}{c}\frac {f_{n-c}}{(n-c)!} $$

这个式子还是体现出了卷积的形式。

我们设 $\hat G$ 为 $\frac {g_n}{n!}$ 的生成函数，$\hat F$ 为 $\frac {f_n}{n!}$ 的生成函数，这类生成函数我们称其为 EGF，它有非常自然的组合结构。

那么我们是否能求出 $\hat F$ 呢？我们发现如果把一个大小为 $c$ 的环的贡献改为 $c$，那么最后求出来的值即为 $nf_n$，因为一个错排所有置换环的大小和为 $n$，可以写出：

$$\begin{aligned} nf_n &= \sum_{c=2}^n \binom n c (c-1)!cf_{n-c}\\ \frac {nf_n} {n!}&= \sum_{c=2}^n \frac {f_{n-c}}{(n-c)!} \end{aligned} $$

这又是一个新的递推式，可以按照它写出 $\hat F$ 的关系式：

$$\begin{aligned} \hat F'x &=\frac {1}{1-x}\hat F-\hat F-\hat Fx\\ \end{aligned} $$

整理一下：

$$\hat F'=\frac {x}{1-x}\hat F$$

我们考虑：

$$(\frac {1}{1-x})'=\frac 1 {(1-x)^2}$$

所以我们猜测 $\hat F$ 中应该有 $\frac 1 {1-x}$，设 $\hat F=\frac P {1-x}$，那么代到原式里：

$$\begin{aligned} (\frac {P}{1-x})' &=\frac {Px}{(1-x)^2}\\ \frac {P'}{1-x} +\frac P{(1-x)^2}&=\frac {Px}{(1-x)^2}\\ P'(1-x)+P&=Px\\ P'(1-x)&=P(x-1)\\ P'&=-P\\ P&=c_1e^{-x} \end{aligned} $$

那么：

$$F=\frac {c_1e^{-x}}{1-x}$$

因为 $f_0 =1$，代入后解得 $c_1 =1$。

其实我们之前数列算出了：

$$\frac {f_n}{n!} =\sum_{i=0}^n \frac {(-1)^i }{i!}$$

而且我们还知道：

$$e^{x}=\sum_{i\geq 0}\frac {1}{i!} x^i$$

可以构造：

$$e^{-x}=\sum_{i\geq 0} \frac {(-1)^i }{i!}x^i$$

那么 $\hat F$ 便是对 $e^{-x}$ 做前缀和得到的，即：

$$\hat F =\frac {e^{^{-x}}}{1-x}$$

我们就这样算出了 $\hat F$，回到上面，构造 $\hat H$：

$$\hat H = \sum_{i\geq 2} \frac {1}{i} x^i$$

我们知道：

$$\frac 1{1-x} = \sum_{i\geq 0} x^i$$

那么有：

$$\hat H = \int \frac {1}{1-x} - x= -\ln (1-x)-x$$

则：

$$\hat G =\hat H\hat F=\frac{[-\ln(1-x)-x] e^{-x}}{1-x} $$

通过构造，我们依然可以取得相同的递推式；而通过泰勒展开，我们可以获取 $\hat G$ 的通项，本文不再赘述。

换一个视角，$f_n$ 可以直接当作对 $n$ 位做一次大小大于 1 的置换环划分得到。

考虑我们构造 $t$ 的指数生成函数 $\hat T$，其中 $t_i$ 代表 $i$ 个数能组成多少个本质不同的且大小大于 1 的置换环，那么：

$$\hat T = \sum_{i\geq 2} \frac {(i-1)!}{i!}x^i = -\ln (1-x)-x $$

这个我们已经求出来过，考虑利用指数生成函数的自然组合性质，即如果我们有数列 $a，b$，则对其指数生成函数 $\hat A,\hat B$ 卷积得到：

$$[x^n]\hat A \hat B=\sum_{i=0}^n \frac {a_i}{i!} \frac {b_{n-1}}{(n-i)!}=\frac {1}{n!} \sum_{i=0}^n \binom n i a_ib_{n-i} $$

得到的结果就是我们对答案进行划分，一部分去 $a$，另外一部分去 $b$，最后方案数乘起来，这样做的方案数的指数生成函数，那么我们枚举总的有多少个置换环，则有：

$$\hat F = \sum_{i\geq 1} \frac {\hat T^i}{i!}=e^{\hat T}=\frac {e^{-x}}{1-x} $$

因为每个置换环是没有顺序的，所以最后除掉 $i!$ 去重，得到了 $\exp$ 意义下的结果，算出了 $\hat F$ 的结果。