# Probablity of $k$ balls go into at most (including) $m$ boxes, with $n$ given boxes ($m\le n\le k$)

Suppose I have $n$ boxes, and an infinity of balls. All balls are regarded the same.

I randomly throw balls into the boxes, each time the ball may be thrown into one of the box, with equal probability, i.e., $\frac{1}{n}$.

Now I throw $k$ times, each time one ball thrown into one box. Let $E_{k, m, n}$ denote the situation where the k balls go into at most (including) m boxes (with $m\leq n\leq k$). What is the probability for $E_{k,m,n}$ to happen?

• Are the boxes indistinguishable? – user208649 Jun 26 '15 at 2:48
• Yes. The boxes are the same. – zell Jun 26 '15 at 2:48

## 2 Answers

I think the answer could be as follows:

Using stars and bars, the number of ways k balls could get into m boxes is $(k-1)\choose(m-1)$ ways. the number of ways m boxes could be chosen amongst n boxes is $n\choose m$. The probability that each of the k balls could hit any of the boxes is $\frac{1}{n}$.If it is thrown k times, it is $(\frac{1}{n})^k$. Thus

$E(n,m,k) = {(k-1)\choose(m-1)}.{n\choose m}.(\frac{1}{n})^k$

• Shouldn't $E(n,n,k)=1$ ? I don't see how ${k-1\choose n-1}\cdot \frac{1}{n^k}=1$. – Alexey Burdin Jun 26 '15 at 3:51
• the k could get into n boxes however they want. In one box you may gave 1 and in other box you may have two given the fact that k>n – Satish Ramanathan Jun 26 '15 at 3:53
• So how can I achieve a sum probabilities of $1$ to test the formula? Don't I misunderstand something? – Alexey Burdin Jun 26 '15 at 3:58
• I think you can test the formula by running all values of m and n upto k. Then the sum would be 1. I have not tested but I am hoping that it will be right. I am talking about running values of m=1 to n and n = 1 to k. – Satish Ramanathan Jun 26 '15 at 4:17
• The simplest case would be have m = 1, n = 1 then the probability is 1 always – Satish Ramanathan Jun 26 '15 at 4:27

We have to take .care of the fact that

(a) more than one ball can go into a box

(b) arrangements through stars and bars are not equi-probable.

(c) probabilities (including box n) must sum to 1.

I believe we shall have to apply PIE, as illustrated below for n = 6, k = 10

Let $m_k$ denote the # of ways k boxes can be filled. Applying PIE, we get

$m_1 = {6\choose 1}\cdot 1^{10} = 6$

$m_2 = {6\choose 2}\cdot [2^{10} - {2\choose 1}\cdot1^{10}] = 15,330$

$m_3 ={6\choose 3}\cdot [3^{10} - {3\choose 2}\cdot2^{10} + {3\choose 1}\cdot 1^{10}] = 1119600$

Proceeding similarly,

$m_4 = 12277800$

$m_5 = 30618000$

$m_6$ = 16435440

Divide by 6^10 for the probabilities, which will sum to 1, as they must.

You can now generalise for $P[E_{k,m,n}]$

Edit:

Oh, comment gives boxes as indistinguishable ! Shall have to rethink !

Edit 2:

In effect, there are n targets at which you are throwing k missiles which always hit some target or other. This makes the targets distinct, which is what I took in my answer