问题描述
已知递推数列：
$$ A_n = (n-1)(A_{n-1} + A_{n-2}), \quad n \ge 3 $$初始条件：
$$ A_1 = 0, \quad A_2 = 1 $$求 ${A_n}$ 的通项公式。
背景知识：该数列即为组合数学中的错排数（Derangement Number），通常记为 $D_n$ 或 $!n$。它表示 $n$ 个元素排列后，没有任何一个元素出现在其原始位置上的排列总数。
推导过程
1. 变形递推关系
将原递推公式展开：
$$ A_n = (n-1)A_{n-1} + (n-1)A_{n-2} $$为了构造可解的形式，我们在等式两边同时减去 $n A_{n-1}$：
$$ \begin{aligned} A_n - n A_{n-1} &= (n-1)A_{n-1} + (n-1)A_{n-2} - n A_{n-1} \\ &= -A_{n-1} + (n-1)A_{n-2} \\ &= -(A_{n-1} - (n-1)A_{n-2}) \end{aligned} $$其实你可以用待定系数法强行构造出来一个等比然后再展开求解
2. 构造辅助数列
令 $B_n = A_n - n A_{n-1}$ ($n \ge 2$)。 由上式可得：
$$ B_n = -B_{n-1} $$这表明 ${B_n}$ 是一个公比为 $-1$ 的等比数列。
计算首项 $B_2$：
$$ B_2 = A_2 - 2 A_1 = 1 - 2 \times 0 = 1 $$因此, ${B_n}$ 的通项为：
$$ B_n = B_2 \cdot (-1)^{n-2} = 1 \cdot (-1)^{n-2} = (-1)^n $$(注: $(-1)^{n-2} = (-1)^n \cdot (-1)^{-2} = (-1)^n$)
代回 $B_n$ 的定义，得到新的递推关系：
$$ A_n - n A_{n-1} = (-1)^n \implies A_n = n A_{n-1} + (-1)^n $$3. 累加
将上式两边同时除以 $n!$：
$$ \frac{A_n}{n!} = \frac{A_{n-1}}{(n-1)!} + \frac{(-1)^n}{n!} $$令 $C_n = \frac{A_n}{n!}$，则有：
$$ C_n - C_{n-1} = \frac{(-1)^n}{n!} $$对 $k$ 从 $2$ 到 $n$ 进行累加：
$$ \begin{aligned} C_n &= C_1 + \sum_{k=2}^n (C_k - C_{k-1}) \\ &= \frac{A_1}{1!} + \sum_{k=2}^n \frac{(-1)^k}{k!} \end{aligned} $$由于 $A_1 = 0$，故 $C_1 = 0$。
$$ C_n = \sum_{k=2}^n \frac{(-1)^k}{k!} $$观察求和项：
- 当 $k=0$ 时, $\frac{(-1)^0}{0!} = 1$
- 当 $k=1$ 时, $\frac{(-1)^1}{1!} = -1$
- 前两项之和 $1 + (-1) = 0$，不影响总和。
因此可以将求和下标扩展至 $0$：
$$ C_n = \sum_{k=0}^n \frac{(-1)^k}{k!} $$4. 得出通项公式
由 $A_n = n! \cdot C_n$，最终得到：
$$ A_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!} $$最终结论
该数列的通项公式为：
$$ A_n = n! \left( 1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!} \right) $$或者写作求和符号形式：
$$ A_n = \sum_{k=0}^n (-1)^k \frac{n!}{k!} $$近似公式
当 $n$ 较大时，由于 $\sum_{k=0}^\infty \frac{(-1)^k}{k!} = e^{-1} = \frac{1}{e}$，该公式可近似为：
$$ A_n \approx \frac{n!}{e} $$精确值为最接近 $\frac{n!}{e}$ 的整数：
$$ A_n = \left[ \frac{n!}{e} \right] $$(其中 $[x]$ 表示四舍五入取整)