Cycle generating function of permutations with only odd cycles

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?

• Note that we can analogously define $\mathrm{EVEN}(2m)$ to be the permutations in $\mathfrak{S}_{2m}$ with only even cycles, and then $\mathcal{C}_{\mathrm{EVEN}}(2m,t)=(2m-1)!!\cdot t (t+2)(t+4)\cdots(t+2(m-1))$. This is much simpler than $\mathcal{C}_{\mathrm{ODD}}(n,t)$. – Sam Hopkins Aug 13 '18 at 16:01
• I don't know if it helps, but isn't it well known that the number of partitions of $n$ with all parts odd is equal to the number of partitions of $n$ with no repeated part? – Geoff Robinson Aug 13 '18 at 16:55
• @GeoffRobinson: that's true, but I'm not sure how it is related to my question. – Sam Hopkins Aug 13 '18 at 17:10
• Can you double check conjecture 2? It doesn't seem to give the right values for $P_k$. – Gjergji Zaimi Aug 14 '18 at 1:40
• @GjergjiZaimi: does it look right now? – Sam Hopkins Aug 14 '18 at 1:53

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.

• Awesome! This looks great! – Sam Hopkins Aug 16 '18 at 16:35

Conjecture 2 follows from setting $t=2k$ in the formula $$\sum_{n\geq 0}\mathcal{C}_{\mathrm{ODD}}(n,t)\cdot\frac{z^n}{n!} =\left(\frac{\sqrt{1-z^2}}{1-z}\right)^t.$$ It then follows easily that $$\sum_{j\geq 0}P_k(j)x^j = \frac{(2k-1)!!\,x(1+x)^{k-1}}{(1-x)^{k+1}}.\ \qquad (1)$$ By Theorem 3.2 of http://math.mit.edu/~rstan/papers/cycles.pdf we see that all the zeros of $P_k(x)$ are purely imaginary, which implies that $P_k(x)$ has nonnegative coefficients and is either even or odd, depending on the parity of $k$. Clearly also from (1) $P_k(0)=0$. I don't see immediately from (1) why $P_k(x)$ has integer coefficients.

Let me also remark that the polynomial $(P_k(x)+P_k(x+1))/(2k-1)!!$ is the Ehrhart polynomial of the standard $k$-dimensional cross-polytope. See Exercise 4.61 of Enumerative Combinatorics, vol. 1, second edition.

• Very interesting comment about the cross-polytope. But is it the $h^*$-polynomial or just the usual Ehrhart polynomial? – Sam Hopkins Aug 14 '18 at 3:25
• And it seems this Ehrhart polynomial should be $(P_k(x)+P_k(x+1))/(2k-1)!!$ – Sam Hopkins Aug 14 '18 at 3:54
• @SamHopkins: Thanks, this is corrected. – Richard Stanley Aug 14 '18 at 19:11