[Math] The Number of Permutation Consists of Odd Length of Cycles.

combinatoricsexponential functiongenerating-functions

I would like to find an explicit formula for the number of permutations $\sigma \in \sum_n $ in which every cycle has odd length.

First I had found following links and get EGF for this counting:

$$
E(z)=\exp(\sum_{k\geq 0}\frac{z^{2k+1}}{2k+1})$$ (referenced to here https://math.stackexchange.com/posts/1163681/edit)

So I had looked up the Wikipedia page regarding EGFs, such that introduced the concept as following :

"Exponential generating function (EGF) is $$EG(a,n\mid x) =\sum_0^\infty a_n{x^n\over n!}$$
EGFs are generally more convenient than ordinary generating functions for combinatorial enumeration problems that involve labelled objects."


My question here:

1) What is the labelled object? I want to understand this concept so to track how the $E(z)$ has developed from the format of EGF(I don't think it's a definition).

2) This EGF has form of exponential function, which is different from ordinary one. How could I draw out explicit formula from this EGF for the specific case of given n?

Best Answer

This is a long story, hard to tell succinctly. Try reading the beginning of Analytic Combinatorics by Flajolet and Sedgewick or Combinatorial Species and Tree-like Structures by Bergeron, Labelle, and Leroux. One way or another you'll arrive at a substantially more general result, which is a version of what's called the "exponential formula," and which concisely expresses in generating function form the decomposition of a permutation into cycles; see, for example, this blog post. This formula asserts that

$$\exp \left( \sum_{k \ge 1} z_k \frac{t^k}{k} \right) = \sum_{n \ge 0} \left( \sum_{\pi \in S_n} \prod_{i=1}^n z_i^{c_i(\pi)} \right) \frac{t^n}{n!}$$

where $c_i(\pi)$ denotes the number of cycles of length $i$. You can learn a lot of things from this generating function by substituting things for the $z_k$. For example, it follows that the EGF of permutations whose cycle lengths are constrained to lie in some subset $S \subseteq \mathbb{N}$ is

$$\exp \left( \sum_{k \in S} \frac{t^k}{k} \right)$$

which is already a substantial generalization of your claim. But there is even more information hidden in this generating function; for example, it implies that the distribution of the number of $i$-cycles in a random permutation of size $n$, as $n \to \infty$, approaches a Poisson distribution with mean $\frac{1}{i}$.

In any case, the generating function you're interested in can be written somewhat more explicitly as follows. Note that $\sum_{k \ge 1} \frac{t^k}{k} = \log \left( \frac{1}{1 - t} \right)$. We can isolate the odd terms using the general fact that if $f(t)$ is a power series then its odd terms are given by $\frac{f(t) - f(-t)}{2}$, hence we want

$$\sum_{k \ge 0} \frac{t^{2k+1}}{2k+1} = \frac{1}{2} \left( \log \left( \frac{1}{1 - t} \right) - \log \left( \frac{1}{1 + t} \right) \right) = \frac{1}{2} \log \frac{1 + t}{1 - t}$$

and exponentiating both sides gives

$$\boxed{ O(t) = \exp \left( \sum_{k \ge 0} \frac{t^{2k+1}}{2k+1} \right) = \sqrt{ \frac{1 + t}{1 - t} } }.$$

From here we can extract a closed formula for the number $o_n$ of permutations with odd cycles as follows. First let's consider the analogous problem for permutations consisting of only even cycles; this corresponds to adding rather than subtracting to isolate even terms which gives

$$\boxed{ E(t) = \exp \left( \sum_{k \ge 1} \frac{t^{2k}}{2k} \right) = \frac{1}{\sqrt{1 - t^2}} }$$

and so, using the identity $\frac{1}{\sqrt{1 - 4t}} = \sum_{n \ge 0} {2n \choose n} t^n$, we conclude that the number $e_n$ of permutations of $n$ elements with only even cycles satisfies

$$\boxed{ e_{2k} = \frac{(2k)!}{2^{2k}} {2k \choose k} = \left( \frac{(2k)!}{2^k k!} \right)^2 = (2k-1)!!^2 }$$

where $(2k-1)!! = (2k-1)(2k-3) \dots 1$, and of course $e_{2k+1} = 0$. $e_{2k}$ is A001818 on the OEIS.

Now we can observe that we can rewrite $O(t)$ as

$$\sqrt{ \frac{1 + t}{1 - t} } = \frac{1 + t}{\sqrt{1 - t^2}} = (1 + t) E(t)$$

which gives that $o_{2k} = e_{2k}$ and $o_{2k+1} = (2k+1) e_{2k}$; that is,

$$\boxed{ o_{2k} = (2k-1)!!^2 }$$

and

$$\boxed{ o_{2k+1} = (2k+1) (2k-1)!!^2 }.$$

This is A000246 on the OEIS.

Related Question