3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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. :-)

$\endgroup$
  • $\begingroup$ Thank you very much. I miscounted the number of partitions for $n=6$. $\endgroup$ – john_leo Oct 13 '14 at 14:26
  • $\begingroup$ @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! :-) $\endgroup$ – Markus Scheuer Oct 13 '14 at 15:30

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.