Número de maneras de organizar $n$ personas en fila

Question

Me encontré con esta pregunta confusa en Combinatoria.

Dado $n \in \mathbb N$ . Tenemos $n$ personas que están sentadas en fila. Marcamos $a_n$ como el número de maneras de reorganizarlos de forma que una persona pueda permanecer en su asiento o desplazarse un asiento a la derecha o un asiento a la izquierda. Calcula $a_n$

Esta es una de las preguntas de combinatoria más difíciles que me he encontrado (todavía estoy a mitad de curso), así que si alguien puede orientarme, ¡se lo agradeceré!

Answer 1

CONSEJO: Es un poco más cómodo pensar en esto en términos de permutaciones: $a_n$ es el número de permutaciones $p_1 p_2\dots p_n$ de $[n]=\{1,\dots,n\}$ tal que $|p_k-k|\le 1$ para cada $k\in[n]$ . Llamamos a estas permutaciones bien .

Supongamos que $p_1 p_2\dots p_n$ es una permutación de este tipo. Es evidente que una de $p_{n-1}$ y $p_n$ debe ser $n$ .

• Si $p_n=n$ entonces $p_1 p_2\dots p_{n-1}$ es una buena permutación de $[n-1]$ . Además, cualquier permutación buena de $[n-1]$ puede extenderse a una buena permutación de $[n]$ con $n$ al final. Así, hay $a_{n-1}$ buenas permutaciones de $[n]$ con $n$ como último elemento.

• Si $p_{n-1}=n$ entonces $p_n$ debe ser $n-1$ Así que $p_1 p_2\dots p_{n-2}p_n$ es una buena permutación de $[n-1]$ con $n-1$ como último elemento. Por el contrario, si $q_1 q_2\dots q_{n-1}$ es una buena permutación de $[n-1]$ con $q_{n-1}=n-1$ entonces $q_1 q_2\dots q_{n-2}nq_{n-1}$ es una buena permutación de $[n]$ con $n$ como penúltimo elemento. ¿Cuántas permutaciones buenas de $[n-1]$ están allí con $n-1$ como último elemento?

---

Como alternativa, puede calcular $a_k$ a mano para $k=0,\dots,4$ y ver qué aparece; deberías reconocer los números que obtienes.