link
Hint：错排计数。
\(ans_k=C_n^k\times A_n^k\times 2^k\times g(n-k)\)
\(g(i)\) 代表 \(i\) 对情侣全部错开的方案数。
解释一下 \(ans_k\) 的表达。
我们从 \(n\) 对情侣中无序地抽出 \(k\) 对情侣，有序地放到 \(k\) 排座位上，这里的方案数是 \(C_n^k\times A_n^k\)。由于两个相邻的人可以交换，所以需要 \(\times 2^k\)。对于剩下的 \(n-k\) 对情侣，必须要将他们全部错开，显然应该是乘法原理。
或者将 \(C_n^k\times A_n^k\) 视作有序地抽出 \(k\) 对情侣，无序地放到 \(k\) 排座位上也可。
现在考虑一下怎么求 \(g(i)\)，我们选择递推的经典策略。
假设 \(i-1\) 对已经错排好，现在要加入第 \(i\) 对。先来讨论第 \(i\) 对的男生和前面的某一个男生坐在一起的情况，此时该座位的方案数有 \((n-1)\)。假如说他们的情侣坐在一起，那么这里的方案数为 \(2(n-1)\)，\((n-1)\) 代表有 \((n-1)\) 个座位可以选择，\(2\) 代表两个人可以交换位置。对于剩下的 \(n-2\) 对情侣，只需要让他们错排即可，方案数为 \(g(n-2)\)。由于 \(n\) 对情侣中的每一对都可以座位新加入的，所以总方案数还要乘上一个 \(n\)。
当女生坐在一起时同理。对于一男一女坐在一起的情况，总体仍与上面一致，只不过加入这一男一女时的方案数是 \(2(n-1)\)，代表第一个人可以是男也可以是女。
具体见下图：
得到 \(g(n)=4n(n − 1)(2(n − 1)g(n − 2) + g(n − 1))\)。
递推即可。
