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
up vote 2 down vote accepted

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.

  • 1
    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

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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