Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

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.

share|improve this answer
    
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
    
Yes, and yes. Thanks you guys! –  Dimitrije Kostic Dec 18 '11 at 18:00
    
@Dimirijie - thanks for the great answer, but unfortunately I missed out on a restriction - could you please look at the question again ? Thanks! –  TCSGrad Dec 18 '11 at 18:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.