Solving Combinatorial Problem - Red Ball Distribution in Three Bins

Question

I'm reaching out to the community for help in tackling a combinatorial problem that I'm currently stuck on. The problem revolves around distributing twelve identical red balls into three bins, labeled $A$, $B$, and $C$, while satisfying specific conditions:

1. Bin $A$ must contain 1, 3, or 5 balls.
2. Bin $B$ must have at least two balls.
3. Bin $C$ must contain an odd number of balls.

The goal is to calculate the number of ways to achieve this distribution.

I've established that bin $B$ must have an even number of balls, as bins $A$ and $C$ are required to contain an odd number of balls to sum up to 12 (an even number).

We've begun exploring possibilities by considering different cases for bin $A$:

• When bin $A$ contains 1 ball, we deduced that bin $B$ could range from 2 to 10 balls, and the corresponding number of balls in bin $C$ can be calculated accordingly.
• However, we're uncertain about formulating a general formula to streamline this process, as brute-forcing through all possibilities could be time-consuming.

Answer 1

You can simplify the problem quite a bit by using the specific conditions that you have already deduced. The trick is to think about pairs of balls, rather than individual balls.

Start by placing $1$ ball in bin A, $2$ balls in bin B, and $1$ ball in bin C. There are $8$ balls remaining, meaning $4$ pairs of balls remaining. And since you know the parity of each bin in a solution can't change, all you have to place is pairs of balls.

Count unconstrained solutions to $y_1+y_2+y_3=4$. By stars and bars there are $\binom 64=15$ unconstrained solutions.

Of the $15$ unconstrained solutions, there are $2$ solutions that don't work because $y_1=3$ (corresponding to $7$ balls in bin A), and $1$ solution that doesn't work because $y_1=4$ (corresponding to $9$ balls in bin A). Or to do this a little more systematically, identify the unacceptable solutions (those in which $y_1 \geq 3$) by placing $3$ more pairs in bin A and then counting solutions to $z_1+y_2+y_3=1$. There are $3$ solutions to that equation so there are $3$ unacceptable solutions to the unconstrained equation. There are, therefore, a total of $12$ solutions that satisfy your constraints.

Answer 2

Place 1, 3, or 5 balls in box A, so you will have three cases. Next place 2 balls in box B so there are at least two there. Then distribute the remaining balls (9, 7, or 5 depending on the case) between boxes B and C such that box C receives an odd count.

To do that last bit, pull two boxes out of your hat, sort those odd remaining balls in those boxes. As you noticed, one will contain an odd count and the other an even count, so just select which will mete the requirements to fill box B and C.

Answer 3

Plot and count the possibilities for the pair of numbers (Balls in A, Balls in C).

Answer 4

You can simply make use of ordinary generating functions.

• The generating function for bin A is : $$x^1+x^3+x^5=\frac{x-x^7}{1-x^2}$$

• The generating function for bin B is : $$x^2+x^3+x^4+...=\frac{x^2}{1-x}$$

• The generating function for bin C is : $$x^1+x^3+x^5+...=\frac{x}{1-x^2}$$

Realize that the exponentials represent the number of balls that the bins can contain. Then find the coefficient of $x^{12}$ in the expansion of $$\frac{x-x^7}{1-x^2}\frac{x^2}{1-x}\frac{x}{1-x^2}$$

,which is $12$