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

Question

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?

Answer 1

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

Answer 2

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$