It is not difficult to evaluate a formula for the number of derangements, with a simple combinatorical argument we get $D(n)=(n-1)(D(n-1)+D(n-2)), n\ge 3$ where $D(n)$ is the number of derangements.

Now I would like to synthesize the number of even and odd cycles, i.e $D_1(n)$ the number of derangements whose number of cycles is even and $D_0(n)$ be the number of derangements whose number is odd.

How is this possible because I think if we substract them we get $D_1(n)-D_0(n)=n-1$

  • $\begingroup$ I think there is a formula for calculating dearrangements. $\endgroup$ – Manoj Pandey Mar 31 '13 at 13:27
  • $\begingroup$ You can find them on oeis.org/… $\endgroup$ – Voyage Mar 31 '13 at 13:31

OEIS A216778 is the number of derangements of $n$ elements with an even number of cycles; OEIS A216779 is the number of derangements of $n$ elements with an odd number of cycles. Recurrences are given for both; in your notation


with initial values $D_1(0)=1$ and $D_1(1)=0$, and


with initial values $D_0(0)=D_0(1)=0$. These can also be expressed directly in terms of $D(n)$:

$$D_1(n)=\frac{D(n)-n+1}2\quad\text{and}\quad D_0(n)=\frac{D(n)+n-1}2\;.\tag{3}$$

Your conjecture has the wrong sign: it should be


as is easily proved by induction from $(1)$ and $(2)$ or directly from $(3)$.

The early data:

$$\begin{array}{rcc} n:&0&1&2&3&4&5&6&7&8&9\\ D_0(n):&0&0&1&2&6&24&135&930&7420&66752\\ D_1(n):&1&0&0&0&3&20&130&924&7413&66744\\ D_0(n)-D_1(n):&-1&0&1&2&3&4&5&6&7&8& \end{array}$$

Added: I don’t at the moment see how to derive $(1)$ and $(2)$ directly, but it’s clear that

$$D_1(n+1)=nD_1(n)+nD_0(n-1)\quad\text{and}\quad D_0(n+1)=nD_0(n)+nD_1(n-1)\;:\tag{4}$$ in each of these recurrences the first term counts the number of derangements of $[n+1]$ in which $n+1$ is not in a $2$-cycle, and the second term counts the rest. From these it’s easy to prove by induction that $D_0(n)-D_1(n)=n-1$, and combining this with $(4)$ yields $(1)$ and $(2)$.

  • $\begingroup$ Thanks, but could you explain me the recurrences for $D_1(n+1)$ and $D_0(n+1)$, I do not see right now how to derive them. $\endgroup$ – Voyage Mar 31 '13 at 18:45
  • $\begingroup$ @Voyage: It took me a while to figure out a way to get them; see the addition to my answer. $\endgroup$ – Brian M. Scott Mar 31 '13 at 19:06

These can be calculated with exponential generating functions. Let me change the notation so that $D_0(n)$ is the number of derangements whose number of cycles is even and $D_1(n)$ the number whose number of cycles is odd, so that the subscript on $D$ indicates the parity. The EGF of the set of derangements by the number of cycles is $$ G(z, u) = \exp\left( - u z + u \log \frac{1}{1-z} \right) = \exp(-uz) \left( \frac{1}{1-z} \right)^u.$$ Now add $1/2 \times G(z, -1)$ and $1/2 \times G(z, 1)$ to obtain the EGF $Q(z)$ of $D_0(n),$ getting $$ Q(z) = \frac{1}{2} \exp(-z) \frac{1}{1-z} + \frac{1}{2} \exp(z) (1-z).$$ We thus have $$ D_0(n) = n! [z^n] Q(z) = \frac{1}{2} n! \sum_{k=0}^n \frac{(-1)^k}{k!} + \frac{1}{2} n! \frac{1}{n!} - \frac{1}{2} n! \frac{1}{(n-1)!} \\= \frac{1}{2} n! \sum_{k=0}^n \frac{(-1)^k}{k!} + \frac{1}{2} (1-n) \sim \frac{1}{2e} n! + \frac{1}{2} (1-n).$$ There is more information at the OEIS.

Of course since the number of derangements $D(n)$ is $$D(n)= n! \sum_{k=0}^n \frac{(-1)^k}{k!}, $$ we get $$D_1(n) = \frac{1}{2} n! \sum_{k=0}^n \frac{(-1)^k}{k!} - \frac{1}{2} (1-n)$$ and the difference is indeed $n-1$ as pointed out in the OP.

  • 1
    $\begingroup$ Except that the OP got the sign wrong on the difference, perhaps owing to the poor choice of subscripts. $\endgroup$ – Brian M. Scott Mar 31 '13 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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