# cyclic permutations without consecutive integers?

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!

-

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)
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
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