Question

若整数 $1, 2, \ldots, n$ 的一个排列 $a_1, a_2, \ldots, a_n$ 满足对每个 $1 \le k \le n - 1$ 都有 $a_k \le a_{k+1} + 2$ ，则称它为准递增排列。例如， $53421$ 和 $14253$ 是整数 $1, 2, 3, 4, 5$ 的准递增排列，但 $45123$ 不是。求整数 $1, 2, \ldots, 7$ 的准递增排列个数。

Call a permutation $a_1, a_2, \ldots, a_n$ of the integers $1, 2, \ldots, n$ quasi-increasing if $a_k \le a_{k+1} + 2$ for each $1 \le k \le n - 1.$ For example, $53421$ and $14253$ are quasi-increasing permutations of the integers $1, 2, 3, 4, 5,$ but $45123$ is not. Find the number of quasi-increasing permutations of the integers $1, 2, \ldots, 7.$

答案

答案：486

知识点：排列递推计数

难度评级：2890

解答：

设 $S_n$ 为 $1, \ldots, n$ 的准递增排列个数。把 $n$ 插入一个 $1, \ldots, n - 1$ 的准递增排列中：紧跟在 $n$ 后面的数必须至少为 $n - 2$ ，所以 $n$ 可以放在 $n - 1$ 正前方、 $n - 2$ 正前方，或最后面，恰好有 $3$ 个位置；每种插入都会保持其他相邻条件不变。

反过来，从一个 $1, \ldots, n$ 的准递增排列中删除 $n$ 会留下一个 $1, \ldots, n - 1$ 的准递增排列，因为当 $n \ge 3$ 时，被删去的 $n$ 两侧的数满足 $a_{k-1} \le n - 1 \le a_{k+1} + 2$ 。所以对 $n \ge 3$ 有 $S_n = 3S_{n-1}$ 。

因为 $S_2 = 2$ ，所以 $S_7 = 2 \cdot 3^5 = 486$ 。

Let $S_n$ be the number of quasi-increasing permutations of $1, \ldots, n.$ Insert $n$ into a quasi-increasing permutation of $1, \ldots, n - 1:$ the entry following $n$ must be at least $n - 2,$ so $n$ can go immediately before $n - 1,$ immediately before $n - 2,$ or at the very end — exactly $3$ positions, and each insertion keeps every other adjacent condition intact.

Conversely, deleting $n$ from a quasi-increasing permutation of $1, \ldots, n$ leaves a quasi-increasing permutation of $1, \ldots, n - 1,$ since the entries around the deleted $n$ satisfy $a_{k-1} \le n - 1 \le a_{k+1} + 2$ when $n \ge 3.$ So $S_n = 3S_{n-1}$ for $n \ge 3.$

Since $S_2 = 2,$ we get $S_7 = 2 \cdot 3^5 = 486.$

2015 AIME II 第 10 题

答案：486

难度评级：2890

解答：

其他年份的第 10 题