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?