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 Santos Apr 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.

  • 2
    $\begingroup$ Why do you need such a thing? $\endgroup$ – Mariano Suárez-Álvarez Jan 12 '13 at 7:23
  • $\begingroup$ @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 :) ) $\endgroup$ – Anvit Tawar Jun 19 '13 at 9:04
  • $\begingroup$ This question has been re-asked, and an answer is given at the new question. $\endgroup$ – 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?

  • $\begingroup$ 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.) $\endgroup$ – Mike Spivey Jan 13 '13 at 22:04
  • $\begingroup$ Sounds good. Thanks :) $\endgroup$ – Anvit Tawar Feb 17 '13 at 17:28
  • $\begingroup$ @Anvit: You’re welcome. $\endgroup$ – Brian M. Scott Feb 18 '13 at 3:38
  • $\begingroup$ 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. $\endgroup$ – Will Orrick Sep 9 '13 at 12:41
  • 1
    $\begingroup$ @WillOrrick hmm you are right, something is funny here, your interpretation was probably intended but has double counting, interesting... $\endgroup$ – Evan Sep 10 '13 at 16:30

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