# Bijection between derangements and good permutations [duplicate]

This question already has an answer here:

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 \left\{1,2,\ldots,n-1\right\}$$. Call the number of such permutations $$S(n)$$.

Also, $$D(n)$$ is the number of derangements of $$\left\{1,2,\ldots,n\right\}$$.

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.

## marked as duplicate by darij grinberg, Eevee Trainer, callculus, Lord Shark the Unknown, José Carlos SantosApr 3 at 7:38

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• Why do you need such a thing? – Mariano Suárez-Álvarez 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

## 1 Answer

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