Question

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.$

Answer

Answer: 486

Concepts:permutations recursive counting

Difficulty rating: 2890

Solution:

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 Problem 10

Answer: 486

Difficulty rating: 2890

Solution:

Problem 10 in Other Years