$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.
Best Answer
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.