每日一题[2197]递推计数

在 $1,2,3,4,5,6$ 的排列中，满足对 $k=1,2,3,4,5$ 都有排列的前 $k$ 项中至少有一个数比 $k$ 大的排列的个数为_______．

答案    $461$．

解析    对于正整数 $n,k$（$k\leqslant n$），若 $1,2,3,\cdots,n$ 的一个排列满足前 $k$ 项为 $1,2,\cdots,k$ 的排列，但前 $k+1$ 项（如果有的话）不为 $1,2,\cdots,k+1$ 的排列，则称这个排列为 $k$ 阶不动的．设排列 $1,2,\cdots,n$ $k$ 阶不动排列的个数为 $a_{n,k}$，根据题意，所求排列的个数为 $a_{6,6}$．注意到 $\displaystyle\sum_{k=1}^{n} a_{n, k}=n !$ 且

$$a_{n, k}=(n-k) ! a_{k, k},$$ 于是数列 $\left(a_{n, n}\right)$ 满足递推关系 $$a_{n, 1}=n !-\sum_{k=1}(n-k) ! a_{k, k},$$ 于是有 $a_{1,1}=a_{2,2}=1$，$a_{3,3}=3$．因此 $$\begin{split} a_{4,4}&=24-(6 \cdot 1+2 \cdot 1+1 \cdot 3)=13,\\ a_{5,5}&=120-(24 \cdot 1+6 \cdot 1+2 \cdot 3+1 \cdot 13)=71,\\ a_{6,6}&=720-(120 \cdot 1+24 \cdot 1+6 \cdot 3+2 \cdot 13+1 \cdot 71)=461.\end{split}$$