# Bijection between derangements and good permutations

A good permutation is a permutation of the numbers 1 to n, such that i is not followed by i+1 at any position in the permutation, for any i in {1,2,..,n-1}. Call the number of such permutations S(n). Also, D(n) is the number of derangements of {1,2,..,n}.

I am required to show that S(n) = D(n) + D(n-1).

Note that an algebraic solution is possible, but I need a combinatorial argument i.e. by showing bijections between the two sets.

-
Why do you need such a thing? – Mariano Suárez-Alvarez Jan 12 '13 at 7:23
@MarianoSuárez-Alvarez Bijective/Combinatorial Proofs of identities like these usually give more insights into the problem at hand, compared to an algebraic solution. I, of course, need this for a homework ;) (Rest assured though, I gave it enough thought posting here :) ) – Anvit Tawar Jun 19 '13 at 9:04
This question has been re-asked, and an answer is given at the new question. – Will Orrick Oct 5 '13 at 15:23

This does not in fact work; see the comments. Then see the answers to this question.

HINT: Let $\pi=\pi_1\pi_2\dots\pi_n$ be a permutation of $[n]=\{1,\dots,n\}$. Define a map

$$\hat\pi:[n]\to[n]:\pi_k\mapsto\begin{cases} \pi_{k+1}-1,&\text{if }k<n\text{ and }\pi_{k+1}\ne 1\\ \pi_1-1,&\text{if }k=n\text{ and }\pi_1\ne 1\\ n,&\text{otherwise}\;; \end{cases}$$

$\hat\pi$ is a permutation of $[n]$, and in fact the map $\pi\mapsto\hat\pi$ is a bijection on $S_n$, the set of permutations of $[n]$.

Suppose that $\pi$ is good. Then $\hat\pi$ has no fixed point in $[n-1]=\{1,\dots,n-1\}$. Can you fill in the details and finish it from there?

-
I may be mistaken, Brian, but I think the rest of it is the harder part. (Of course, the OP hasn't responded to your hint, either.) – Mike Spivey Jan 13 '13 at 22:04
Sounds good. Thanks :) – Anvit Tawar Feb 17 '13 at 17:28
@Anvit: You’re welcome. – Brian M. Scott Feb 18 '13 at 3:38
I'm not sure whether my understanding is correct, but it looks like all cyclic permutations of $\pi_1\pi_2\ldots\pi_n$ have the same image under this map. For example, $132$ and $213$ would both map to $231.$ In other words, the map seems to depend only on the relative, rather than absolute, positions of the elements of $\pi.$ Please let me know if I've gone wrong somewhere. – Will Orrick Sep 9 '13 at 12:41
@WillOrrick hmm you are right, something is funny here, your interpretation was probably intended but has double counting, interesting... – Evan Sep 10 '13 at 16:30