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?
 A: 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)$.
