Question

Llamamos a una permutación $a_1, a_2, \ldots, a_n$ de los enteros $1, 2, \ldots, n$ casi creciente si $a_k \le a_{k+1} + 2$ para cada $1 \le k \le n - 1.$ Por ejemplo, $53421$ y $14253$ son permutaciones casi crecientes de los enteros $1, 2, 3, 4, 5,$ pero $45123$ no lo es. Halla el número de permutaciones casi crecientes de los enteros $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.$

Respuesta

Solución:

Sea $S_n$ el número de permutaciones casi crecientes de $1, \ldots, n.$ Inserta $n$ en una permutación casi creciente de $1, \ldots, n - 1:$ la entrada que sigue a $n$ debe ser al menos $n - 2,$ así que $n$ puede ir inmediatamente antes de $n - 1,$ inmediatamente antes de $n - 2,$ o al final; exactamente $3$ posiciones, y cada inserción mantiene intacta cada otra condición de adyacencia.

Recíprocamente, eliminar $n$ de una permutación casi creciente de $1, \ldots, n$ deja una permutación casi creciente de $1, \ldots, n - 1,$ ya que las entradas alrededor del $n$ eliminado cumplen $a_{k-1} \le n - 1 \le a_{k+1} + 2$ cuando $n \ge 3.$ Así que $S_n = 3S_{n-1}$ para $n \ge 3.$

Como $S_2 = 2,$ obtenemos $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 Problema 10

Solución:

El Problema 10 en otros años