0
$\begingroup$

In how many ways can we distribute $6$ red balls, $7$ green balls and $8$ blue balls in $3$ different boxes such that each box has at least one ball of each color?

I'd like to solve this problem via generating functions. I guess the generating function would be:

$$(1-x^7)(1-x^8)(1-x^9)\cdot\frac{1}{(1-x)^3}$$

The problem is that the coefficient of $x^3$ also counts boxes that have $3$ blue balls and no other ball of other color. Then I guess it would become a little complicated to extract the cases that fail. Then I thought this:

$$\frac{1-x^7}{1-x} \cdot \frac{1-y^8}{1-y} \cdot \frac{1-x^9}{1-z}$$

I'd have to count the coefficients of $x^ny^mz^o$ with $n,m,o\geq 1$, but somehow it doesn't seem very practical. I've also tried to assume that each box had one fruit of each kind and then distribute the rest, which would yield:

$$(x+x^2)(x+x^2+x^3)(x+x^2+x^3+x^4),$$

but the expansion of this yields a number too small for the answer. I'm out of ideas, can you help me?

$\endgroup$
  • $\begingroup$ Do you have a specific number of boxes in mind or are you considering all the possibilities up to six boxes? $\endgroup$ – N. F. Taussig Feb 23 '15 at 11:24
  • $\begingroup$ @Taussig Sorry,I meant 3 boxes. I forgot to add it. $\endgroup$ – Billy Rubina Feb 23 '15 at 12:34
  • 1
    $\begingroup$ I do not know whether this problem can be done with generating functions. It is possible to solve it determining the number of solutions of the equations $x_1 + x_2 + x_3 = 3$, $y_1 + y_2 + y_3 = 4$, and $z_1 + z_2 + z_3 = 5$ in the non-negative integers, then multiplying the results. $\endgroup$ – N. F. Taussig Feb 23 '15 at 14:18
3
$\begingroup$

As N. F. Taussig points out, you can treat each of the colors independently and multiply the results, so let's start with the red balls. We want to distribute $6$ red balls into each of three bins, with at least one ball in each bin; this will be the coefficient of $x^6$ in the product $$ (x+x^2+\cdots)\ (x+x^2+\cdots)\ (x+x^2+\cdots) = \frac{x^3}{(1-x)^3}. $$ We have $[x^6] \frac{x^3}{(1-x)^3} = [x^3] (1-x)^{-3}$, which by the binomial theorem is $(-1)^3\binom{-3}{3} = \binom{5}{3}$.

Similarly, for the green and blue balls, you extract the $x^7$ and $x^8$ coefficients respectively. Multiplying everything out, you get $$\binom53\binom64\binom75.$$

If you wanted to do this all as one generating function, you could also express this as $$[x^6 y^7 z^8] \frac{x^3}{(1-x)^3}\frac{y^3}{(1-y)^3}\frac{z^3}{(1-z)^3}.$$

$\endgroup$
  • $\begingroup$ When I did this problem without generating polynomials, I obtained $$\binom{5}{2}\binom{6}{2}\binom{7}{2}$$ which agrees with Tad's answer. $\endgroup$ – N. F. Taussig Feb 24 '15 at 12:09

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.