<s>[INST] 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?
 [/INST] 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.
</s>