2
$\begingroup$

I need to find - as a homework problem - the exponential generating function for the number of permutations of $n$ consisting of an even number of odd-length cycles. I can retrieve the exponential generating function for the number of permutations with just odd-length cycles, by $$ E(z)=\exp(\sum_{k\geq 0}\frac{z^{2k+1}}{2k+1})=\exp(\sum_{k\geq 1}\frac{z^{k}}{k})/\exp(\sum_{k\geq 1}\frac{z^{2k}}{2k})=\frac{1}{1-z}(\sqrt{1-z^2})=\sqrt{\frac{1+z}{1-z}}. $$ Since $n$ has permutations of an even number of odd-length cycles if and only if it is even, in which case all permutations with odd-length cycles have an even number of cycles, I believe that I have to find the power series obtained by $E(z)$ by just selecting the terms in $z^n$ with $n$ even. Is this correct? In any case, I don't know how to proceed.

$\endgroup$
2
$\begingroup$

There are two possible interpretations here, the first, permutations consisting of an even number of odd cycles and some even cycles and second, permutations consisting of an even number of odd cycles only.

First interpretation. Observe that the generating function of permutations with odd cycles marked is $$G(z, u) = \exp\left(\sum_{k\ge 1} \frac{z^{2k}}{2k} + u \sum_{k\ge 0}\frac{z^{2k+1}}{2k+1}\right).$$ This is $$G(z, u) = \exp\left((1-u)\sum_{k\ge 1} \frac{z^{2k}}{2k} + u \sum_{k\ge 1}\frac{z^{k}}{k}\right).$$

To get the permutations with an even number of odd cycles use $$\frac{1}{2} G(z,1)+\frac{1}{2} G(z, -1)$$ which yields $$\frac{1}{2}\exp\left(\sum_{k\ge 1}\frac{z^{k}}{k}\right) + \frac{1}{2} \exp\left(2\sum_{k\ge 1} \frac{z^{2k}}{2k} - \sum_{k\ge 1}\frac{z^{k}}{k}\right).$$

This simplifies to $$\frac{1}{2} \frac{1}{1-z} + \frac{1}{2} (1-z) \frac{1}{1-z^2}$$ which is $$\frac{1}{2} \frac{1}{1-z} + \frac{1}{2} \frac{1}{1+z}.$$

This simply says that when $n$ is even then there must be an even number of odd cycles and when $n$ is odd there cannot be an even number of odd cycles, which follows by inspection (parity).

Second interpretation. Here we have $$G(z, u) = \exp\left(u \sum_{k\ge 0}\frac{z^{2k+1}}{2k+1}\right).$$ This is $$G(z, u) = \exp\left(u \sum_{k\ge 0}\frac{z^{k}}{k} - u \sum_{k\ge 1}\frac{z^{2k}}{2k}\right).$$ To get the permutations with an even number of odd cycles use $$\frac{1}{2} G(z,1)+\frac{1}{2} G(z, -1)$$ which yields $$\frac{1}{2}\frac{1}{1-z} \left(\frac{1}{1-z^2}\right)^{-1/2} + \frac{1}{2} (1-z) \left(\frac{1}{1-z^2}\right)^{1/2}.$$

This gives the sequence $$0, 1, 0, 9, 0, 225, 0, 11025, 0, 893025, 0, 108056025, 0, 18261468225,\ldots$$ which points us to OEIS A177145, where we find this computation confirmed.

This generating function maybe written as $$\frac{1}{2}\frac{1}{1-z} \sqrt{1-z^2} + \frac{1}{2} (1-z) \frac{1}{\sqrt{1-z^2}}$$ or $$\frac{1}{2}\sqrt{\frac{1+z}{1-z}} + \frac{1}{2}\sqrt{\frac{1-z}{1+z}}.$$

$\endgroup$
  • $\begingroup$ Thanks but I'm afraid I don't get the point. The right interpretation is "permutations consisting of an even number of odd-length cycles only". Is $u$ a variable standing for the sign of the permutation? And where does the formula $\frac{1}{2}(G(z,1)+G(z,-1))$ come from? Is my result above wrong? $\endgroup$ – user212361 Feb 24 '15 at 21:40
  • $\begingroup$ A term $u^k z^n/n!$ in $G(z, u)$ represents a permutation on $n$ items consisting of $k$ odd cycles. Now observe what happens when we set $u$ to one and to minus one, add the two terms, and divide by two. That should produce the necessary insight. $\endgroup$ – Marko Riedel Feb 24 '15 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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