Derangements with even/odd cycles

Question

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$

Answer 1

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

Answer 2

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.