Encuentra el número de permutaciones de $1,2,\dots ,n$ que $1$ está en la primera posición y la diferencia entre dos números adyacentes es $\le 2$

Question

Encuentra el número de permutaciones de $1,2,\dots ,n$ que $1$ está en la primera y la diferencia entre dos números adyacentes es $\le 2$

Mi intento Se puede demostrar fácilmente que borrando $n$ se obtiene la misma pregunta para $n-1$ números, así que considera la respuesta de la pregunta $f_n$ . En cualquier caso de $n-1$ números, podemos al menos poner $n$ en un lugar que la condición es verdadera de nuevo. Pero en algunos casos podemos poner $n$ en dos lugares. Me refiero al caso que $n-1$ es al final y $n-2$ es antes de que pueda calcular estos casos. De todos modos, la respuesta en el libro es:

$f_n=f_{n-1}+f_{n-3}+1$

Answer 1

$\textbf{Hint:}$

Dejemos que $a_n$ sea el número de permutaciones de $\{1,\cdots,n\}$ que cumplen esta condición.

1) Demuestre que el número de permutaciones que empiezan por $\textbf{12}$ viene dada por $a_{n-1}$ , ya que cualquier permutación de este tipo puede ${\hspace .2 in}$ se obtiene tomando cualquier permutación válida permutación de $\{1,\cdots,n-1\}$ sumando 1 a cada dígito, y luego colocando un ${\hspace .2 in} 1$ en el frente.

2) Demuestre que el número de permutaciones que empiezan por $\textbf{132}$ viene dada por $a_{n-3}\;$ (de forma similar al último paso).

3) Demuestre que no hay ninguna permutación que empiece por $\textbf{134}\;$ (si $n>4$ ).

4) Demuestre que sólo hay una permutación que empieza por $\textbf{135}\;$ (si $n>4$ ).

Por lo tanto, $a_n=a_{n-1}+a_{n-3}+1$ .

Answer 2

Supongo que su método es correcto, ya que he calculado

$$f_2=1$$

$$f_3=2$$

$$f_4=2+2=4$$

$$f_5=2+2+2=6$$

$$f_6=2+2+2+3=9$$

$$f_7=2+2+2+3+5=14$$

$$f_8=2+2+2+3+5+7=21$$

De estos cálculos se desprende que la parte creciente proviene del último incremento, que representa los números de ese tipo de permutaciones en las que $$2->3$$

Con cálculos sencillos esta parte es $$2*(n-5)+1=2n-9.$$

---

EDITAR:

Para que quede claro, observe que $$\{3,4,...,n\}->\{2,4,...,n\},$$ así que $$3->2$$ o $$n->2.$$

Caso 1: $$n->2.$$ Entonces $$n-1->4$$$$ 3->5 $$$$n-2->6$$$$ 4->7 $$$$n-3->8$$$$ 5->9...$$ así que sólo hay una respuesta posible.

Caso 2: $$3->2. $$ Entonces $$4->4.$$ $$\{5,...,n\}->\{5,...,n\}$$ y $$5->5$$ o $$5->6.$$ Esto es lo mismo que $$\{1,...,n-4\}->\{1,...,n-4\}$$ y $$1->1$$ o $$1->2.$$ Así que por inducción obtenemos $$2*(n-5)$$ respuestas.

En total, esta parte es $$2n-9.$$

---

por lo que la respuesta total es $$f_n=2+2+2+3+5+7+...+(2n-9)=(n-3)(n-5)+6=n^2-8n+21$$

Esto es válido para $$n>4$$