Color Combinations When Drawing Balls
A bag contains an unlimited supply of balls in three different colors (say red, green, and blue). You draw balls from the bag and care only about the combination of colors, not the order.
(a) If you draw 3 balls, how many distinct color combinations are possible?
(b) Generalize: if you draw $n$ balls from 3 colors, how many distinct color combinations are there?
Hints
- This is a combinations-with-replacement problem: order does not matter, and each color can be chosen multiple times.
- Reframe it as: how many non-negative integer solutions are there to $r + g + b = n$? Use the stars and bars formula.
- Stars and bars gives $\binom{n + k - 1}{k - 1}$ for $n$ objects and $k$ categories. Here $k = 3$.
Worked Solution
How to Think About It: This is a classic "stars and bars" counting problem. You are distributing $n$ identical draws among 3 color categories. The order of draws does not matter -- only the counts of each color. This is equivalent to counting the number of non-negative integer solutions to $r + g + b = n$.
Quick Estimate: For $n = 3$ and 3 colors, just enumerate: you could have all one color (3 ways), two of one and one of another ($3 \times 2 = 6$ ways), or one of each (1 way). Total: $3 + 6 + 1 = 10$.
Approach: Stars and bars formula for combinations with replacement.
Formal Solution:
(a) We need the number of non-negative integer solutions to $r + g + b = 3$. By stars and bars, this is: $\binom{3 + 3 - 1}{3 - 1} = \binom{5}{2} = 10$
Enumeration as a check (listing $(r, g, b)$): - All one color: $(3,0,0), (0,3,0), (0,0,3)$ -- 3 combinations - Two of one, one of another: $(2,1,0), (2,0,1), (1,2,0), (0,2,1), (1,0,2), (0,1,2)$ -- 6 combinations - One of each: $(1,1,1)$ -- 1 combination - Total: $3 + 6 + 1 = 10$ \checkmark
(b) For general $n$ balls and 3 colors, the number of solutions to $r + g + b = n$ with $r, g, b \ge 0$ is: $\binom{n + 2}{2} = \frac{(n+1)(n+2)}{2}$
Sanity checks: - $n = 1$: $\binom{3}{2} = 3$ (pick one of three colors) \checkmark - $n = 2$: $\binom{4}{2} = 6$ \checkmark - $n = 3$: $\binom{5}{2} = 10$ \checkmark
Generalization to $k$ colors: Distribute $n$ balls among $k$ colors gives $\binom{n + k - 1}{k - 1}$.
Answer: (a) $\binom{5}{2} = 10$ combinations. (b) $\binom{n+2}{2} = \dfrac{(n+1)(n+2)}{2}$ combinations.
Intuition
Stars and bars is one of the most versatile counting tools. The idea is to convert a combinatorial selection problem into an equivalent problem of placing dividers among objects. If you have $n$ identical balls (stars) and need to divide them into $k$ groups (colors), you place $k - 1$ dividers (bars) among the $n + k - 1$ positions. The formula $\binom{n + k - 1}{k - 1}$ counts the number of ways to place those dividers. This same technique shows up whenever you need to count multisets, distribute indistinguishable objects into distinguishable bins, or count monomials of a given degree. In quant interviews, it often appears disguised as a probability question -- for example, counting the number of ways to distribute trades among desks or orders among time buckets.