Number of cycles of all even permutations of $[n]$ and number of cycles of all odd permutations differ by $(-1)^n (n-2)!$

Here is an argument completely different from joriki’s; it is also a complete solution.

A cycle is an odd permutation iff its length is even, so a permutation written as a product of disjoint cycles is even iff an even number of the factors are even cycles. Let $\pi=\sigma_1\dots\sigma_k$ be a permutation of $[n]$ written as a product of $k$ disjoint cycles. Then $n=|\,\sigma_1|+\dots+|\,\sigma_k|$, so the parity of $n$ is the same as the parity of the number of cycles of odd length. Thus, $\pi$ has an even number of cycles of even length iff $n$ and $k$ have the same parity, i.e., iff $(-1)^{n+k}=1$.

Let $e_n$ be the total number of cycles in even permutations of $[n]$, let $o_n$ be the total number of cycles in odd permutations of $[n]$, and let $d_n=e_n-o_n$. The total number of permutations of $[n]$ with $k$ cycles is given by $\left[n\atop k\right]$, the unsigned Stirling number of the first kind. Each of these $\left[n\atop k\right]$ permutations contributes $k$ cycles to $e_n$ if $(-1)^{n+k}=1$, and to $o_n$ if $(-1)^{n+k}=(-1)$. Thus, each contributes $(-1)^{n-k}k$ to $d_n$, and it follows that

$$d_n=\sum_k(-1)^{n+k}k\left[n\atop k\right]\;.$$

Now $(-1)^{n+k}\left[n\atop k\right]=(-1)^{n-k}\left[n\atop k\right]$ is the signed Stirling number of the first kind, for which we have the generating function $$\sum_k(-1)^{n+k}\left[n\atop k\right]x^k=x^{\underline{n}}\;.\tag{1}$$

(Here $x^{\underline{n}}=x(x-1)(x-2)\cdots(x-n+1)$ is the falling factorial, sometimes written $(x)_n$.)

Differentiate $(1)$ with respect to $x$ to obtain

$$\sum_k(-1)^{n+k}k\left[n\atop k\right]x^{k-1}=Dx^{\underline{n}}=(x-n+1)Dx^{\underline{n-1}}+x^{\underline{n-1}}\;,$$

where the last step is simply the product rule, since $x^{\underline{n}}=x^{\underline{n-1}}(x-n+1)$. But $$Dx^{\underline{n-1}}=\sum_k(-1)^{n-1+k}k\left[{n-1}\atop k\right]x^{k-1}\;,$$ so

$$\sum_k(-1)^{n+k}k\left[n\atop k\right]x^{k-1}=\sum_k(-1)^{n-1+k}k\left[{n-1}\atop k\right]x^{k-1}+x^{\underline{n-1}}\;.\tag{2}$$

Now evaluate $(2)$ at $x=1$ to get $$d_n=(2-n)d_{n-1}+[n=1]\;,\tag{3}$$ where the last term is an Iverson bracket. If we set $d_0=0$, $(3)$ yields $d_1=[1=1]=1$, which by direct calculation is the correct value: the only permutation of $[1]$ is the identity, which is even and has one cycle. It’s now a trivial induction to check that $d_n=(-1)^n(n-2)!$ for all $n\ge 1$: the induction step is

$$\begin{align*}d_{n+1}&=\Big(2-(n+1)\Big)d_n\\ &=(1-n)(-1)^n(n-2)!\\ &=(-1)^{n+1}(n-1)!\;. \end{align*}$$

Added: It occurs to me that there’s a rather easy argument that does not use generating functions. Let $\sigma$ be any $k$-cycle formed from elements of $[n]$; then $\sigma$ is a factor in $(n-k)!$ permutations of $[n]$. Moreover, exactly half of these permutations are even unless $n-k$ is $0$ or $1$. Thus, $\sigma$ contributes to $d_n$ iff $k=n$ or $k=n-1$.

There are $(n-1)!$ $n$-cycles; they are even permutations iff $n$ is odd, so they contribute $(-1)^{n-1}(n-1)!$ to $d_n$.

There are $n(n-2)!$ $(n-1)$-cycles: there are $n$ ways to choose the element of $n$ that is not part of the $(n-1)$-cycle, and the other $n-1$ elements can be arranged in $(n-2)!$ distinct $(n-1)$-cycles. The resulting permutation of $[n]$ is even iff $n-1$ is odd, i.e., iff $n$ is even, so they contribute $(-1)^nn(n-2)!$ to $d_n$.

It follows that $$\begin{align*}d_n&=(-1)^nn(n-2)!+(-1)^{n-1}(n-1)!\\ &=(-1)^n\Big(n(n-2)!-(n-1)!\Big)\\ &=(-1)^n(n-2)!\Big(n-(n-1)\Big)\\ &=(-1)^n(n-2)!\;. \end{align*}$$

Warning: This is a complete solution; you may want to read only a part of it to get you on the right track and then see if you can complete it.

The number of permutations of $[n]$ is $n!$, so the exponential generating function for the number of permutations is

$$\sum_{n=0}^\infty x^n=\frac1{1-x}\;.$$

The number of cycles containing all elements of $[n]$ is $(n-1)!$, so the exponential generating function for the number of cycles is

$$\sum_{n=1}^\infty \frac1nx^n=-\log(1-x)\;.$$

The exponential generating function for the number of ordered tuples of $k$ cycles together containing all elements of $[n]$ is therefore $(-\log(1-x))^k$.

The number of permutations of $[n]$ with $k$ cycles is the number of unordered tuples of $k$ cycles together containing all elements of $[n]$, so we have to divide by a factor of $k!$ for the number of permutations of the cycles; so the exponential generating function for the number of permutations of $[n]$ with $k$ cycles is $(-\log(1-x))^k/k!$. We can check this result by summing over $k$ to regain

$$\sum_{k=0}^\infty\frac{(-\log(1-x))^k}{k!}=\mathrm e^{-\log(1-x)}=\frac1{1-x}\;.$$

Now we just have to include a sign for the parity of the permutations. A permutation of $[n]$ with $k$ cycles has parity $(-1)^{k+n}$. To test the approach, let's first calculate the excess of the even permutations over the odd permutations, without counting the cycles. Including the factor $(-1)^k$ in the coefficients yields

$$\sum_{k=0}^\infty(-1)^k\frac{(-\log(1-x))^k}{k!}=\mathrm e^{\log(1-x)}=1-x\;,$$

and then taking into account the factor $(-1)^n$ yields the expected result, namely that the excess is $1$ for $n=0$ and $n=1$ and $0$ otherwise.

Now to count the total number of cycles we just have to include a factor $k$ in the sum:

$$ \begin{eqnarray} \sum_{k=0}^\infty(-1)^kk\frac{(-\log(1-x))^k}{k! } &=& \sum_{k=1}^\infty(-1)^k\frac{(-\log(1-x))^k}{(k-1)!} \\ &=& (1-x)\log(1-x) \\ &=& -x+\sum_{n=2}^\infty\frac{x^n}{n(n-1)} \\ &=& -x+\sum_{n=2}(n-2)!\frac{x^n}{n!}\;, \end{eqnarray} $$

and then taking into account the factor $(-1)^n$ from the parity yields the desired result for $n\ge2$.

P.S.: I just realized the factor $(-1)^n$ could have been dealt with a bit more elegantly by including it right from the start and writing $1+x$ everywhere instead of $1-x$.

Added: Brian's easier proof without generating functions made me wonder whether there's also an easier proof by induction. There is: Consider the cycle structures of all permutations of $[n]$, and add $n+1$ to each of them in all possible ways. For each cycle structure, there are $n$ ways of adding $n+1$ to one of the cycles and $1$ way of adding it as a cycle of its own.

If we add it as a cycle of its own, the parity is unchanged. Since there are equal numbers of permutations of both parities, the new cycle doesn't contribute to the result; the other cycles contribute the same excess as they did for $n$, namely $(-1)^n(n-2)!$ by the induction hypothesis.

On the other hand, if we add $n+1$ to one of the cycles, the parity changes while the number of cycles stays the same. Since there are $n$ ways of doing this for each cycle, this yields a contribution of $-n(-1)^n(n-2)!$. The total is therefore $(1-n)(-1)^n(n-2)!=(-1)^{n+1}((n+1)-2)!$.

Here is a solution that has the advantage of brevity. Start by observing that the sign of a permutation $\pi$ is given by $$\sigma(\pi) = \prod_{c\in\pi} (-1)^{|c|-1}$$ where the product is over all cycles $c$ of $\pi.$

Recall that the unmarked species of permutations by the number of cycles is given by $$\mathfrak{P}(\mathfrak{C}(\mathcal{Z})).$$

If we want to include the signs of these permutations we need to mark cycles with a variable $\mathcal{U}$ whose exponent indicates the cycle length minus one. This gives the modified species

$$\mathfrak{P}(\mathfrak{C}_{=1}(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_{=2}(\mathcal{Z}) + \mathcal{U}^2\mathfrak{C}_{=3}(\mathcal{Z}) + \mathcal{U}^3\mathfrak{C}_{=4}(\mathcal{Z}) + \cdots.)$$

We also want the cycle count so we mark all cycles with the variable $\mathcal{V},$ finally getting the species $$\mathfrak{P}(\mathcal{V}\mathfrak{C}_{=1}(\mathcal{Z}) + \mathcal{V}\mathcal{U}\mathfrak{C}_{=2}(\mathcal{Z}) + \mathcal{V}\mathcal{U}^2\mathfrak{C}_{=3}(\mathcal{Z}) + \mathcal{V}\mathcal{U}^3\mathfrak{C}_{=4}(\mathcal{Z}) + \cdots.)$$

Switching to generating functions we obtain the generating function $G(z, u, v)$ where $$G(z, u, v) = \exp\left( vz + vu\frac{z^2}{2} + vu^2\frac{z^3}{3} + vu^3\frac{z^4}{4} + vu^4\frac{z^5}{5} + \cdots \right).$$ This is $$G(z, u, v) = \exp \left(\frac{v}{u}\left( uz + u^2 \frac{z^2}{2} + u^3 \frac{z^3}{3} + u^4 \frac{z^4}{4} + u^5 \frac{z^5}{5} + \cdots \right) \right)$$ which finally gives $$G(z, u, v) = \exp \left( \frac{v}{u} \log \frac{1}{1-uz} \right).$$ Now to obtain the total cycle count differentiate by $v$ and set $v=1$ to get $$H(z, u) = \left.\frac{d}{dv} G(z, u, v)\right|_{v=1} = \left.\exp \left( \frac{v}{u} \log \frac{1}{1-uz} \right) \left( \frac{1}{u} \log \frac{1}{1-uz} \right)\right|_{v=1} \\ = \exp \left( \frac{1}{u} \log \frac{1}{1-uz} \right) \left( \frac{1}{u} \log \frac{1}{1-uz} \right).$$ Observe that $$\frac{1}{2} H(z, 1) + \frac{1}{2} H(z, -1)$$ gives the contribution from even permutations and $$\frac{1}{2} H(z, 1) - \frac{1}{2} H(z, -1)$$ from odd ones, so that $$H(z, -1)$$ yields the difference we want to compute. Setting $u=-1$ we obtain $$H(z, -1) = \exp \left( - \log \frac{1}{1+z} \right) \left( - \log \frac{1}{1+z} \right) \\=\left( -\log \frac{1}{1+z} \right) \exp\left(\log(1+z)\right) = -(1+z)\log\frac{1}{1+z}.$$

To conclude it remains to extract coefficients from this exponential generating function, and we get $$n! [z^n] H(z, -1) = - n! [z^n] (1+z)\log\frac{1}{1+z} = - n! \left(\frac{(-1)^n}{n} + \frac{(-1)^{n-1}}{n-1}\right) \\= - (-1)^n \times n! \times \left(\frac{1}{n}-\frac{1}{n-1}\right) = (-1)^{n+1} \times n! \times \frac{-1}{n(n-1)} \\= (-1)^n \times (n-2)!.$$

Nice page I have to say.

Important note. I just noticed that the above is a duplicate. I solved the same problem a little less than a year ago using the same method and the link to it can be found under "linked" in the right side bar.