Tell me more ×
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.
up vote 2 down vote favorite

I am trying to find the number of cyclic permutations (An) of {1,2,3,...,n} without any two consecutive integers together. The second part of the problem is to prove that A(n+1)+A(n)=D(n) [derangement numbers]

Any help on how to start this would be appreciated!

share|improve this question

1 Answer

up vote 4 down vote

Note that the derangement numbers have no simple closed form. If the equation is true, then you cannot hope for a simple form for $A(n)$.

Therefore, you can try to prove a recurrence relation. What do you get if you take out $n$ of a cyclic permutation? (You will need to regard two different cases)

Compare the recurrence relation with the recurrence relation for the derangement numbers and prove it by induction.

share|improve this answer
I don't get "...take out n of a cyclic permutation". Are you saying consider a cyclic permutation on $[n]$ and ignore the $n$ to get a new one on $[n-1]$? – Mitch Apr 25 '11 at 21:49
1  
Yes, but this does not always give a cyclic permutation on $n-1$, so you have to regard the case where it does and the case where it does not. – Phira Apr 25 '11 at 22:52

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.