2025年2月清华大学THUSSAT测试数学 #19
已知 $\left\{a_1,a_2,a_3,\cdots,a_n\right\}=\{1,2,3,\cdots,n\}$ 其中 $n\geqslant 2$ 且 $n\in\mathbb N$，一个 $n$ 元排列记为 $\left(a_1,a_2,a_3,\cdots,a_n\right)$．如果排列 $\left(a_1,a_2,a_3,\cdots,a_n\right)$ 满足任意 $k\in\{1,2,\cdots,n-1\}$，存在 $m\in\mathbb N$，且 $k<m\leqslant n$ 使得 $\left|a_k-a_m\right|=1$，称其为凝聚排列．
1、写出 $n=4$ 时的所有凝聚排列；
2、求证：凝聚排列 $\left(a_1,a_2,a_3,\cdots,a_n\right)$ 必有 $a_1=1$ 或 $n$；
3、求 $n$ 元凝聚排列的个数．
解析
1、对排列 $p=(a_1,a_2,\cdots,a_n)$，定义 $p$ 的补 $\overline p =(n+1-a_1,n+1-a_2,\cdots,n+1-a_n)$，则 $p$ 是凝聚排列等价于 $\overline p$ 是凝聚排列．而且凝聚数列从结尾倒排，每个数都是之前的数的相邻数，于是先写出\[(4,3,2,1),(1,4,3,2),(4,1,3,2),(1,2,4,3),\]再写出它们的补即可，为\[(4,3,2,1),(1,4,3,2),(4,1,3,2),(1,2,4,3),(1,2,3,4),(4,1,2,3),(1,4,2,3),(4,3,1,2).\]
2、考虑集合 $A_k=\{a_k,\cdots,a_n\}$，则分别令 $k=n-1,n-2,\cdots$ 可知 $A_k$ 中的元素从小到大排列为连续正整数，而\[A_2=\{1,2,3,\cdots,n\}\setminus\{a_1\},\]从而 $a_1=1$ 或 $n$．
3、设 $n$ 元凝聚排列的个数为 $x_n$，则 $x_2=2$，且 $n+1$ 开头的 $n+1$ 元凝聚排列，去掉第一个数后与 $n$ 元凝聚排列一一对应；而 $1$ 开头的 $n+1$ 元凝聚排列取补后去掉第一个数与 $n$ 元凝聚排列一一对应； 综上所述，有 $x_{n+1}=2x_n$，进而 $x_n=2^{n-1}$（$n\in\mathbb N^{\ast}$，$n\geqslant 2$）．