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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Tobias Kildetoft Mar 14 '13 at 15:01


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{{}}$.


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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.