Difference of number of cycles of even and odd permutations Show that the difference of the number of cycles of even and odd permutations is $(-1)^n (n-2)!$, using a bijective mapping (combinatorial proof).
Suppose to convert a permutation from odd to even we always flip 1 and 2. Then the difference can be easily calculated.
Thus, if I can find the number of cycles of all even permutations of $[n]$ that have $\{1,2\}$ in the same cycle., I can compute the difference. Can somebody show me a way?
 A: This isn’t quite a bijective proof in the usual sense, since one of the quantities involved can be negative. However, it uses a bijection to reduce the problem to a very simple counting problem, so I think that it qualifies. I’ve left the final step to you.
Let $$E_n=\{\langle\pi,\sigma\rangle:\pi\text{ is an even permutation of }n\text{ and }\sigma\text{ is a cycle of }\pi\}$$ and $$O_n=\{\langle\pi,\sigma\rangle:\pi\text{ is an odd permutation of }n\text{ and }\sigma\text{ is a cycle of }\pi\}\;;$$ we want to show that $|E_n|-|O_n|=(-1)^n(n-2)!$.
Let $E_n^*=\{\langle\pi,\sigma\rangle\in E_n:|\sigma|\le n-2\}$ and $O_n^*=\{\langle\pi,\sigma\rangle\in O_n:|\sigma|\le n-2\}$. For any $p=\langle\pi,\sigma\rangle\in E_n^*\cup O_n^*$ let $i_p$ and $j_p$ be the two smallest elements of $[n]$ not in $\sigma$, and define
$$f_n\big(\langle\pi,\sigma\rangle\big)=\big\langle\pi(i_pj_p),\sigma\big\rangle\;.$$
then $f_n$ is an involution on $E_n^*\cup O_n^*$ mapping $E_n^*$ to $O_n^*$ (and vice versa), and $|E_n^*|=|O_n^*|$, so we need only show that $|E_n\setminus E_n^*|-|O_n\setminus O_n^*|=(-1)^n(n-2)!$. Let $E_n^{**}=E_n\setminus E_n^*$ and $O_n^{**}=O_n\setminus O_n^*$. 
The members of $E_n^{**}\cup O_n^{**}$ are the $\langle\pi,\sigma\rangle\in E_n\cup O_n$ such that $\sigma$ is an $n$-cycle or an $(n-1)$-cycle, and in each case we must have $\pi=\sigma$. Thus,
$$E_n^{**}\cup O_n^{**}=\{\langle\sigma,\sigma\rangle:\sigma\text{ is a cycle of length }n\text{ or }n-1\}\;.$$
Now just count the $n$-cycles and $(n-1)$-cycles, categorize them as even or odd, and do a little arithmetic, and you’ll find that indeed $|E_n^{**}|-|O_n^{**}|=(-1)^n(n-2)!$.
Added: I forgot to mention that this answer combines an idea from this answer of mine with a comment on that answer by joriki.
A: Here is an answer using generating functions that may interest you. Recall that the sign $\sigma(\pi)$ of a permutation $\pi$ is given by
$$\sigma(\pi) = \prod_{c\in\pi} (-1)^{|c|-1}$$
where the product ranges over the cycles $c$ from the disjoint cycle composition of $\pi$.
It follows that the combinatorial species $\mathcal{Q}$ that reflects the signs and the cycle count of the set of permutations is given by
$$\mathcal{Q} =
\mathfrak{P}(\mathcal{V}\mathfrak{C}_1(\mathcal{Z})
+\mathcal{U}\mathcal{V}\mathfrak{C}_2(\mathcal{Z}))
+\mathcal{U}^2\mathcal{V}\mathfrak{C}_3(\mathcal{Z})
+\mathcal{U}^3\mathcal{V}\mathfrak{C}_4(\mathcal{Z})
+\mathcal{U}^4\mathcal{V}\mathfrak{C}_5(\mathcal{Z})
+\cdots)$$
where we have used $\mathcal{U}$ to mark signs and $\mathcal{V}$ for the cycle count.
Translating to generating functions we have
$$Q(z, u, v) =
\exp\left(v\frac{z}{1} 
+ 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 simplifies to
$$Q(z,u,v) = \exp\left(\frac{v}{u}
\left(
\frac{zu}{1} 
+ \frac{z^2 u^2}{2} 
+ \frac{z^3 u^3}{3} 
+ \frac{z^4 u^4}{4} 
+ \frac{z^5 u^5}{5} 
+ \cdots
\right)\right) \\
= \exp\left(\frac{v}{u} \log \frac{1}{1-uz}\right)
= \left(\frac{1}{1-uz}\right)^{\frac{v}{u}}.$$
Now the two generating functions $Q_1(z, v)$ and $Q_2(z, v)$ of even and odd permutations by cycle count are given by
$$Q_1(z,v) = \frac{1}{2} Q(z,+1,v) + \frac{1}{2} Q(z,-1,v) =
\frac{1}{2}\left(\frac{1}{1-z}\right)^v
+\frac{1}{2}\left(\frac{1}{1+z}\right)^{-v}$$ and
$$Q_2(z,v) = \frac{1}{2} Q(z,+1,v) - \frac{1}{2} Q(z,-1,v) =
\frac{1}{2}\left(\frac{1}{1-z}\right)^v
-\frac{1}{2}\left(\frac{1}{1+z}\right)^{-v}.$$
We require the quantity
$$G(z, v) = \left.\frac{d}{dv} (Q_1(z,v)-Q_2(z,v))\right|_{v=1} \\=
\left.\frac{d}{dv} \left(\frac{1}{1+z}\right)^{-v}\right|_{v=1} =
- \left.\log \frac{1}{1+z} \left(\frac{1}{1+z}\right)^{-v}\right|_{v=1}
= -(1+z)\log \frac{1}{1+z}.$$
Finally extracting coeffcients from this generating function we obtain
$$- n! [z^n] (1+z)\log \frac{1}{1+z}
= - n! \left(\frac{(-1)^n}{n} + \frac{(-1)^{n-1}}{n-1}\right)
\\= - n! (-1)^{n-1} \left(-\frac{1}{n} + \frac{1}{n-1}\right)
= n! (-1)^n \frac{n-(n-1)}{n(n-1)}
\\= n! (-1)^n \frac{1}{n(n-1)} = (-1)^n (n-2)!$$
This concludes the proof. I do think this is rather pretty.
