Balls, Balls, and Balls!

Relevant wiki: Generating Functions

I will show two ways to solve this problem, both making use of generating functions .

$\fbox{1st way}$

First, we can transform the question into $a + b + c = 13$ , removing the "at least one ball" part. Then, look at a more general question of finding the number of solutions in non-negative integers to the equation $a + b + c = n$ .[From here we can solve it with stars and bars , but we will use generating functions here instead] Since the value of $a$ can be any non-negative integer $0,1,2,3, \ldots, i , \ldots$ (see note below), we can represent this as the generating function $A(x) = 1 + x + x^2 + \cdots + x^i + \cdots .$ We have the same generating function for the possible values of $b$ and $c$ . So our generating function for the number of solutions is $A(x) \times B(x) \times C(x) = [A(x)]^3$ . However, finding this product could be extremely tedious.

We instead transform $A(x)$ into the rational function $\frac{1}{1-x}$ , which we recognize from the sum of a geometric progression. Thus, we are interested in $[A(x)]^3 = \frac{1}{(1-x)^3}$ . This can be expanded using the negative binomial theorem , which gives

$\frac{1}{(1-x)^3} = {2 \choose 2} + {3 \choose 2} x + { 4 \choose 2 } x^2 + \cdots + { i+2 \choose 2 } x^ i + \cdots.$

Therefore, the answer when $n=13$ is given by ${ 15 \choose 2 } = 105$ . This agrees with what we know from the stars and bars .

But we only have 9 balls each. Hence we need to deduct the possibilities where one type of ball are $>9$ .

We now draw a table and write down all the possibilities.

Hence $105-30=75 \ _\square$

Note: It might be confusing why we allow $a$ to be any non-negative integer, even those which are larger than $n$ , which clearly would not lead to a solution. Consider what would happen if we let $a = n+1$ or $a = n+2$ or any larger integer: In the final product of polynomials, the exponents of these terms would be larger than $n,$ so they will not contribute to the term we want, which has exponent $n.$

$\fbox{2nd way}$

First, we look at a more general question of finding the number of solutions in non-negative integers to the equation $a + b + c = n$ . Since the value of $a$ can be any positive integer $1,2,3, \ldots, 10$ , we can represent this as the generating function $A(x) = x + x^2 + \cdots + x^{10} = x (1 + x + x^2 + \cdots + x^{9}) = \frac{x^3(1-x^{10})^3}{(1-x)^3}.$ We have the same generating function for the possible values of $b$ and $c$ . So our generating function for the number of solutions is $A(x) \times B(x) \times C(x) = [A(x)]^3$ .

$\begin{aligned} A(x) \times B(x) \times C(x) &= [A(x)]^3 \\ &= \frac{x^3(1-x^{10})^3}{(1-x)^3} \\ &= x^3(1-x^{10})^3(1-x)^{-3} \\ &= x^3 (1-3x^{10}+3x^{20}-x^{30}) \sum_{k=0}^{ \infty } {k+2 \choose k} x^k \\ \end{aligned}$

The coefficient of $x^{16}$ is then the number of ways the balls can be picked. To compute this, take the $1$ from the first bracket and let $k=13$ , and take $-3x^{10}$ from the first bracket and let $k=3$ :

${15 \choose 2} - 3{5 \choose 2} = 75 \ _\square$

There is a simple use of stars and bars without the algorithm of generating functions

It is [15C2]-3×[5C2]=75

Find the coefficient of x^16 in the Taylor series expansion of the generating function: {(x+x^2+...... x^10)^3} ={x(1-x^10)/(1-x)}^3, using Wolfram Alpha. Answer is 75.

To remove the "at least one ball" part, choose one of each which leaves you with the following: 9 red, 9 blue, 9 green, pick 13 of them.

Now, without loss of generality consider the number of reds. Below, this shows the number of reds, the possibilities and then the number of permutations.

0 red = 9,4 8,5 7,6 ... 4,9 x6

1 red = 9,3 ... 3,9 x7

2 red = 9,2 ... 2,9 x8

3 red = 9,1 ... 1,9 x9

4 red = 9,0 ... 0,9 x10

5 red = 8,0 ... 0,8 x9

6 red = 7,0 ... 0,7 x8

7 red = 6,0 ... 0,6 x7

8 red = 5,0 ... 0,5 x6

9 red = 4,0 ... 0,4 x5

Summing these number of permutations gives us our answer.

(There is probably a better way to do it than this)