Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

1 Answer 1

up vote 2 down vote accepted

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?

share|improve this answer
    
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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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