On partitions of integers

468 Views Asked by At

In an example in my textbook, I came across a question where it was asked to find the generating function for the number of partitions of ${n \in N}$ into summands that (a) cannot occur more than 5 times; and (b) cannot exceed 12 and cannot occur more than 5 times.

The proposed solution for (a) is:

${f(x)=(1+x+x^2+...+x^5)(1+x^2+x^4+...+x^{10})...=\Pi_{i=1}^\infty(1+x^i+x^{2i}+...+x^{5i})}$

And the solution for (b) is proposed as:

${\Pi_{i=1}^{12}(1+x^i+x^{2i}+...+x^{5i})}$

However, the book fails to elaborate on what these problems concretely represent in practical terms.

For instance, when it says, it cannot occur more than 5 times, would it mean that we cannot repeat the same part of the partition more than 5 times? And what exactly does it mean when it says, it cannot exceed 12 in practical terms?

2

There are 2 best solutions below

0
On BEST ANSWER

Think of playing a solitaire game where you have $5$ identical decks of $m$ cards; the cards are numbered $1,\ldots,m$. You mix the decks together and try to find sets adding up to $n$. The question is how many solutions there are.

For (a), you can think of $m$ as being $\infty$, i.e. there's no bound on the numbers on the cards. Or you can take $m=n$, since cards with labels greater than $n$ can't be in a solution.

For (b) we are fixing $m=12$.

0
On

If $n=72$, the partition $7+2+3+7+7+7+9+13+10+7=72$ doesn't answer (b) because $13>12$, but it answers (a) because, although the summand 7 appears five times, it doesn't appear more than five times.