Let $\mathrm{ODD}(n)$ be the set of permutations in $\mathfrak{S}\_n$ whose cycle lengths are all odd. It is known that
$$ \#\mathrm{ODD}(n) = \begin{cases} ((n-1)!!)^2 &\textrm{ if $n$ is even}; \\ n\cdot((n-2)!!)^2 &\textrm{ if $n$ is odd}. \end{cases}$$


Set $\mathcal{C}\_{\mathrm{ODD}}(n,t) = \sum\_{\pi \in \mathrm{ODD}(n)} t^{\kappa(\pi)}$, where $\kappa(\pi)$ is the number of cycles of $\pi \in \mathfrak{S}\_n$.


Then it is easy to show that
$$ \sum\_{n\geq0}\mathcal{C}\_{\mathrm{ODD}}(n,t) \cdot \frac{z^n}{n!} = \left(\frac{\sqrt{1-z^2}}{1-z}\right)^t$$
From this one can show that
$$ \mathcal{C}\_{\mathrm{ODD}}(n,t)= \sum\_{i=0}^{\lfloor n/2\rfloor}\frac{1}{2^i\cdot i!}\prod\_{j=0}^{n-1-2i}(t+j)\prod\_{k=0}^{i-1}(t-2k)(n-2k)(n-2k-1)$$
In particular if we set $t:=2k$ to be an even integer, then
$$ \mathcal{C}\_{\mathrm{ODD}}(n,2k)=\frac{(n-1)!}{(2k-1)!} \cdot \sum\_{j=0}^{k}(-1)^j\binom{k}{j}\prod\_{i=0}^{k-j-1}(n+2i)(n+2i+1)\prod\_{i=0}^{j-1}(n-2i)(n-2i-1)$$
Thus, for example $\mathcal{C}\_{\mathrm{ODD}}(n,2)=2\cdot n!$ and $\mathcal{C}\_{\mathrm{ODD}}(n,4)=4n\cdot n!$.


Define the polynomial $P\_k(x)$ by setting
$$ \mathcal{C}\_{\mathrm{ODD}}(n,2k) = \frac{(n-1)!\cdot k! \cdot 2^k}{(2k-1)!}\cdot P\_k(n)$$


For example,


* $P\_1(x)=x$;
* $P\_2(x)=3x^2$;
* $P\_3(x)=10x^3+5x$;
* $P\_4(x)=35x^4+70x^2$;
* $P\_5(x)=7\cdot 3^2(2x^5+10x^3+3x)$;
* $P\_6(x)=3\cdot 7\cdot 11(2x^6+20x^4+23x^2)$;
* et cetera


**Conjecture 1**: $P\_k(x)$ is a polynomial of degree $k$ with nonnegative integer coefficients, with zero constant term, and which is odd if $k$ is odd and even if $k$ is even.


**Conjecture 2**: We have,
$$ \sum\_{k \geq 0} \frac{P\_k(x)}{(2k-1)!!} \cdot z^k = \frac{1}{2}\cdot\left( \frac{1+z}{1-z}\right)^x$$
(The constant term on the RHS is $1/2$ so take whatever convention for $P\_0(x)$ or $(-1)!!$ for that to work.)


With regard to Conjecture 2, note that from the above we have
$$ \sum\_{n\geq0}\mathcal{C}\_{\mathrm{ODD}}(n,2k) \cdot \frac{z^n}{n!} = \left(\frac{1+z}{1-z}\right)^k$$


**Question**: Are these conjectures correct? Are these cycle generating functions studied somewhere?



Cycle generating function of permutations with only odd cycles
I'll start by addressing conjecture 2. By summing your generating fun over all values of $k$ we obtain
$$F(z,w)=\sum\_{n\geq 0}\sum\_{k\geq 0}C\_{\text{ODD}}(n,2k)\frac{z^n}{n!}w^k=\sum\_{k\geq 0}w^k\left(\frac{1+z}{1-z}\right)^k=\frac{1-z}{1-w-z-wz}$$
From here we see that
$$\sum\_{n\geq 1}\sum\_{k\geq 1}\frac{P\_k(n)}{(2k-1)!!}w^k \frac{z^{n-1}}{(n-1)!}=\frac{1}{2}\frac{d}{dz}\int\left(F(z,w)-1\right)dw$$
$$=\int \frac{w}{(1-w)^2}\frac{1}{\left(1-z(\frac{1+w}{1-w})\right)^2}dw$$
By extracting the coefficients of $z^{n-1}/(n-1)!$ on both sides we have
$$\sum\_{k\geq 0}\frac{P\_k(n)}{(2k-1)!!}w^k=\int \frac{nw}{(1-w)^2}\left(\frac{1+w}{1-w}\right)^{n-1} dw=\frac{1}{2}\left(\frac{1+w}{1-w}\right)^n+\text{constant}$$
which is what we wanted. 




---


I just realized that we can also answer conjecture 1 by making use of this identity. Start with the expansion
$$\left(\frac{1+w}{1-w}\right)^n=\left(1+\frac{2w}{1-w}\right)^n=1+\sum\_{r\geq 1} \binom{n}{r}\left(\frac{2w}{1-w}\right)^r$$
$$=1+\sum\_{k\geq 1}w^k\sum\_{r\geq 1}2^r\binom{n}{r}\binom{k-1}{r-1}$$
which gives us an explicit formula for $P\_k$
$$P\_k(n)=\sum\_{r\geq 1}2^{r-1}(2k-1)!!\binom{n}{r}\binom{k-1}{r-1}$$
Which immediately tells us that $P\_k(n)$, as a linear combination of $\binom{n}{r}$ for $1\le r\le k$, is a polynomial of degree $k$ with no constant term. Combined with the fact that $\left(\frac{1+w}{1-w}\right)^n=\left(\frac{1-w}{1+w}\right)^{-n}$ we have $P\_k(n)=(-1)^kP\_k(-n)$ which tells us that $P\_k$ has the same parity as $k$. Now it remains to establish integrality of the coefficients. The explicit formula for $P\_k$ can be rearranged as
$$P\_k(n)=\sum\_{r\geq 1}\binom{k+r-1}{r,r-1,k-r}\frac{(2k-1)!}{2^{k-r}(k+r-1)!}(n)\_r$$
and from here it is clear that the coefficients of $P\_k$ have nonnegative $p$-adic valuation for any odd prime $p$. It remains to show the following lemma


**Lemma:** For any $k\geq r\geq 1$ we have
$$\nu\_2\left(\frac{(2k-1)!}{r!(r-1)!(k-r)!}\right)\geq k-r.$$
**Proof** We make use of the fact that $\nu\_2\left(\frac{s!}{\lfloor\frac{s}{2}\rfloor!}\right)=\lfloor\frac{s}{2}\rfloor$. Our expression can be written as
$$\nu\_2\left(\frac{(2k-1)!}{r!(r-1)!(k-r)!}\right)=\nu\_2 \left(\frac{(2k-1)!}{(k-1)!}\frac{\lfloor\frac{r}{2}\rfloor!\lfloor\frac{r-1}{2}\rfloor!}{r!(r-1)!}\right)+\nu\_2\left(\binom{k-1}{\lfloor\frac{r}{2}\rfloor,\lfloor\frac{r-1}{2}\rfloor,k-r}\right)$$
the first term is equal to $k-1-\lfloor\frac{r}{2}\rfloor-\lfloor\frac{r-1}{2}\rfloor=k-r$ and the second term is clearly nonnegative. This completes the proof of integrality.


