What is the number of ways of choosing 70 balls from a jar with 30 red balls, 40 blue balls, and 50 green balls?

Question

I encountered this question in undergrad intro combinatorics class and my professor showed us how to use generating expressions to get the answer (it should be 1061).

My question has two parts:

1. Is there anyway to solve this problem from first principles without generating expressions? (I'm not looking for some complicated analytic expression, but an actual exact result)
2. Using generating expressions, what's the intuition behind each step of the process of solving?

I realize this is a bulky question, so please feel free to answer either part (or both) in full or just leave whatever thoughts you may have.

Answer 1

With regard to the first question, if we let $x_r, x_b,$ and $x_g$ represent, respectively, the number of red, blue, and green balls selected, then the number of ways we can select $70$ balls from the jar containing $30$ red, $40$ blue, and $50$ green balls is the number of solutions of the equation $$x_r + x_b + x_g = 70 \tag{1}$$ in the nonnegative integers subject to the restrictions $x_r \leq 30, x_b \leq 40, x_g \leq 50$.

If we initially ignore the restrictions on $x_r, x_b,$ and $x_g$, equation $1$ is an equation in the nonnegative integers. A particular solution of equation $1$ corresponds to the placement of two addition signs in a row of $70$ ones, with the number of ones to the left of the first addition sign representing the number of red balls selected, the number of ones between the two addition signs representing the number of blue balls selected, and the number of ones to the right of the second addition sign representing the number of green balls selected. Therefore, the number of solutions of equation $1$ is the number of ways we can select two of the $72$ positions required for $70$ ones and two addition signs to be filled with addition signs, which is $$\binom{70 + 3 - 1}{3 - 1} = \binom{72}{2}$$

In general, the number of ways $k$ objects can be selected from $n$ types of objects without restrictions is the number of solutions of the equation $$x_1 + x_2 + x_3 + \cdots + x_n = k$$ in the nonnegative integers, which is $$\binom{k + n - 1}{n - 1}$$ since we must select which $n - 1$ of the $k + n - 1$ positions required for $k$ ones and $n - 1$ addition signs will be filled with addition signs.

However, we must remove those solutions of equation $1$ which violate one or more of the restrictions $x_r \leq 30, x_b \leq 40, x_g \leq 50$. Observe that it is not possible to violate two or more of the restrictions simultaneously since $31 + 41 = 72 > 70$.

Suppose $x_r > 30$. Then $x_r' = x_r - 31$ is a nonnegative integer. Substituting $x_r' + 31$ for $x_r$ in equation $1$ yields \begin{align*} x_r' + 31 + x_b + x_g & = 70\\ x_r' + x_b + x_g & = 39 \end{align*} which is an equation in the nonnegative integers with $$\binom{39 + 3 - 1}{3 - 1} = \binom{41}{2}$$ solutions.

As you should verify, there are $$\binom{31}{2}$$ solutions of equation $1$ which violate the restriction that $x_b \leq 40$ and $$\binom{21}{2}$$ solutions of equation $1$ which violate the restriction that $x_g \leq 50$.

Thus, by the Inclusion-Exclusion Principle, the number of ways we can select $70$ balls from the jar containing $30$ red, $40$ blue, and $50$ green balls is $$\binom{72}{2} - \binom{41}{2} - \binom{31}{2} - \binom{21}{2} = 1061$$

Answer 2

The inclusion-exclusion approach has already been covered in the comments. For the generating function approach, we have three decisions: how many red, blue, and green to choose. Each term of the sums $x^0+x^1+\dots+x^{30}$, $x^0+x^1+\dots+x^{40}$, and $x^0+x^1+\dots+x^{50}$ records the number of red, blue, and green, respectively. Choosing $r$ red, $b$ blue, and $g$ green yields $r+b+g$ balls in total, and multiplication of the three sums yields corresponding terms of the form $x^r x^b x^g=x^{r+b+g}$. So the generating function for the number $a_n$ of ways to choose $n$ balls is \begin{align} \sum_{n=0}^\infty a_n x^n &= (x^0+x^1+\dots+x^{30})(x^0+x^1+\dots+x^{40})(x^0+x^1+\dots+x^{50}) \\ &= \frac{1-x^{31}}{1-x}\cdot\frac{1-x^{41}}{1-x}\cdot\frac{1-x^{51}}{1-x} \end{align} You want the coefficient of $x^{70}$, which turns out to be $a_{70}=1061$.