# Derangements property

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$

• I think there is a formula for calculating dearrangements. – Manoj Pandey Mar 31 '13 at 13:27
• You can find them on oeis.org/… – 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

$$D_1(n+1)=n\Big(D_1(n)+D_1(n-1)+n-2\Big)\tag{1}$$

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

$$D_0(n+1)=n\Big(D_0(n)+D_0(n-1)-n+2\Big)\tag{2}$$

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

$$D_0(n)-D_1(n)=n-1\;,$$

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

• 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. – Voyage Mar 31 '13 at 18:45
• @Voyage: It took me a while to figure out a way to get them; see the addition to my answer. – 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.

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