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$
3
  • $\begingroup$ Do you have a specific number of boxes in mind or are you considering all the possibilities up to six boxes? $\endgroup$ Commented Feb 23, 2015 at 11:24
  • $\begingroup$ @Taussig Sorry,I meant 3 boxes. I forgot to add it. $\endgroup$
    – Red Banana
    Commented Feb 23, 2015 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$ Commented Feb 23, 2015 at 14:18

1 Answer 1

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$
1
  • $\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$ Commented Feb 24, 2015 at 12:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .