# Drawing colored balls

I have a sack with $15$ red balls, $15$ blue balls, $15$ green balls and $15$ yellow balls (balls of the same color are indistingishable).

In how many ways can I take $30$ balls from the sack?

$\\$

I tried using $(\binom{4}{30})$, combination with repetition, but that ignores the restriction of having at most $15$ balls of the same color.

I thought about using a permutation with repetition, but I don't know how to then not take into account the order.

• $\binom{4}{30}$ doesn't make sense anyway. Commented May 19, 2015 at 9:00
• It's not $\binom{4} {30}$ ,but ($\binom{4} {30}$), which is combinations with repetition. You can find info about it in the provided link Commented May 19, 2015 at 11:09

## 2 Answers

You are asking for an integer partition of $30$ with at most four summands, each at most $15$, i.e. $$\#\{(a,b,c,d)\mid a+b+c+d = 30;~~ a,b,c,d\ge 0;~~ a,b,c,d\le 15\}$$ The first two of the conditions can be solved using the stars-and-bars method, $$\#\{(a,b,c,d)\mid a+b+c+d = 30;~~ a,b,c,d \ge 0\} = \binom{33}3$$ From these you have to subtract those where at least one summand exceeds $15$. If one summand exceeds $15$, no other can because $30-16 = 14 \le 15$, so these are disjoint. The four sets all have the same cardinality, namely that of $$\#\{(a,b,c,d) \mid a+b+c+d=30;~~ b,c,d \ge 0;~~ a \ge 16\} \\ =\#\{(a,b,c,d) \mid a+b+c+d=14;~~ a,b,c,d\ge 0\} = \binom{17}3$$

So the final answer is $$\binom{33}3 - 4\cdot \binom{17}3 = 2736$$

• Very elegant! Perhaps you'd like to apply your partition-wrangling skills to this recent question. :) Commented May 19, 2015 at 10:05

AlexR has given a combinatorial solution. Here is one with a recursion which produces the same answer.

If $f(n,m)$ is the number of ways of drawing $n$ balls from the first $m$ colours with no more than $15$ of each colour then $f(n,0)=0$ except $f(0,0)=1$ and $$f(n,m)=\sum_{j=0}^{15} f(n-j,m-1).$$ This can be translated into a generating function where you want the coefficient of $x^{30}$ in the expansion of $$\left(1 + x+ x^2+ \cdots + x^{15}\right)^4 = \left(\frac{1-x^{16}}{1-x\,\,\,}\right)^4$$ or you could just do the arithmetic of the recursion giving the following table:

n/m 0   1   2   3   4
-   -   -   --  --- ----
0   1   1   1   1   1
1   0   1   2   3   4
2   0   1   3   6   10
3   0   1   4   10  20
4   0   1   5   15  35
5   0   1   6   21  56
6   0   1   7   28  84
7   0   1   8   36  120
8   0   1   9   45  165
9   0   1   10  55  220
10  0   1   11  66  286
11  0   1   12  78  364
12  0   1   13  91  455
13  0   1   14  105 560
14  0   1   15  120 680
15  0   1   16  136 816
16  0   0   15  150 965
17  0   0   14  162 1124
18  0   0   13  172 1290
19  0   0   12  180 1460
20  0   0   11  186 1631
21  0   0   10  190 1800
22  0   0   9   192 1964
23  0   0   8   192 2120
24  0   0   7   190 2265
25  0   0   6   186 2396
26  0   0   5   180 2510
27  0   0   4   172 2604
28  0   0   3   162 2675
29  0   0   2   150 2720
30  0   0   1   136 2736


so the same answer as AlexR