I am looking to show that the number of permutations on $n$ objects such that there are an even number of cycles, all with odd length, is equal to
$${n \choose {n/2}}\frac{n!}{2^n}$$
if $n$ is even and $0$ otherwise
In my search about how to go about this problem, I have found a number of sites describing the difference between an odd and an even permutation (odd: number of even length cycles is odd, even: number of even length cycles is even). However, I am not sure how to go about it for odd length cycles.
Any thoughts?
Best Answer
Combinatorial class
Using combinatorial classes we have the following class $\mathcal{P}$ of permutations with all cycles of odd length: $$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{P} = \textsc{SET}( \textsc{CYC}_{=1}(\mathcal{Z}) + \textsc{CYC}_{=3}(\mathcal{Z}) + \textsc{CYC}_{=5}(\mathcal{Z}) + \cdots).$$This gives the EGF
$$G(z) = \exp\left(z+\frac{z^3}{3} + \frac{z^5}{5} + \cdots\right) \\ = \exp\left(\log\frac{1}{1-z} - \frac{1}{2} \log\frac{1}{1-z^2}\right) \\ = \frac{1}{1-z} \sqrt{1-z^2}.$$
Recurrence
Now we have
$$G'(z) = G(z) \frac{1}{1-z} - G(z) \frac{z}{1-z^2} \\ = \frac{1}{2} G(z) \frac{1}{1-z} + \frac{1}{2} G(z) \frac{1}{1+z}.$$
Extracting coefficients we get a recurrence for $G_n = [z^n] G(z)$ where the desired quantity is $n! \times G_n$ and $G_0 = G_1 = 1$
$$[z^n] G'(z) = (n+1) G_{n+1} = \frac{1}{2} \sum_{q=0}^n G_q + \frac{1}{2} \sum_{q=0}^n G_q (-1)^{n-q}$$
We also have
$$(n+3) G_{n+3} = \frac{1}{2} \sum_{q=0}^{n+2} G_q + \frac{1}{2} \sum_{q=0}^{n+2} G_q (-1)^{n-q}$$
which yields
$$(n+3) G_{n+3} - (n+1) G_{n+1} = \frac{1}{2} (G_{n+1} + G_{n+2}) + \frac{1}{2} ( - G_{n+1} + G_{n+2} )$$
so that
$$(n+3) G_{n+3} = G_{n+2} + (n+1) G_{n+1}.$$
Induction proof of closed form
We now claim that for $n\ge 0$ we have
$$G_{n+1} = \frac{1}{2^n} {n\choose \lfloor n/2\rfloor}.$$
We will prove this by induction. We have two consecutive base cases for $n=0$ and $n=1$ which go through, being confirmed combinatorially. Now if $n=2m$ we need to verify that
$$(2m+3) \frac{1}{2^{2m+2}} {2m+2\choose m+1} = \frac{1}{2^{2m+1}} {2m+1\choose m} + (2m+1) \frac{1}{2^{2m}} {2m\choose m}.$$
Multiply by $(m+1)!^2$ to get
$$(2m+3)!/2^{2m+2} = (m+1) (2m+1)!/2^{2m+1} + (m+1)^2 (2m+1)!/2^{2m}$$
Now we have $(2m+3)(2m+2) = 2(m+1)+4(m+1)^2$ so this holds. Next when $n=2m+1$ we need
$$(2m+4)\frac{1}{2^{2m+3}} {2m+3\choose m+1} = \frac{1}{2^{2m+2}} {2m+2\choose m+1} + (2m+2) \frac{1}{2^{2m+1}} {2m+1\choose m}.$$
Multiply by $(m+1)! (m+2)!$ to get
$$(2m+4)!/2^{2m+3} = (m+2) (2m+2)!/2^{2m+2} + (m+1) (m+2) (2m+2)!/2^{2m+1}$$
This time we have $(2m+4)(2m+3) = 2(m+2) + 4(m+1)(m+2)$ so this holds as well. This completes the induction proof.
Conclusion
Keeping in mind that we seek $n!\times G_n$ we have shown the closed form for $n\ge 1$
$$\bbox[5px,border:2px solid #00A000]{ \frac{n!}{2^{n-1}} {n-1\choose \lfloor (n-1)/2 \rfloor}.}$$
This yields the sequence
$$1, 1, 3, 9, 45, 225, 1575, 11025, 99225, 893025, \ldots$$
which points us to OEIS A000246, where a variety of additional material awaits.
Remark
As regards how we interpret the question, we say that the permutation must consist of an even number of cycles, all of which are odd. This is only possible for $n$ even. (Moreover if there are only odd cycles there must be an even number of them.) In that case the the closed form will produce $$\frac{n!}{2^{n-1}} {n-1\choose n/2-1} = \frac{n!}{2^{n-1}} \frac{n/2}{n} {n\choose n/2} = \frac{n!}{2^n} {n\choose n/2}$$ as proposed by OP. We get zero for $n$ odd, again as proposed by OP. Here the above boxed formula gives the number of permutations consisting of an odd number of odd cycles.