Number of cycles of all even permutations of $[n]$ and number of cycles of all odd permutations differ by $(-1)^n (n-2)!$ I'm trying to solve task 44 of the first chapter of Stanleys Enumerative Combinatorics (found here).

Show that the total number of cycles of all even permutations of $[n]$ and the
  total number of cycles of all odd permutations of $[n]$ differ by $(−1)^n (n − 2)!$. Use generating functions.

I might be completely off the track here, but the way I thought of this problem is the following. A permutation can be written as a product of disjoint cycles, and a permutation is odd iff there is an odd number of even-length cycles.
The set of cycles partition $[n]$ into disjoint orbits, and thus the number of cycles of all odd permutations of $[n]$ should be equal to the number of partitions of $[n]$ into even parts, with an odd number of such parts (and similarly for the even permutations).
Is this right or have I misunderstood something? Also, I'm not quite sure how to proceed from here and how to set up the generating functions.
I did find this question, which might be of some use if my interpretation of this problem is correct.
However, I did not clearly see how one could end up with $(-1)^n (n-2)!$ from that.
Any help would be greatly appreciated :)
 A: 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*}$$
A: 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)!$.
A: 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.
