EGMO-2020-P4

Enunciado

Unha permutación $(\sigma (1),\dots ,\sigma (n))$ dos enteiros $\{1,2,\dots ,n\}$ dise irreducible se non existe $k<n$ enteiro tal que $\{\sigma (1),\sigma (2),\dots ,\sigma (k)\}=\{1,2,\dots ,k\}$. Por exemplo, $(3,1,4,2)$ é irreducible pero $(2,3,1,4)$ non.

Sexa $f_n$ o número de permutacións irreducibles de $\{1,2,\dots ,n\}$. Demostra que $f_n\ge n\cdot f_{n-1}$ para $n\ge 3$.

---

Resolución

Pista

Intenta obter $n$ permutacións irreducibles de $\{1,2,\dots ,n\}$ de cada unha das permutacións irreducibles de $\{1,2,\dots ,n-1\}$.

Solución

Sexa $(\sigma (1),\dots ,\sigma (n-1))$ unha permutación irreducible de $\{1,2,\dots ,n-1\}$. Dado $1\le i\le n-1$, definimos ${\sigma }^{(i)}=(\sigma (1),\dots ,\sigma (i-1),n,\sigma (i),\dots ,\sigma (n-1))$.

Probemos que ${\sigma }^{(i)}$ é una permutación irreducible de $\{1,2,\dots ,n\}$: sexa $1\le k\le n-1$. Se $k\ge i$, entón $n\in \{{\sigma }^{(i)}(1),\dots ,{\sigma }^{(i)}(k)\}$ pero $n\notin \{1,2,\dots ,k\}$, polo que $\{{\sigma }^{(i)}(1),\dots ,{\sigma }^{(i)}(k)\}\ne \{1,2,\dots ,k\}$. Se $k<i$ entón $k<n-1$, polo que $\{{\sigma }^{(i)}(1),\dots ,{\sigma }^{(i)}(k)\}=\{\sigma (1),\dots ,\sigma (k)\}\ne \{1,2,\dots ,k\}$, xa que $(\sigma (1),\dots ,\sigma (n-1))$ é una permutación irreducible de $\{1,2,\dots ,n-1\}$.

Temos entón que para $1\le i\le n-1$, ${\sigma }^{(i)}$ é permutación irreducible de $\{1,2,\dots ,n\}$, polo que $f_n\ge (n-1)\cdot f_{n-1}$. Necesitamos entón obter unha permutación irreducible nova a partir de $(\sigma (1),\dots ,\sigma (n-1))$ para obter a cota desexada.

Nótese que unha permutación irreducible de $\{1,2,\dots ,m\}$ necesariamente non pode acabar en $m$, polo que $(\sigma (1),\dots ,\sigma (n-1))$ acaba sempre nun número distinto a $n-1$. De forma similar, unha permutación irreducible de $\{1,2,\dots ,n\}$ non pode acabar en $n$, pero se nos fixamos ben podemos ver que todos os ${\sigma }^{(i)}$ non só non terminan co $n$, senón que tamén evitan o $n-1$, o cal é unha restrición non necesaria a priori. Esta é a última idea clave da resolución, e agora só falta obter unha nova permutación irreducible a partir de $(\sigma (1),\dots ,\sigma (n-1))$ que termine en $n-1$.

Sexa $(\sigma (1),\dots ,\sigma (n-1))$ unha permutación irreducible de $\{1,2,\dots ,n-1\}$ e sexa $j$ natural tal que $\sigma (j)=n-1$n entón definimos ${\sigma }^{\ast }=(\sigma (1),\dots ,\sigma (j-1),n,\sigma (j+1),\dots ,\sigma (n-1),n-1)$. Con un argumento análogo ó realizado no estudio das ${\sigma }^{(i)}$, próbase que ${\sigma }^{\ast }$ é permutación irreducible de $\{1,2,\dots ,n\}$, polo que concluímos que $f_n\ge n\cdot f_{n-1}$, tal como queríamos demostrar.

---

Dúbidas & Comentarios

Nesta sección pódesnos deixar as túas dúbidas e comentarios a cerca do problema anterior. Non teñas teima en preguntar, estamos aí para botar unha man!