Bijective proof of a combinatorial recurrence This question is inspired by one asked yesterday.  What is the number of cyclic permutations of $[n]$ with no number followed by it's successor?  ($1$ is counted as the successor of $n$.)  Matthew Daly noticed that the answer is given by A000757 where the recurrence $$
a_n = (n-2)a_{n-1} + (n-1)a_{n-2} - (-1)^n,\ n>0
$$ is given.  The OEIS page gives a reference to a derivation of the exponential generating function, from which I imagine it's easy to prove the recurrence, but I've been looking for a bijective proof, and getting nowhere.
I know that $a_5=8$:
13254
13524
13542
14253
14352
15243
15324
15432

and that $a_4=1$:
1432

and $a_3=1$:
132

I've been playing around with these, trying to find a way to construct the solution for $n=5$ for the solutions from $n=4$ and $n=3$, but I haven't been able to come close.  In going from $n-1$ to $n$, I said you can insert the $n$ in an admissible permutation of length $n-1$, after any number but $n-1$ and any place but at the end.  That only gives $n-3$ permutations, not $n-2$, and I haven't any good ideas about how to go from a permulation of length $n-2$ to one of length $n$.
Can you give a proof or suggestions?   
 A: Based on Mike Earnest's simplification of the recurrence, it is not hard to see the classes that one needs to break the "good" permutations into to get a bijection. It will be helpful to define a couple of functions:


*

*$d:S_n \rightarrow S_{n-1}$: delete $n$ from a permutation

*$c:S_n \rightarrow S_{n-1}$: given a permutation that has a successor pair $k,k+1$, replace the subsequence $k,k+1$ with $k$, and decrement every permutation element greater than $k$ by 1


With these functions, we have the following classes:


*

*Good permutations $\pi$ of $S_n$ such that $d(\pi)$ is a good permutation of $S_{n-1}$: Starting with any of the $a_{n-1}$ good permutations in $S_{n-1}$, once can insert $n$ after any element except $n-1$ and the last element, which is not $n-1$ since the starting permutation is good. Hence there are $(n-3)a_{n-1}$ permutations of this form.

*Good permutations $\pi$ of $S_n$, such that $d(\pi)$ has a single successor pair and does not end in $n-1$: Note that if $d(\pi)$ has a single successor pair, then $c(d(\pi))$ is a good permutation in $S_{n-2}$, since $c$ eliminates the successor pair and the last element of the permutation is not $n-2$. Note that any good permutation of $S_{n-2}$, of which there are $a_{n-2}$, is the image of exactly $n-2$ permutations in $S_{n-1}$ under $c$, and that each of these $n-2$ permutations gives rise to a single good permutation of $S_n$ by inserting $n$ between the single successor pair. Hence there are $(n-2)a_{n-2}$ permutations of this class.

*Good permutations $\pi$ of $S_n$ that end in $n-1$, but $d(\pi)$ has no successor pair other than $n-1,1$: Since $d(\pi)$ has no successor pair, we know $n-2$ does not precede $n-1$, hence $d(d(\pi))$ is a good permutation in $S_{n-2}$. Given such a good permutation of $S_{n-2}$, we can place $n-1$ at the end uniquely, and then there are $n-2$ locations (any except the end) to place $n$ to obtain a good permutation of $S_n$. Hence there are $(n-2)a_{n-2}$ permutations of this class.

*Good permutations $\pi$ of $S_n$ that end in $n-1$, and $d(\pi)$ has an additional successor pair that is not $n-2,n-1$: For a permutation in this class, if we remove both $n$ and $n-1$, we obtain a permutation of $S_{n-2}$ that has a single successor pair, and the last element is not $n-2$. So much like in case 2, $c(d(d(\pi)))$ is a good permutation of $S_{n-3}$. Starting with a good permutation of $S_{n-3}$, of which there are $a_{n-3}$, it is the image of $n-3$ permutations of $S_{n-2}$ with a single successor pair, with last element not $n-2$. Adding $n-1$ to the end and inserting $n$ between the successor pair yields a good permutation of $S_n$ in this class. Hence there are $(n-3)a_{n-3}$ permutations of this class.

*Good permutations $\pi$ of $S_n$ that end in $n-1$, and $d(\pi)$ has the additional successor pair $n-2,n-1$: In this case, $\pi$ must have as its last three elements $n-2,n,n-1$, and the first $n-3$ elements form a good permutation of $S_{n-3}$. Hence there are $a_{n-3}$ such permutations.


Adding all of these up yields Mike Earnest's recurrence.
