组合数学中的遭遇数（rencontre numbers）与子阶乘（subfactorial）

组合 遭遇数 子阶乘

---

参考wiki上的说明：
https://en.wikipedia.org/wiki/Rencontres_numbers
http://oeis.org/wiki/Rencontres_numbers
这两个网页里都没给证明，很多东西莫名其妙，但手头上又没有组合数学的书，于是就自己推了一遍

碰到这个点是因为看论文时里面的定理证明需要，定理来自于：KDD,2011, On the Privacy of Anonymized Networks

问题：对于$n\geq 0$个数，还有n个位置，正确的情况是这n个数与对应的n个位置一一对应，如1和第一个位置对应，2和第二个位置对应等等。现在需要知道，假如摆对位置（也就是置换permutation，将置换理解成一一对应即可）的数只有$0\leq k \leq n$个，其他全部摆错的情况下总共有多少种可能的摆放组合方式，记为$D_{n,k}$，这个数就称之为遭遇数。

计算方式：
我们认为$D_{0,0}=1$，此外，可知$D_{1,0}=0$，这是因为总共就一个数，一个位置，那么自然不可能出现摆错的情况。仍然以$k=0$（即所有数的位置都摆错了）为例，可以得出一个递归的表达式$D_{n+2,0}=(n+1)(D_{n+1,0}+D_{n,0})$。这个式子可以这样理解：有一个数摆错了，此时可能的错位置有n+1种，对于剩下的n+1个数，有两种情况，假设数1摆到了位置3上，那么数3有两种情况，第一种是数3正好摆到了位置1上，此时就对应$D_{n,0}$，第二种是数3不在位置1上，那么错的位置有$n$种，在下一次计算时3可以等价地看成1（因为和1一样不能放在位置1上），此时就对应$D_{n+1,0}$。
注：$D_{0,0}=1$是合理的，因为$D_{2,0}$显然等于1，那么根据递归式子计算可以得出$D_{0,0}=1$。

上面说的是$k=0$时的情况，对于$k \geq 0$，可以得出$D_{n,k}=C_n^k \cdot D_{n-k, 0}$。可以看出，关键仍然是如何计算$D_{n,0}$（也就是子阶乘的表达式）。首先，考虑$D_{n,0}$和$D_{n,1}$之间的关系。可以自然的得到第一个等式$D_{n,1}=nD_{n-1,0}$。接下来考虑一个问题，是否存在一个$f(n)$，使得$D_{n,0}=D_{n,1}+f(n)$对于任一的$n\geq 0$恒成立呢？一旦存在，也就是存在某些可能通过递归式子计算出子阶乘的表达式。

假设存在，那么可以推出以下式子：

$$D_{n,0}=nD_{n-1,0}+f(n)\\ $$
又因为$D_{n,0}=(n-1)(D_{n-1,0}+D_{n-2,0})$，两式相减可得
$$f(n)=(n-1)D_{n-2,0}-D_{n-1,0}$$
因为$D_{n-2,0}=\frac{1}{n-1} D_{n-1,1}$，所以
$$f(n)=D_{n-1,1} - D_{n-1,0}$$
所以，存在$f(n)=D_{n-1,1} - D_{n-1,0}$使得$D_{n,0}=D_{n,1}+f(n)$对于任一的$n\geq 1$恒成立。
进一步，因为$D_{n,0}=D_{n,1}+f(n)$，所以
$$D_{n,0} - D_{n,1} = D_{n-1,1} - D_{n-1,0}$$
即
$$D_{n,1} - D_{n,0} = (-1)\cdot (D_{n-1,1} - D_{n-1,0})$$
由这个递归式子可以继续推导，
$$D_{n,1} - D_{n,0} = (-1)\cdot (D_{n-1,1} - D_{n-1,0}) \\ = (-1)^2 \cdot (D_{n-2,1} - D_{n-2,0}) \\ = (-1)^{n-1} \cdot (D_{1,1} - D_{1,0}) \\ = (-1)^{n-1}$$
可以发现，最终形式极为简单，也就是说，$f(n)=(-1)^{n-2}$，代入后可得出下式：
$$D_{n,0}=D_{n,1}+(-1)^{n-2}\\ = D_{n,1}+(-1)^{n}$$

接下来的目标是计算$D_{n,0}, n \geq 1$，也就是子阶乘$!n$的表达式，这个较为简单：

$$D_{n,0}= D_{n,1}+(-1)^{n} \\ =nD_{n-1,0} + (-1)^{n} \\ =n \cdot (D_{n-1,0} + \frac{(-1)^{n}}{n}) \\ =n \cdot (n-1) \cdot (D_{n-2,0} + \frac{(-1)^{n-1}}{n-1} + \frac{(-1)^{n}}{n(n-1)})\\ \ldots \\ =n! \cdot \sum_{k=0}^n \frac{(-1)^k}{k!}$$
进一步的关于子阶乘的一些基本内容也很容易证得，比如和欧拉常数的关系，由函数级数相关的知识可知$e^{x} = \sum_{k=0}^{\infty} \frac{(x)^k}{k!}$，令$x=-1$，则
$$lim_{n \rightarrow \infty} \frac{n!}{D_{n,0}} = lim_{n \rightarrow \infty} \frac{n!}{!n} = e$$