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.

I have the following problem. $N$ balls are dropped randomly into $M$ containers $C_i$, $i=1..M$ with probability $p_i$, $\sum_i p_i = 1$. Having dropped $N$ balls into the container, $c_i$ may hold the number of balls in container $i$. Let's denote the tuple $(c_1, ..., c_N)$ as a configuration. My question is how many configurations of $N$ balls in $M$ containers exist and what is their distribution?

Assume we have $N=5$ balls and $M=2$ containers. Each ball is dropped with probability $p_1, p_2$ into container $C_1,C_2$, respectively. $p_1 + p_2 = 1$. If I'm not mistaken, only the following configurations are possible:

$\Omega = \{(5,0),(0,5),(1,4),(4,1),(2,3),(3,2)\}$

How can I determine the number of configurations $|\Omega|$ and how can I determine the probability $Pr(\omega \in \Omega)$ of each such configuration? I have to admit that so far I got nothing. Thank you for your help!

share|improve this question
    
The last paragraph contradicts both your example and the characterization via the tuple $(c_1,\dotsc,c_N)$, which are appropriate for indistinguishable balls. If the balls are distinguishable, there are $2^5=32$ different arrangements in the example, with $2$ different choices for each of the $5$ balls. –  joriki Jan 15 '13 at 7:45
    
@joriki: You are right. I needed a way to illustrate what I mean, say, to indicate that I'm interested in the probability of a configuration, not something else. I'd appreciate if you could help me improve the description. –  Jef Jan 15 '13 at 8:28
    
I don't understand -- you've accepted André's answer, so apparently you did mean indistinguishable balls; all the rest of the question is consistent with that ; all you have to do now to fix it is to replace "the balls are labeled, thus distinguishable" by "the balls are indistinguishable". –  joriki Jan 15 '13 at 9:08
    
@joriki: Done, thx. –  Jef Jan 15 '13 at 9:19
add comment

1 Answer 1

up vote 1 down vote accepted

The number of configurations is the number of solutions od the equation $x_1+x_2+\cdots +x_M=N$ in non-negative integers $x_i$. This is a standard Stars and Bars problem (please see the Wikipedia article). We can think of the number of solutions as the number of ways to distribute $N$ indistinguishable candies between $M$ children. This turns out to be $$\binom{N+M-1}{M-1}.$$

For finding the various probabilities, one uses the multinomial distribution. For instance, the configuration $(3,2)$ in your example has probability $\binom{5}{3,2}p_1^3p_2^2$. Here $\binom{5}{3,2}=\frac{5!}{3!2!}$. This is the ordinary binomial coefficient $\binom{5}{3}$.

share|improve this answer
    
Thank you. I did not know about the multinomial distribution. –  Jef Jan 15 '13 at 8:26
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.