1
$\begingroup$

The question is like this:

In how many ways can 13 chocolate-chip cookies and 8 jelly donuts be distributed among four children that each child gets at least one cookies and one donuts?

The model answer of this question is:

${9+4-1 \choose 4-1}{4+4-1 \choose 4-1} = {12 \choose 3}{7 \choose 3} = 7700$

However, I cannot understand why using generating function method does not work:

$((x+x^2+...+x^{13-3})(x+x^2+...+x^{8-3}))^4$

where $13-3$ means every kid can at most get $10$ cookies as each of the others 3 kids need to get at least one.

With this method, I get an answer of $52020$ ways to do this.

So what is wrong with this method? I am really confused. Could anyone explain this to me?

Thanks in advance :D

$\endgroup$
2
$\begingroup$

Your generating function is a product of $8$ factors, and the products of terms making $x^{21}$ include things like this: $$x^1x^2x^3x^4x^5x^4x^1x^1=x^{21}\ .$$ The interpretation of this is that the children receive $1,2,3,4$ cookies and $5,4,1,1$ donuts, which is clearly not a valid solution to the problem.

$\endgroup$
  • $\begingroup$ Oh I see :D Thanks a lot. But does it also mean that we can't use generating function to solve this kind of problems? $\endgroup$ – SPMIHC Nov 1 '14 at 12:13
  • 2
    $\begingroup$ You could use two variables and find the coefficient of $c^{13}d^8$ in$$(c+c^2+c^3+\cdots)^4(d+d^2+d^3+\cdots)^4\ .$$ $\endgroup$ – David Nov 1 '14 at 12:51
  • $\begingroup$ Oh I can understand it now :D Thank you very much $\endgroup$ – SPMIHC Nov 1 '14 at 13:29
1
$\begingroup$

Expanding the comment of the OP on the answer of @David, you can use this generating function

$$f(x,y)=((x+x^2+...+x^{13-3})(y+y^2+...+y^{8-3}))^4$$

and after search the coefficient for $x^{13}y^8$.

Anyway see that you have 2 independent distributions combined into one: the distribution of chocolate and the distribution of donuts.

$\endgroup$

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.