# Counting problem - Distributing 30 balls over 4 boxes

We got 30 balls which are not distinguishable. We want to put them into 4 boxes A,B,C,D ,which are distinguishable, such that the number of balls in A is $\geq 10$ and in $B+C\leq 17$. This is equivalent to $\# \{(a,b,c,d) \in \mathbb N_{\geq 0}^4 \mid a \geq 10, b+c \leq 17, a+b+c+d = 30\}$.

How can I begin ?

My approach: Denote $\alpha(k)$ as the number of possibilities to put $k$ balls in $B$ and $C$ and $\beta(k)$ as the number for $B,C$ and $D$.

Then if $a=10$ we have $d \in \{3,4,\cdots,20\}$ and get $\sum_{d=3}^{20} \alpha(20 -k)$. The same for $a =11$ and $a=12$. For $a \geq 13$ we have to put the rest of the balls into $B,C$ and $D$ without restriction which gives $\sum_{k=0}^{17} \beta(k)$ possibilites. Now add all the stuff and I hope we get the result.

Further is $\alpha(k) = 2+k-1$ and $\beta(k) = \binom{3+k-1}{2}$

This approach results in 1653 possibilities.

Suggestions would be nice :)

-
I think you mean $d\in[3,20]$ where it says $d\in\{3,20\}$. –  joriki Apr 8 '13 at 10:34

Since $A$ needs at least $10$, put $10$ balls there. Now we need to distribute $20$ balls between $A$, $B$, $C$, and $D$ so that together $B$ and $C$ get $\le 17$.

$1.$ Find the number of ways to distribute $20$ balls between our four people, not paying any attention to the restriction about $B$ and $C$. I expect you have a standard Stars and Bars way of counting the number of ways to do this.

$2.$ But in $(1)$ you have counted some forbidden configurations, namely the ones in which between $B$ and $C$ we have (i) $18$; (ii) $19$; (ii) $20$.

Count all these bad configurations separately. For example, how many with $18$ between $B$ and $C$? There are $19$ ways to distribute the $18$ balls between $B$ and $C$. And for each of these there are $3$ ways to distribute the other $2$ between $A$ and $D$. Do the same sort of calculation for (ii) and for (iii).

Finally, subtract the total number obtained in $(2)$, that is, the sum of (i), (ii), and (iii), from the number obtained in $(1)$.

There is also a generating functions approach, probably overkill, and no easier.

-
Thanks. I love generating functions but yeah. This is an (practice)exam question so it should be solvable quite fast. I try to work out your method and see in what it results. Question: Do I have to sum over $\#A \in \{10,11,\cdots,30\}$ ? –  Andre Apr 8 '13 at 10:40
I have described how to do it. No summing. This is really about distributing $20$ balls. –  André Nicolas Apr 8 '13 at 10:46
This is great :) Makes it a lot easier and gives indeed the same result. –  Andre Apr 8 '13 at 10:56