1
$\begingroup$

Number of ways to distribute five red balls and five blues balls into 3 distinct boxes with no empty boxes allowed

The link above provides the solution by way of PIE.

I was wondering if we could solve this more directly. I tried this method below.

We first distribute the red balls into the boxes in $\binom{4}{2}$ ways because we don't want to leave any boxes empty. Then for each of those six ways, we can distribute the blue balls in the boxes in $\binom 75$ ways because we can distribute without restrictions now. That's $6 \cdot 21= 126$ ways in total. Now we must repeat the process above by distributing the blue balls first. Then altogther we have $2 \cdot 126 = 252$ distributions. This is not only an undercount (the answer must be $336)$, but we also overcounted. There are at least $6$ redundant combinations. For example, we can distribute one red ball in the first box, three red balls in the second box and one red ball in the third box, then distribute one blue ball in the first box, three blue balls in the second box and one blue ball in the third box; but exactly the same scenario is possible when we distribute the blue balls first, so there's one redundant combination.

What's the better way of counting the distributions without PIE in this problem? Thanks.

$\endgroup$

1 Answer 1

1
$\begingroup$

A slightly different approach which is nonetheless closely related to PIE is to use a generating function, i.e.

$$[R^5 B^5] \left(-1 + \frac{1}{1-R}\frac{1}{1-B}\right)^3.$$

This will produce

$$[R^5 B^5] \left(\frac{1}{(1-R)^3}\frac{1}{(1-B)^3} - 3 \frac{1}{(1-R)^2}\frac{1}{(1-B)^2} + 3 \frac{1}{1-R}\frac{1}{1-B} - 1\right).$$

Extracting coefficients we find

$${5+2\choose 2}^2 - 3 {5+1\choose 1}^2 + 3 {5+0\choose 0}^2 = 336 $$

which is the same result as what was obtained at the linked-to post.

$\endgroup$

You must log in to answer this question.

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