2024年北京大学强基计划数学试题（回忆版）#3
在 $1,2, \cdots, 8$ 的排列中没有出现连续的两个数（$12,23, \cdots, 78$）的个数为（ ）
A．$14325$
B．$16687$
C．$17429$
D．以上答案都不对
答案 B．
解析 这个题有很强的背景．
新的问题 取 $n$ 张扑克牌，分别为 $1,2,\cdots,n$，经过洗牌（即排列）后如果原来的连张（如 $12,23,\cdots$）都被破坏了，那么称之为好的洗牌，求好的洗牌数．
解法一 设 $n$ 张牌的好的洗牌数为 $a_n$．我们把洗好的牌中的连张合并成堆，最后 $n$ 张牌变成若干堆，如 $1,2,3,4,5$ 会变成 $1$ 堆，$5,4,1,3,2$ 会变成 $5$ 堆，而 $2,3,1,4,5$ 会变成 $3$ 堆．这样好的洗牌数就是堆数为 $n$ 堆的洗牌数，而堆数为 $k$ 的洗牌数为 $\dbinom {n-1}{k-1}\cdot a_k$，这样就有\[\sum_{k=1}^n\dbinom {n-1}{k-1}\cdot a_k=n!,\]于是依次计算可得 ${}^{[1]}$\[\begin{array}{c|c|c|c|c|c|c|c|c}\hline n&1&2&3&4&5&6&7&8\\ \hline a_n&1&1&3&11&53&309&2119&16687\\ \hline\end{array}\]
解法二 通过解法一的探索可以得到对于 $n$ 张牌的好的洗牌，去掉第 $n$ 张牌，那么堆数或者为 $n-1$，或者为 $n-2$，因此可以得到递推公式\[ a_n=(n-1)a_{n-1}+(n-2)a_{n-2},\]这样可以更快的完成递推计算．
容斥原理 考虑有 $k$ 个二连张的排列数为 $\dbinom {n-1}k\cdot (n-k)!$，根据容斥原理，有\[ a_n=\sum_{k=0}^n(-1)^k\dbinom {n-1}k\cdot (n-k)!,\]于是 ${}^{[2]}$\[ \begin{split} a_8&=8!-\dbinom71\cdot 7!+\dbinom72\cdot 6!-\dbinom73\cdot 5!+\dbinom74\cdot 4!-\dbinom75\cdot 3!+\dbinom76\cdot 2!-\dbinom77\cdot 1!\\ &=40320-35280+15120-4200+840-126+14-1\\ &=16687.\end{split}\]
[1] 这些数恰好是相邻两个错排数之和．
[2] 对于选择题可以考虑尾数（但无法排除选项 $\boxed{D}$），这样容斥原理的做法可以很方便的处理 $n$ 比较大的情形．