0
$\begingroup$

In how many ways can we distribute $11$ oranges and $6$ pears to $3$ kids, such that each kid gets at least $3$ orange and a maximum of $2$ pears?

I guess the generating function for the distribution of oranges is $(x^3+x^4+x^5)^3$. It doesn't have $x^6$ because if one kid had six oranges, then $11-6=5$ and one kid would have less than $3$ oranges. Then eash kid must have at least $3$, with a total of $9$. Then we must find the value of the coefficients from $x^9,x^{10},x^{11}$ on $(x^3+x^4+x^5)^3$.

Writing it as:

$$(x^3+x^4+x^5)^3=x^9(1+x+x^2)^3$$

Then we have to find the coefficients of $x^{9-9},x^{10-9},x^{11-9}=x^{0},x^{1},x^{2}$ in $(1+x+x^2)^3$. Rewriting it:

$$(1+x+x^2)^3=\left[\frac{1-x^3}{1-x}\right]^3=(1-x^3)^3 \left[ \frac{1}{1-x}\right]^3$$

Then:

$$(1-x^3)^3=\sum_{i=0}^3(-1)^i{3\choose i}x^{3i}\tag{A}$$

And:

$$\left[\frac{1}{1-x}\right]^3=\sum_{i=0}^{\infty}{3+i-1 \choose i}x^i\tag{B}$$

Then the coefficients for this part of the problem should be:

$$A_0B_0+A_0B_1+A_0B_2={3\choose 0}{2\choose 0}+{3\choose 0}{3\choose 1}+{3\choose 0}{4\choose 2}=1+3+6=10$$

And this number is bigger than the actual answer. I was planning to multiply this number by the result of the generating function for the pears, but I guess it's going to be bigger and farther from the answer. I tried to combine both generating functions, but it seems to cause a big hurdle to computation: $(1+ax+a^2x^2)^3 (b^3 x^3 + b^4 x^4 + b^5 x^5)^3$

Perhaps I am mistaken, but I don't know how to proceed to calculate this with generating functions.

$\endgroup$
  • 1
    $\begingroup$ I suppose you mean that each kid gets at least 3 oranges? $\endgroup$ – Uncountable Feb 16 '15 at 23:25
  • $\begingroup$ @Uncountable Yes, it was a typo. Thanks. $\endgroup$ – Billy Rubina Feb 16 '15 at 23:25
  • $\begingroup$ Is the actual answer $6$? $\endgroup$ – N. F. Taussig Feb 16 '15 at 23:33
  • $\begingroup$ @N.F.Taussig Yes. $\endgroup$ – Billy Rubina Feb 17 '15 at 0:47
1
$\begingroup$

If each of the three children receives a maximum of two of the six pears, then each child must receive two pears. If each of the three children receives at least three oranges, then there are two remaining oranges to distribute among the three children. This is equivalent to solving the equation $x_1 + x_2 + x_3 = 2$ in the non-negative integers, which can be done in $\binom{4}{2} = 6$ ways since it is the number of ways we can place two addition signs in a list of two ones.

$\endgroup$
1
$\begingroup$

First of all we give each kid $3$ oranges. Now there are $2$ oranges left to potentially distribute. Distributing $0$ oranges can be done only in $1$ way. Distributing $1$ oranges gives us $3$ choices and distributing $2$ oranges gives us $6$ ($2$ for one kid or a pair). So the total number of ways for the oranges is $10$. Now each kid gets either $0$, $1$ or $2$ pears. So we have $3^3=27$ ways for the pears. Now the total number of ways is $10*27=270 $.

Edit: If we have to give away all the fruit then each kid gets $2$ pears and we can distribute the remaining $2$ oranges in $6$ ways, as said before. So in this case, the final answer should be $6$.

$\endgroup$
  • $\begingroup$ I thini it should be 3+3=6 for oranges: we dont have options like 0+0+0 $\endgroup$ – Alex Feb 17 '15 at 10:28
1
$\begingroup$

For a generating function approach, consider the oranges and pears separately.

The OPSGF for the distribution of oranges is $$ f(x) = (x^3 + x^4 + x^5 + \dots)^3$$ You want the coefficient of $x^{11}$. It's true that we could disregard powers of $x^6$ or higher, but I think you will find the math simpler if we leave them in.

The series for the distribution of pears is $$ g(x) = (1 + x + x^2)^3$$ You want the coefficient of $x^6$.

Having found the solution to each of these sub-problems, multiply them together to find the number of ways to distribute both oranges and pears.

$\endgroup$
  • $\begingroup$ Why only the coefficient of $x^{11}$? Don't you need to count the coefficients of $x^{11},x^{10},x^{9}$? There is (for example) the ocasion when each kid has $3$ oranges, no? $\endgroup$ – Billy Rubina Feb 17 '15 at 1:17
  • $\begingroup$ Is it a general idea that I can leave the higher powers to simplify it? Aren't there ocasions when such procedure fails? $\endgroup$ – Billy Rubina Feb 17 '15 at 1:19
  • $\begingroup$ @Vyska, we only need the coefficient of $x^{11}$ in the first part because $x_1 + x_2 + x_3 = 11$, where $x_i$ is the number of oranges to kid $i$. As for leaving in the higher powers, try it both ways and see. If you were using a computer algebra system it might (or might not) be preferable to truncate the series. $\endgroup$ – awkward Feb 17 '15 at 18:27

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.