Number of Permutations Fixed by the Fundamental Transformation is Fibonacci

Writing a permutation in $S_n$ as a product of disjoint cycles, we define a standard representation by writing each cycle with its largest element first, and ordering the cycles by the increasing order of their largest element. Then there's a map $\hat{}: S_n \rightarrow S_n$ that takes a permutation $w\mapsto \hat w$, deleting all of w's parentheses. If we impose the standard representation above, this is a bijection.

What I'm asked to show is that the number of permutations left fixed by this bijection is the (n+1)st Fibonacci number. This is a problem from Stanley's Enumerative Combinatorics in case anyone is wondering. Right now I'm just staring pretty blankly trying to figure out how to approach this. I'm even a little confused as to what "left fixed" means. Is it just the permutations with no parentheses to remove?

• By left fixed, he means those permutations that are not changed by removing their parenthesis like this. All the permutations will have at least one pair of parentheses to remove. – Tobias Kildetoft Mar 14 '13 at 15:01

Example

Consider the permutation $\sigma = [1 3 2]\in S_3$ (which is $1\mapsto 1$, $2\mapsto 3$, $3\mapsto 2$). In the standard representation introduced in the exercise, $\sigma = (1)(3,2)$. Now $\hat{\sigma} = [1 3 2] = \sigma$, so $\sigma$ is fixed under $\hat{{}}$.

Solution

Let $A(n)$ be the number of fixed permutations in $S_n$. We see that $A_1 = 1$ and $A_2 = 2$, i.e. in $S_1$ and $S_2$, all permutationes are fixed.

Now let $n \geq 3$. Let $\pi\in S_n$ be fixed under the transformation. Consider the largest number $n$. In the standard representation, $n$ is the first element of the last cycle. If the last cycle has length $1$ (i.e. it has the form (n), which is a fixed point), then $\pi$ is fixed if and only if after removing the cycle $(n)$, the resulting permutation is fixed in $S_{n-1}$.

Now assume the last cycle of $\pi$ is $(n,\ldots,a)$ of length $\geq 2$. Then $\hat{\pi}(n) = a$. So also $\pi(n) = a$, which implies that the last cycle is $(n,a)$. Now $\pi(a) = n$ and $\hat{\pi}(n-1) = n$, which implies $a = n-1$. So the last cycle has the form $(n-1, n)$. We see that $\pi = \hat{\pi}$ if and only if after removing the last cycle, the resulting permutation is fixed in $S_{n-2}$.

So $A(n) = A(n-1) + A(n-2)$. Thus $A(n)$ adheres to the same recursion formula as the Fibonacci numbers F(n). Because of $A(1) = 1$, $A(2) = 2$ and $F(2) = 1$, $F(3) = 2$, we get $A(n) = F(n+1)$.