$\mathfrak{S}_n$ is amazing (part 1)

Let $\hat{w}$ denote $\phi_{n}(w)$ . For this problem in $\mathfrak{S}_n$ , the claim in that the number of permutations that are left unchanged by $\phi_n$ is $F_{n+1}$ or the n+1st Fibonacci number. Since Fibonacci numbers obey a nice recurrence relation, an easy way to approach this problem is to simply show that this is obeyed using induction.

First, let $w = (C_1)(C_2) \cdots (C_l)$ . Divide this into two cases: $|C_l|=1, |C_l|\neq 1$ . If the size of $C_l$ is one, then since this is the last cycle it must be larger than all other elements of $w$ - that is, it must be $n$ . For this first case, we have an unchanged permutation every time $(C_1) \cdots (C_{l-1})=w'\in \mathfrak{S}_{n-1}$ is fixed, and there are $F_n$ ways to do this by the induction hypothesis.

For the other case, we have $C_l = (n, \cdots k)$ . Note that $\hat{w}(n)=w(n)=k$ , meaning that $C_l$ is a 2-cycle of the form $(n,k)$ . But we also have $w(k)$ is $n$ and since we know exactly where $n$ is we see $k=n-1$ . In the same way as the last case, we get $F_{n-1}$ ways.

Now simply verify the first few cases to see that the relationship is in fact true.

---

Alternative solution : Suppose that $w=(C_1)(C_2)\cdots(C_l)$ has $|C_i|\le 2$ . It is not difficult to see that the two conditions on the standard form force the every cycle to contain the actual indices it covers in $\hat{w}$ : for example if $|C_1|=2$ then $C_1=(21)$ . When we go from cycle notation to the permutation, no change occurs because 1-cycles simply map to themselves and so do 2-cycles. This means that this class of permutations remains unchanged by $\phi_n$ .

Suppose that there was a cycle $C= (w_i, \cdots w_j)$ over the indices $i \cdots j$ in some $\hat{w}=w$ of size greater than two. We know that $w_k$ is at index $w_{k-1}$ (this is cyclic) from $\hat{w}=w$ , and what this tells us is that since $w_i$ is the largest $w_{i+1}$ is at the largest index. This implies $|C|\le 2$ , a contradiction.

Using the above, the only viable class of permutation is those with 1 or 2-cycles. This is a well known problem, and has a solution of $F_{n+1}$ .