2026年3月湖北武汉调研考试数学试卷 #19
有 $n$ 张编号分别为 $1$ 到 $n$ 的卡片，横向随机排列．对于这 $n$ 张卡片，初始状态下卡片标号从左到右为 $A_1,A_2,\cdots ,A_n$，记此时的卡片排列为 $\left(A_1,A_2,\cdots A_n\right)$．对这 $n$ 张卡片的排列进行如下三步操作： $1$．取出最左边的卡片，记其标号为 $k $； $2$．剩余卡片中，标号小于 $k$ 的卡片按照原排列中的从左到右顺序依次为 $L_1,L_2,\cdots, L_{k-1}$（若不存在则为空），标号大于 $k$ 的卡片按照原排列中的从左到右顺序依次为 $R_1,R_2,\cdots, R_{n-k}$（若不存在则为空）； $3$．对这 $n$ 张卡片重新排列，得到新排列：$\left(L_1,L_2,\cdots L_{k-1},k,R_1,R_2,\cdots R_{n-k}\right)$． 每进行完上述三步操作，称为一次完整操作．
1、若初始排列为 $(3,5,2,4,1)$，写出连续经过两次完整操作后得到的新排列；
2、求初始排列经过一次完整操作后恰好能得到 $(1,2,\cdots,n)$ 的顺序排列的概率；
3、记初始排列中有 $B_n$ 个排列种数能经过连续若干次完整操作后能得到 $(1,2,\cdots,n)$ 的顺序排列，当 $n\geqslant 2$ 时，证明：$B_{n+1}\leqslant n B_n+B_{n-1}$．
解析
1、根据题意，有\[(3,5,2,4,1)\to (2,1,3,5,4)\to (1,2,3,5,4).\]
2、设初始排列满足要求且最左边的卡片标号为 $k$（$k=1,2,\cdots,n$），则经过一次操作后，该排列变为 $(A,k,B)$，其中 $A$ 为 $1,2,\cdots,k-1$，$B$ 为 $k+1,\cdots,n$，于是在操作前 $A,B$ 中各数的相对顺序保持不变，有 $\binom {n-1}{k-1}$ 种可能，因此所求概率为\[ \dfrac{\sum\limits_{k=1}^n\binom{n-1}{k-1}}{n!}=\dfrac{2^{n-1}}{n!}.\]
3、若一个排列经过连续若干次完整操作后能得到 $(1,2,\cdots,n)$，则称该排列为好排列，若排列中的数 $k$ 恰好在第 $k$ 个位置，则称该数是排好的．考虑长度为 $n$ 的好排列，设最左边的数为 $k$（$k=1,2,\cdots,n$），则一次完整操作后，$k$ 必然是排好的，且之后的操作只对前 $k-1$ 个数组成的排列操作，而不会影响后 $n-k$ 个数，因此该排列是好排列等价于前 $k-1$ 个数组成的排列是好排列且后 $n-k$ 个数是排好的，对应的个数为\[\binom{n-1}{k-1}B_{k-1},\]这样就完成了递归，有\[B_n=\sum_{k=1}^n\binom{n-1}{k-1}B_{k-1},\]欲证命题即\[\sum_{k=1}^{n+1}\binom{n}{k-1}B_{k-1}\leqslant nB_n+B_{n-1},\]即\[B_n+nB_{n-1}+\sum_{k=1}^{n-1}\binom{n}{k-1}B_{k-1}\leqslant nB_n+B_{n-1},\]也即\[B_n\geqslant B_{n-1}+\dfrac{1}{n-1}\sum_{k=1}^{n+1}\binom{n}{k-1}B_{k-1},\]而\[B_n=B_{n-1}+\sum_{k=1}^{n-1}\binom{n-1}{k-1}B_{k-1},\]因此只需要证明\[\binom{n-1}{k-1}\geqslant \dfrac{1}{n-1}\binom{n}{k-1}\impliedby n\binom{n-1}{k-1}\geqslant \binom{n}{k-1}+\binom{n-1}{k-1},\]也即\[n\binom{n-1}{k-1}\geqslant \binom nk\impliedby n\binom{n-1}{k-1}\geqslant \dfrac nk\binom {n-1}{k-1}\impliedby k\geqslant 1,\]命题得证．