# How to solve the following combinatorics problem?

There are $C$ kinds of colored balls, with $f_i$ being the frequency of each color $c_i$, such that $\Sigma_{i=1}^{C}f_i = n$, and $F= max(f_i)$.

Let $G(x)$ be the number of ways in which these $n$ balls can be placed in $x$ bins, with the following restriction:

• No bin shall contain more than one ball of the same color.

I'm trying to find the following sum: $\Sigma_{i=2}^{n}G(i)$

I'm not very skilled in combinatorial problems - hence I'm looking at possible ways in which to approach this. What I was particularly interested in knowing is whether I can use a dynamic programming approach to solve this problem efficiently for large values of $n$ (~10000). It would be really appreciated if I were to get some kind of hints/tips as to how I should go about trying to solve this.

EDIT: One important feature, which I didn't understand before: the distributions have to be unique i.e. the bins are indistinguishable. I'm giving the following example:

$C = 3$, $f_1 = 3$ , $f_2$ = $f_3$ = 2

The only distribution for $G(3)$ (by virtue of the uniqueness criteria) is:

• Bin 1 = $c_1$, $c_2$
• Bin 2 = $c_1$, $c_2$, $c_3$
• Bin 3 = $c_1$, $c_3$

Since Bins 1,2,3 are identical, the other combinations of placement boil down to this basic distribution, which the answer posted (by Dimitrije) would not cover. Could anyone please point me to what modification needs to be done?

-
You said there are $C$ kinds of balls, so I think you mean $\sum_{i=1}^C f_i = n$. –  Dimitrije Kostic Dec 18 '11 at 15:24
Oh yes - edited ! –  TCSGrad Dec 18 '11 at 16:29
Consider what $G$ does just on the set of balls of color $c_i$. $G$ will send these balls to all different bins. There are $\binom{n}{f_i}$ ways to put $f_i$ balls of color $c_i$ in $n$ bins without putting two of them in the same one.
$G$ does that for each of the $C$ kinds of balls, so $G(x) = \prod_{i=1}^{C} \binom{x}{f_i}$. So $\sum_{i=2}^n G(i) = \sum_{i=2}^n \prod_{j=1}^C \binom{i}{f_j}$. I don't think there's a cleaner expression than that.
I don't think you want to call both your summation indices $i$. Also your outer sum could start at the largest value $c_i$. –  Marc van Leeuwen Dec 18 '11 at 15:56
In the expression for G(x), I assume you meant $\binom{x}{c_i}$, instead of $\binom{n}{c_i}$ ? –  TCSGrad Dec 18 '11 at 16:39