每日一题[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}\]

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表评论