Ordinary partitions vs partitions into odd parts

Question

Let $\mathcal{P}(n)$ be the set of all unrestricted partitions of $n$ while $\mathcal{O}(n)$ stand for the set of all partitions of $n$ into odd parts. We adopt the power notation for partitions $\lambda$ as $1^{m_1}2^{m_2}\cdots n^{m_n}$ with $\ell(\lambda)$ the length of $\lambda$.

Let $B_n$ denote the Bell numbers $$\sum_{n\geq0}B_n\frac{x^n}{n!}=e^{e^x-1}.$$

QUESTION. Is this true? $$\sum_{\lambda\in\mathcal{O}(n)}\frac{2^{\ell(\lambda)}B_{\ell(\lambda)}}{1^{m_1}3^{m_3}\cdots m_1!m_3!\cdots} =\sum_{\mu\in\mathcal{P}(n)}\frac{2^{\ell(\mu)}}{m_1!m_2!m_3!\cdots}.$$

Answer 1

The g.f. for the right-hand is $$e^{2x}\cdot e^{2x^2} \cdots = e^{2\frac{x}{1-x}}.$$

---

For the left-hand side, additionally introducing variable $y$ to account for partition length, we get $$\sum_{n\geq 0} x^n \sum_{\lambda\in\mathcal{O}(n)} \frac{(2y)^{\ell(\lambda)}}{1^{m_1}3^{m_3}\cdots m_1!m_3!\cdots} = e^{2y\frac{x}1}\cdot e^{2y\frac{x^3}3} \cdots = e^{y\log\frac{1+x}{1-x}}.$$ Then the g.f. for the left-hand side is $$\sum_{k\geq 0} B_k\cdot [y^k]\ e^{y\log\frac{1+x}{1-x}} = \sum_{k\geq 0} B_k\cdot\frac{\left(\log\frac{1+x}{1-x}\right)^k}{k!} = e^{\frac{1-x}{1-x}-1} = e^{2\frac{x}{1-x}}.$$ QED

Answer 2

Yes, they are the same. It is more convenient to write this in terms of compositions instead of partitions. Writing $\mathcal{OC}(n)$ for the set of compositions of $n$ with odd parts, the LHS is $$\sum_{\alpha \in \mathcal{OC}(n)} \frac{2^{\ell(\alpha)} B_{\ell(\alpha)}}{\ell(\alpha)!\prod_i \alpha_i}.$$ We apply the usual "snake oil" technique of multiplying by $t^n$, summing over all $n$, and then moving the sum over $k = \ell(\alpha)$ to the outside. This gives $$\begin{aligned} \sum_{n \ge 0}\left(\sum_{\alpha \in \mathcal{OC}(n)} \frac{2^{\ell(\alpha)} B_{\ell(\alpha)}}{\ell(\alpha)!\prod_i \alpha_i}\right)t^n &= \sum_{k \ge 0} \frac{2^kB_k}{k!} \left(\sum_{j \ge 0} \frac{t^{2j+1}}{2j+1}\right)^k \\ &= \sum_{k \ge 0} \frac{B_k}{k!} \left(\log \frac{1+t}{1-t}\right)^k \\ &= \exp\left(\frac{1+t}{1-t} - 1\right) \\ &= \exp \frac{2t}{1-t}. \end{aligned}$$

Similarly, the RHS written in terms of compositions is $$\sum_{\alpha \vDash n} \frac{2^{\ell(\alpha)}}{\ell(\alpha)!}$$ and applying the same method gives $$\begin{aligned} \sum_{n \ge 0}\left(\sum_{\alpha \vDash n} \frac{2^{\ell(\alpha)}}{\ell(\alpha)!}\right)t^n &= \sum_{k \ge 0} \frac{2^k}{k!} \left(\sum_{j \ge 1} t^j\right)^k \\ &= \sum_{k \ge 0} \frac{2^k}{k!} \left(\frac{t}{1-t}\right)^k \\ &= \exp \frac{2t}{1-t} \end{aligned}$$ as wanted.

Answer 3

For what it worth, here is a combinatorial proof.

We start with a known

Lemma 1. Let $m$ be an even positive integer. Then the number of permutations of $[m]$ with only odd cycles equals to the number of permutations of $[m]$ with only even cycles.

See the discussion of this fact, including bijective proof, here, for example.

Lemma 1 yields the following

Lemma 2. Let $n$ be a positive integer. Consider all permutations of $[n]$ with only odd cycles, and color each cycle in white or black. The number of such colored objects equals $2n!$

Proof. Let $C$ denote the cycle containing $1$. Partition all our objects onto pairs in which the permutations are the same, the colorings of cycles except $C$ are the same, and the colorings of $C$ are different. In each pair, exactly one object is admissible in the following sense: the total number of black cycles is even.Thus, it suffices to prove that the number of admissible objects equals $n!$. Lemma 1 suggests a bijection between permutations and admissible objects: take a permutation, color all odd cycles white, replace even cycles to odd cycles bijectively by Lemma 1 (preserving the union of the cycles which we change) and color them black.

Now we see that $n!$ times LHS equals to the number of the following stories: take a permutation of $[n]$ with only odd cycles, color each cycle in white or black, and partition the cycles onto non-empty blocks (we use the combinatorial meaning of Bell number $B_k$ as the numbers of set partitions of a $k$-set.) Applying Lemma 2 to each block, we see that $n!$ times LHS is the number of the following fairytales: partition $[n]$ onto blocks, in each block take a permutation and color this block white or black. If we now denote by $m_i$ the number of blocks of size $i$ ($i=1,2,\ldots$) and by $\ell$ the number of blocks, I claim that the corresponding fairytales are enumerated by the number $n! 2^\ell/\prod m_i!$. (If proven, this clearly completes the proof). As for $2^\ell$, this corresponds to coloring the blocks. So, forget the colors of blocks and forget this multiple. Then we need to prove that the number $T$ of ways to partition $[n]$ onto blocks and in each block take a permutation so that we have $m_i$ blocks of size $i$ equals to $n!/\prod m_i!$. In other words, $T\prod m_i!$ must be equal to $n!$. Well, $T\prod m_i!$ differs from $T$ by choosing enumerations of the blocks of the same size $i$, for every $i=1,2,\ldots$. It equals $n!$ by the following simple bijection: take a permutation $(\pi_1,\pi_2,\ldots,\pi_n)$ and partition this row of $n$ numbers reading it from left to right onto blocks of size 1 ($m_1$ times), then of size 2 ($m_2$ times) etc, enumerated naturally.