# Confusion about Generating Function of Restricted Partitions

I ran into some confusion answering this question.

The OP asked for the number of partitions of an integer into odd numbers greater than $1$, with the additional constraint that there are two different choices (or colors) for each integer (it might be that the OP asked for compositions, but even if, I would like to treat partitions now). Eg we have four possibilities to partition $8$, namely $5_{red}+3_{red}$, $5_{red} + 3_{blue}$, $5_{blue}+3_{red}$ and $5_{blue} + 3_{blue}$.

Looking into the standard reference (Analytic Combinatorics), I found that partitions may be defined via the multiset construction (page 29ff). There, one first takes a combinatorial class $\mathcal B$ and its generating function $B(z)$ and sets $\mathrm{MSET}(\mathcal B) = \prod_{n \ge 1} (1-z^n)^{-B_n}$.
We have $B(z) = \sum_{n \ge 1} 2 \cdot z^{ 2n+1}$ (there are two possibilities for each odd number greater $1$), and so the generating function we are looking for is $$P_1(z) = \prod_{n \ge 1} (1-z^{2n+1})^{-2}.$$ Yet this function produces wrong coefficients (already the coefficient of $z^6$ is $3$, which is clearly wrong). A different function which I derived in an earlier attempt, $$P_2(z) = \prod_{n \ge 1} (1-2z^{2n+1})^{-1},$$ produces the right coefficients. So I guess $P_2(z)$ must be the right generating function, yet I don't clearly understand why. Also I don't know what exactly $P_1(z)$ counts. Did I misunderstand the multiset construction?

Note: I've posted a detailed answer to the question of the OP which also clarifies your question.

First of all: You did not misunderstand the multiset construction and the function $P_1(z)$ is actually the generating function for the partitions of two-colored, odd integers $>1$.

Two hints:

• Observe that the number of partitions of two-colored,odd integers $> 1$ of $6$ is $3$, namely $$6=3_b+3_b=3_b+3_r=3_r+3_r$$ while the number of compositions of $6$ is $4$ $$6=3_b+3_b=3_b+3_r=3_r+3_b=3_r+3_r$$

• The function $P_2(z)$ is regrettably neither the generating function for compositions nor for partitions.

The number of partitions with two-colored, odd integers $> 1$ of $10$ is $7$, the number of compositions of $10$ is $12$, while $[z^{10}]P_2(z)=8$.

Note: Last, but not least I fully agree with you: Flajolets book is an outstanding classic. :-)

• Thank you very much. I miscounted the number of partitions for $n=6$. Oct 13, 2014 at 14:26
• @john_leo: You're welcome! It was interesting and a pleasure for me to clarify these things. Especially at the beginning your $P_2(z)$ seemed to be a plausible candidate! :-) Oct 13, 2014 at 15:30