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?

  • $\begingroup$ 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)$. $\endgroup$ Aug 13, 2018 at 16:01
  • $\begingroup$ 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? $\endgroup$ Aug 13, 2018 at 16:55
  • $\begingroup$ @GeoffRobinson: that's true, but I'm not sure how it is related to my question. $\endgroup$ Aug 13, 2018 at 17:10
  • $\begingroup$ Can you double check conjecture 2? It doesn't seem to give the right values for $P_k$. $\endgroup$ Aug 14, 2018 at 1:40
  • $\begingroup$ @GjergjiZaimi: does it look right now? $\endgroup$ Aug 14, 2018 at 1:53

2 Answers 2


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.

  • 1
    $\begingroup$ Awesome! This looks great! $\endgroup$ Aug 16, 2018 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.