组合意义 + 递推
思路
先随便写一下答案，发现是：
$$
Ans = \binom{n}{k}^2 k! 2^k g(n - k)
$$
其中 $g(x)$ 表示 $x$ 对情侣 $x$ 组座位完全没有坐在同组座位的情侣的方案，然后发现 $g$ 写不出来
考虑推递推式
代数方法
考虑到等式：把 $k \in [0, n]$ 的 $Ans$ 全部加起来，就是总方案数 $(2n)!$ ：
$$
\begin{aligned}
& \sum_{k = 0}^n \binom{n}{k}^2 k! 2^k g(n - k) = (2n)! \\
& \sum_{k = 0}^n \frac{2^k}{k!} \times \frac{g(n - k)}{(n - k)!^2} = \frac{(2n)!}{n!^2} \\
\end{aligned}
$$
发现左式是一个卷积，设 $\frac{g(x)}{x!^2}$ 的生成函数是 $G(x)$ ，现在问题是求另外两项的生成函数
首先 $\frac{2^k}{k!}$ 的生成函数显然就是 $e^{2x}$ ，然后来看右式：
$$
\begin{aligned}
& \sum_{n = 0}^{\infty}\frac{(2n)!}{n!^2} x^n \\
= & \sum \frac{(2n)!}{n!^2 2^{2n}} 4^n x^n \\
= & \sum \frac{(2n)(2n - 1)(2n - 2)…3 * 2 * 1}{(2^n n!)(2^n n!)} 4^n x^n \\
= & \sum \frac{(2n)(2n - 1)(2n - 2)…3 * 2 * 1}{(2n)(2n - 2)(2n - 4)…4 * 2 * 1(2^n n!)} 4^n x^n \\
= & \sum \frac{(2n - 1)(2n - 3)…3 * 1}{(2^n n!)} 4^n x^n \\
= & \sum \frac{2^n(n - \frac{1}{2})(n - \frac{3}{2})…\frac{3}{2} * \frac{1}{2}}{(2^n n!)} 4^n x^n \\
= & \sum \frac{(n - \frac{1}{2})(n - \frac{3}{2})…\frac{3}{2} * \frac{1}{2}}{n!} 4^n x^n \\
= & \sum \frac{(-1)^{n} (-\frac{1}{2}) * (-\frac{3}{2})…(\frac{3}{2} - n) (\frac{1}{2} - n)}{n!} (4x)^n \\
= & \sum \frac{(-\frac{1}{2})^{\underline{n}}}{n!} (-1)^{n} (4x)^n \\
= & \sum_{n = 0}^{\infty} \binom{-\frac{1}{2}}{n} (-1)^{n} (4x)^n \\
& 由广义二项式定理得: \\
= & (1 - 4x)^{-\frac{1}{2}}
\end{aligned}
$$
现在带回，得到关于 $G(x)$ 的方程：
$$
\begin{aligned}
& G(x) * e^{2x} = (1 - 4x)^{-\frac{1}{2}} \\
& G(x) = \frac{e^{-2x}}{\sqrt{1 - 4x}}
\end{aligned}
$$
我们现在要求 $G(x)$ 各项系数的关系，套路（woc ，那里套路了）求导：
$$
\begin{aligned}
& G’(x) = 8 x e^{-2x} (1 - 4x)^{-\frac{3}{2}} \\
& 用 G(x) 表示 G’(x) 有: \\
& G’(x) = \frac{8 x G(x)}{1 - 4x} \\
& (1 - 4x) G’(x) = 8 x G(x) \\
& G’(x) = 4 x G’(x) + 8 x G(x)
\end{aligned}
$$
显然有：
$$
\begin{aligned}
[x^n] G’(x) = (n + 1)[x^{n + 1}] G(x) \\
x [x^n] G(x) = [x^{n - 1}] G(x)
\end{aligned}
$$
提取系数：
$$
\begin{aligned}
& [x^n] G’(x) = 4 [x^{n - 1}] G’(x) + 8 [x^{n - 1}] G(x) \\
& (n + 1) [x^{n + 1}] G(x) = 4 n [x^{n}] G(x) + 8 [x^{n - 1}] G(x) \\
& (n + 1) \frac{g(n + 1)}{(n + 1)!^2} = 4 n \frac{g(n)}{n!^2} + 8 \frac{g(n - 1)}{(n - 1)!^2} \\
& \frac{g(n + 1)}{n! (n + 1)!} = 4 \frac{g(n)}{n!(n - 1)!} + 8 \frac{g(n - 1)}{(n - 1)!^2} \\
& g(n + 1) = 4 n (n - 1)g(n) + 8 n (n - 1)^2 g(n - 1)\\
& g(n) = 4 n (n - 1)g(n - 1) + 8 n (n - 1)^2 g(n - 2)\\
\end{aligned}
$$
边界显然是 $g(0) = 1, g(1) = 0$
组合方法
这才是唯一真神
考虑 $g(n)$ 的组合意义，是 $x$ 对情侣 $x$ 组座位完全没有坐在同组座位的情侣的方案
考虑第一组座位，我们要选出两个不是情侣的人，显然有 $2n(2n - 2)$ 种选法，假设我们选的是 $A, B$ 考虑它们的配偶 $a, b$ ：
- 如果 $a, b$ 坐在一起，有 $2(n - 1)$ 种方案，然后要把 $n - 2$ 组座位分给 $n - 2$ 对情侣，就是 $g(n - 2)$
- 否则，把 $a, b$ 作为一对新的情侣（它们不能坐在一起），就是 $n - 1$ 组座位分给 $n - 1$ 对情侣，就是 $g(n - 1)$
综上 $g(n) = 2n(2n - 2)[2(n - 1) g(n - 2) + g(n - 1)]$
代码
1 |
|