How many ways are there to fill a bag (maximum of weight $N$) with watermelons, apples, and grapes, where the number of apples has to be at least the number of watermelons? The weights are given as follows:

$\omega(watermelon) = 10$

$\omega(apple) = 2$

$\omega(grapes) = 1$

So far, I've tried creating the series for each fruit and using the product lemma to multiply them. The answer would be:

the coefficient of $x^N$ of $(\sum_{j=0}^{\inf} x^j)\ (\sum_{j=0}^{inf} x^{2j})\ (\sum_{j=0}^{inf} x^{10j})$

However, this does not account for the restriction that the number of apples has to be at least the number of watermelons. I don't really know where to go from here.

Edit: Thank you Nicholas for the answer. I found another way to get the same answer. I'd say this is more of an algebraic solution where as Nicholas' solution is more combinatoric. Here is my approach: let a = #apples, w = #watermelons, g = #grapes

we know that $a = w +y$, where $y \in Z, y\ge 0$. and $g + 2a + 10w = N$, substituting we get $g + 2y + 12w$ = N.

We can now write this in terms of generating functions as $(\sum_{j=0}^{\inf} x^j)\ (\sum_{j=0}^{inf} x^{2j})\ (\sum_{j=0}^{inf} x^{12j})$, which gives the same solution.


Because of the closely connected nature of the numbers of apples and watermelons, you can't handle them separately. I would say that the OGF for the total weight of apples AND watermelons is $$ \sum_{n=0}^{\infty}x^{10n}\sum_{m=n}^{\infty}x^{2m}=\sum_{n=0}^{\infty}x^{10n}\cdot\frac{x^{2n}}{1-x^2}=\frac{1}{1-x^2}\sum_{n=0}^{\infty}x^{12n}=\frac{1}{(1-x^2)(1-x^{12})}. $$

Another way to explain this generating function: you are taking any number of pairs of apples and watermelons, at a total of weight 12 each, plus any number of apples at weight 2.

In any event, since the number of grapes IS separate from apples/watermelons, you then just have to multiply by the OGF for grapes, which is $\frac{1}{1-x}$.

  • $\begingroup$ Thank you for the response! I had just obtained the same answer through another method, which is reassuring. I will post my solution in the question $\endgroup$ – rola Jun 1 '14 at 17:36

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.