在 1,2,3,4,5,6 的排列中，满足对 k=1,2,3,4,5 都有排列的前 k 项中至少有一个数比 k 大的排列的个数为_______．
答案 461．
解析 对于正整数 n,k（k⩽），若 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}