3
$\begingroup$

I am trying to find the number of cyclic permutations ,$A(n)$, 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!

1 Answers 1

5

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.

  • 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.2011-04-25