# Can we count odd and even derangements nicely without taking a determinant?

It's not hard to see that $$\det \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$$ is equal to

#(even derangements on 3 elements) - #(odd derangements on 3 elements)

and similarly for larger n. It's not hard to calculate this determinant by various methods, and together with the known expression for the total number of derangements on n elements this results in explicit expressions for the number of odd and even derangements on n elements.

Question: Is there any nice and fundamentally different way of getting at the numbers of odd an even derangements?

My motivation is that this would then provide an alternate method of calculating the determinant. See:

Matrix with zeros on diagonal and ones in other places is invertible

which is the original motivation, goes over a few simple ways to calculate the determinant, and includes a full explanation of the identity I claim above.

• I think the given det is minus what you say. – posilon Jun 5 '15 at 10:42
• Fixed, thanks @posilon. – Daniel McLaury Jun 5 '15 at 10:43
• Robin Chapman: An involution on derangements, doi: 10.1016/S0012-365X(00)00310-1. Abstract: "We give a bijective proof that the number of even and odd derangements in $S_n$ differs by $n-1$." This paper is also cited in the 2nd edition of Bona: Combinatorics of Permutation. So these two sources might be worth looking at. – Martin Sleziak Jun 5 '15 at 12:10
• Mike Spivey's answer here mentions another paper with a combinatorial proof, authored by Benjamin, Bennett, and Newberger. – Martin Sleziak Jun 5 '15 at 13:33
• @MartinSleziak: The existing answers based on generating functions are good, but if I had an answer mentioning a bijective proof that would be the one I would accept. – Daniel McLaury Jun 5 '15 at 20:36

Daniel McLaury indicated in his comment that he is mostly interesting for bijective proofs. For this reason I have decided to post the two references I have mentioned in my comments above in this answer. I think the answer collecting references for combinatorial proofs about this fact might be useful for other users as well. I made this answer CW, feel free to add further references

## References

### Proofs using generating functions

Have you thought about using the cycle index generating function? It is defined as $$Z(x_1,\cdots,x_n,\cdots)=\sum_{w\in S_n} \prod_{i=1}^{\infty}x_i^{\#\text{cycles of } w \text{ of length } i}$$

Now, it is known (for instance by the Fundamental theorem of exponential generating functions (egf)'s as is described here) that $$\sum_{n=0}^{\infty} Z(x_1,\cdots,x_n,\cdots)\frac{t^n}{n!}=\operatorname{exp}(\frac{tx_1}{1}+\frac{t^2x_2}{2}+\cdots)$$

This formula is particularly useful for enumerating classes of permutations that can be characterized in terms of their cycle structure! In this case, for instance, setting $x_1=0$ and $x_i=1$ would enumerate all permutations with no cycle of length one, that is, with no fixed points, i.e. all derangements. If we want to take sign into account we just set $x_i=(-)^{i-1}$, since a cycle of length $i$ can be writtn as a product of $i-1$ transpositions.

Therefore, the exponential generating function for even - odd derangemens is $$\sum Z_n(0,-1,1,-1,1,\cdots)\frac{t^n}{n!}=\operatorname{exp}(-\frac{-t^2}{2}+\frac{t^3}{3}+\frac{-t^4}{4}+\cdots)$$

The right hand side is then written as $$\operatorname{exp}(-t+\operatorname{log}(1+t))=\frac{1+t}{e^t}$$ and extracting the coefficient of $t^n$ from that gives us exactly $$\#\text{even}-\text{odd derrangements}= (-1)^{n-1}(n-1)$$

Too long for a comment (I upvoted the first answer). I would like to point out that we don't need the cycle indices of the symmetric group here as we are working in a labeled universe where only the order of the group counts rather than the cycle structure of its elements.

We get the following species equation for derangements with a variable marking the sum of the cycle lengths minus one, giving the sign. $$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{=2}(\mathcal{Z}) + \mathcal{U}^2\mathfrak{C}_{=3}(\mathcal{Z}) + \mathcal{U}^3\mathfrak{C}_{=4}(\mathcal{Z}) + \mathcal{U}^4\mathfrak{C}_{=5}(\mathcal{Z}) +\cdots).$$

This immediately gives the generating function $$G(z,u) =\exp\left(\sum_{q\ge 2} u^{q-1} \frac{z^q}{q}\right) = \exp\left(\frac{1}{u}\sum_{q\ge 2} u^{q} \frac{z^q}{q}\right) = \exp\left(-z +\frac{1}{u}\sum_{q\ge 1} u^{q} \frac{z^q}{q}\right) \\ = \exp\left(-z +\frac{1}{u}\log\frac{1}{1-uz}\right).$$

Now the even derangements have generating function $$\frac{1}{2} (G(z,1)+G(z,-1))$$ and the odd ones $$\frac{1}{2} (G(z,1)-G(z,-1))$$ the difference being $$G(z,-1)$$ which is $$\exp\left(-z -\log\frac{1}{1+z}\right) = (1+z)\exp(-z).$$

Extracting coefficients we have $$n! [z^n] G(z, -1) = n! \frac{(-1)^n}{n!} + n! \frac{(-1)^{n-1}}{(n-1)!} \\= (-1)^n + (-1)^{n-1} n = (-1)^{n-1} (n-1).$$

• Can you point me to a reference for the notation you used in the first displayed equation? I can kind of infer what it means from context, but I've never even seen some of those symbols before. – Daniel McLaury Jun 5 '15 at 20:25
• There is this: Wikipedia I and more importantly this: Wikipedia II. – Marko Riedel Jun 5 '15 at 20:30

Perhaps this is not what you are looking for, but we can simplify the computation of the determinant to a $1\times1$ determinant, which is as close to not-a-determinant as a determinant gets.

In this answer, it is shown that $$\det(\lambda I_n-AB)=\lambda^{n-m}\det(\lambda I_m-BA)$$ Using $\lambda=1$, $m=1$, $A=\left.\begin{bmatrix}1\\1\\1\\\vdots\\1\end{bmatrix}\right\}$${\scriptsize n\text{ tall}}, and B=\underbrace{\begin{bmatrix}1&1&1&\cdots&1\end{bmatrix}}_{\text{n wide}}, we get$$ (-1)^n\det\underbrace{\begin{bmatrix} 0&1&1&\cdots&1\\ 1&0&1&\cdots&1\\ 1&1&0&\cdots&1\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&1&1&\cdots&0 \end{bmatrix}}_{n\times n} =\det(I_n-AB)=\det\underbrace{(1-BA)}_{1\times1}=1-n $$Therefore,$$ \det\underbrace{\begin{bmatrix} 0&1&1&\cdots&1\\ 1&0&1&\cdots&1\\ 1&1&0&\cdots&1\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&1&1&\cdots&0 \end{bmatrix}}_{n\times n} =(-1)^{n-1}(n-1)$\$