Question

Halla el número de permutaciones de $1, 2, 3, 4, 5, 6$ tales que para cada $k$ con $1 \le k \le 5,$ al menos uno de los primeros $k$ términos de la permutación es mayor que $k.$

Find the number of permutations of $1, 2, 3, 4, 5, 6$ such that for each $k$ with $1 \le k \le 5,$ at least one of the first $k$ terms of the permutation is greater than $k.$

Respuesta

Solución:

La condición falla exactamente cuando los primeros $k$ términos son una permutación de $\{1, \ldots, k\}$ para algún $k \le 5.$ Para una permutación de $1, \ldots, n,$ sea $k$ la menor longitud para la cual el prefijo es $\{1, \ldots, k\}$ (la longitud total $n$ siempre funciona), y sea $c_n$ el número de permutaciones cuyo menor $k$ de este tipo es $n.$ Queremos $c_6.$

Cada permutación de $1, \ldots, n$ se descompone de forma única como un prefijo mínimo de longitud $k$ ( $c_k$ opciones) seguido de cualquier ordenamiento de los $n - k$ valores restantes, así que $\sum_{k=1}^{n} c_k \,(n-k)! = n!.$ Partiendo de $c_1 = 1,$ esto da $c_2 = 1,$ $c_3 = 3,$ $c_4 = 13,$ $c_5 = 71,$ y $\begin{aligned} c_6 &= 720 \\ &\quad {}- \tiny(120 \cdot 1 + 24 \cdot 1 + 6 \cdot 3 + 2 \cdot 13 + 1 \cdot 71) \\ &= 720 - 259 = 461. \end{aligned}$

The condition fails exactly when the first $k$ terms are a permutation of $\{1, \ldots, k\}$ for some $k \le 5.$ For a permutation of $1, \ldots, n,$ let $k$ be the smallest length for which the prefix is $\{1, \ldots, k\}$ (the full length $n$ always works), and let $c_n$ be the number of permutations whose smallest such $k$ is $n.$ We want $c_6.$

Every permutation of $1, \ldots, n$ decomposes uniquely as a minimal prefix of length $k$ ( $c_k$ choices) followed by any arrangement of the remaining $n - k$ values, so $\sum_{k=1}^{n} c_k \,(n-k)! = n!.$ Starting from $c_1 = 1,$ this gives $c_2 = 1,$ $c_3 = 3,$ $c_4 = 13,$ $c_5 = 71,$ and $\begin{aligned} c_6 &= 720 \\ &\quad {}- \tiny(120 \cdot 1 + 24 \cdot 1 + 6 \cdot 3 + 2 \cdot 13 + 1 \cdot 71) \\ &= 720 - 259 = 461. \end{aligned}$

2018 AIME II Problema 11

Solución:

El Problema 11 en otros años