permutación y desafío f(n)

Question

Supongamos que $f(n)$ sea el número de permutaciones del conjunto ${1,2,..,n}$ tal que para cada $ 1 \leq i \leq n$ que tenemos: $ | \pi(i)-i| \leq 1 $ . significado de $ \pi(i)$ es un elemento cuyo lugar $i$ de permutación. por ejemplo en permutación $<2,3,1>$ , $ \pi(1)=2$ .

cómo llegamos a $f(10)= 89$

Answer 1

¿Cómo consiguió $f(10)=4$ ? Para $f(2n)$ hay al menos $2^n$ permutaciones, ya que puede intercambiar cada par de vecinos en $123\cdots n$ .

Esto es inducción. Para $n=1$ , $f(1)=1$ , $f(2)=2$ . Observe que $f(n+1)=f(n)+f(n-1)$ si $\pi(n+1)=n+1$ hay $f(n)$ muchas permutaciones, si $\pi(n+1)=n$ entonces $\pi(n)=n+1$ y hay $f(n-2)$ tales permutaciones. No hay otras opciones, ya que el índice de $n+1$ no puede ser inferior a $n$ .

Esta es la recurrencia de Fibonacci, por lo que $f(n)=F_{n+1}$ donde $F_n$ es el $n$ número de Fibonacci. Entonces, como usted señala, $f(10)=89$ .