El número de permutaciones corregidas por la transformación fundamental es Fibonacci

Question

La escritura de una permutación en $S_n$ como producto de ciclos disjuntos, se define un estándar de representación por escrito de cada ciclo con su elemento más grande la primera, y la orden de los ciclos de la orden creciente de su elemento más grande. Luego hay un mapa de $\hat{}: S_n \rightarrow S_n$ que tiene una permutación $w\mapsto \hat w$, la eliminación de todos los w paréntesis. Si imponemos el estándar de la representación anterior, este es un bijection.

Lo que me piden demostrar es que el número de permutaciones izquierda fija por este bijection es la (n+1)st número Fibonacci. Este es un problema de Stanley Combinatoria Enumerativa en el caso de que alguien se está preguntando. Ahora mismo sólo estoy mirando muy fijamente tratando de averiguar cómo acercarse a este. Incluso estoy un poco confundido en cuanto a lo de "izquierda fija" significa. Es sólo la de permutaciones sin paréntesis a quitar?

Answer 1

Ejemplo

Considere la posibilidad de la permutación $\sigma = [1 3 2]\in S_3$ (que es $1\mapsto 1$, $2\mapsto 3$, $3\mapsto 2$). En el estándar de representación introdujo en el ejercicio, $\sigma = (1)(3,2)$. Ahora $\hat{\sigma} = [1 3 2] = \sigma$, lo $\sigma$ se fija en $\hat{{}}$.

Solución

Deje $A(n)$ el número de permutaciones en $S_n$. Vemos que $A_1 = 1$$A_2 = 2$, es decir, en $S_1$$S_2$, todos los permutationes son fijos.

Ahora vamos a $n \geq 3$. Deje $\pi\in S_n$ se fija en virtud de la transformación. Considerar el mayor número de $n$. En el estándar de representación, $n$ es el primer elemento del último ciclo. Si el último ciclo tiene una longitud de $1$ (es decir, tiene la forma (n), que es un punto fijo), a continuación, $\pi$ es fijo si y sólo si después de quitar el ciclo de $(n)$, el resultado es una permutación es fijo en $S_{n-1}$.

Ahora suponga que el último ciclo de $\pi$ $(n,\ldots,a)$ de la longitud de la $\geq 2$. A continuación,$\hat{\pi}(n) = a$. Así también se $\pi(n) = a$, lo que implica que el último ciclo se $(n,a)$. Ahora$\pi(a) = n$$\hat{\pi}(n-1) = n$, lo que implica $a = n-1$. Así que el último ciclo de la forma $(n-1, n)$. Vemos que $\pi = \hat{\pi}$ si y sólo si después de quitar el último ciclo, el resultado de permutación se fija en $S_{n-2}$.

Por lo $A(n) = A(n-1) + A(n-2)$. Por lo tanto $A(n)$ se adhiere a la misma fórmula de recursión como los números de Fibonacci F(n). Porque de $A(1) = 1$, $A(2) = 2$ y $F(2) = 1$, $F(3) = 2$, llegamos $A(n) = F(n+1)$.