0
$\begingroup$

$k = \sqrt n$ balls are thrown into $n$ bins. The bins are standing in a row and numbered from 1 to $n$. What is the probability that there are no two balls in the same bin or in adjacent bins???

In other words the probability that the distance between every two balls is at least one bin.

I'm not sure how to even begin solving this. If a ball lands on the end then the next ball has only 2 places where it cannot land. But if a ball lands not on the end then the next ball has 3 places and now I have up to 2 more ends to contend with. I tried drawing a probability tree but very quickly got lost.

$\endgroup$
2
$\begingroup$

There are $n^k$ ways to assign the $k$ balls to the $n$ bins with no constraints, all of which we assume are equally likely. There are $\binom{n-k+1}{k}$ ways to pick $k$ bins, no two of which are adjacent. And given the bins, there are $k!$ ways to assign the balls to the bins. So the probability that the assignment of balls to bins is acceptable is $$\frac{\binom{n-k+1}{k} k!}{n^k} = \frac{(n-k+1)!}{(n-2k+1)! \; n^k}$$


If you are not familiar with the formula for the number of ways to select k non-adjacent items from n, here is a derivation. Suppose we want to select $k$ non-adjacent integers $a_1, a_2, a_3, \dots ,a_k$ from the set $\{1, 2, 3, \dots ,n\}$. For the choices to be non-adjacent, we must have $1 \le a_1$, $a_1 < a_2-1$, $a_2 < a_3-1$, $a_3 < a_4-1$, ..., $a_{k-1} < a_k -1$, and $a_k \le n$. An equivalent set of inequalities is $$1 \le a_1 < a_2-1 < a_3-2 < a_4-3 < \dots < a_k-k+1 \le n-k+1$$ So we may equivalently pick the values $ a_1 , a_2-1 , a_3-2 , a_4-3 , \dots , a_k-k+1$ from $\{1, 2, 3, \dots ,n-k+1 \}$, and this can be done in $\binom{n-k+1}{k}$ ways.

$\endgroup$
  • $\begingroup$ Thank you, but I don't understand your answer. First- I'm pretty sure that there are $n^k$ ways to assign the k balls to the n bins, and not $k^n$. Second- can you explain to me please how you go to the $\binom{n-k+1}{k}$ ways to pick k bins. Thanks. $\endgroup$ – user103633 Oct 28 '13 at 14:38
  • $\begingroup$ Oops, you're right about n^k! I'll correct the solution. $\endgroup$ – awkward Oct 29 '13 at 0:45
  • $\begingroup$ Thanks. There is another thing that I don't understand: after we pick k bins why do we multiply by $k!$? all balls are identical,why does their order matter? $\endgroup$ – user103633 Oct 29 '13 at 18:45
  • $\begingroup$ In counting the n^k ways to assign the balls to the bins, the order of the balls matters; for example, an arrangement with ball 1 in bin 1 is different than an arrangement with ball 2 in bin 1. So when we count the number of arrangements which are "acceptable" (no more than one ball per bin, no adjacent bins), we must distinguish between different orderings of the balls. $\endgroup$ – awkward Oct 30 '13 at 0:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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