每日一题[3503]洗牌

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$ 比较大的情形．