Black and white balls, probability that no black ball is alone

Question

I've brought a extra layer to a problem I posted here: K balls in N boxes, no boxes contain 1 ball
Nota bene: This is a problem I'm using to work on my combinatorics

The scenario is pretty classic: k distinguishable balls (j black and k-j white) go in n distinguishable boxes with an equal probability without exclusion.

The objective is to find the probability that no black ball is left alone in a box. To clarify, two black balls in one box do not count, as does not a white ball alone in a box. The only scenario that counts is a black ball being alone in any box.

Here is the approach I've been using: We start by placing the black balls at random in the n boxes (non exclusive) and then count possible arrangements of white balls not leaving any black ball alone using occupancy vectors. Only problem is that occupancy do not account for the variety of the balls, or at least how I've been using them. Would it be a good idea to try and adapt those vectors and use a combination of multiple ones or rather find a more direct approach maybe using multinomial coefficients? (As I said earlier, combinatorics is really not my cup of tea but I'd like to learn the toolbox to solve most of the 'basic' problems).

Thanks in advance, Cheers!

Answer 1

I am not sure what you mean by "vectors". Here is how I would solve the problem:

Number the boxes 1 through n. Let $B_r$ be the event that box $r$ winds up with exactly one lone black ball. This occurs by placing a black ball in that particular box and then randomly distributing all other balls. There are $j$ balls to place in box $B_r$. Then, for every other of the $k-1$ balls, there are $n-1$ choices to place them. So, that is: $j(n-1)^{k-1}$ different possible ways of placing them.

Next, consider $|B_r \cap B_s|$ for $r\neq s$. We place two black balls into the two boxes. Then, we randomly distribute the remaining balls. So, that is $j(j-1)(n-2)^{k-2}$ ways of placing them.

For three different boxes with one black ball each, there are $j(j-1)(j-2)(n-3)^{k-3}$ ways of placing them.

Etc.

Next, apply Inclusion/Exclusion. Start with all possibilities, subtract off where at least one box has a single black ball. Add back where at least two boxes have exactly one black ball. Subtract where at least three boxes have one lone black ball, etc.

You wind up with something like this:

$$\sum_{i=0}^j(-1)^i \dbinom{n}{i}(j)_i(n-i)^{k-i}$$

Where $(j)_i$ is the falling factorial: $(j)_i = j(j-1)\cdots (j-i+1) = \dfrac{j!}{(j-i)!}$

Finally, divide by the total number of ways of distributing the balls: $n^k$.

Edit: I mixed up the $n$'s and the $k$'s. I think I fixed them all, but you may want to double check my work. I have to go for a bit.

Answer 2

Lets denote your probability as $P(j, k, N)$. Let's numerate the black balls from $1$ to $j$. Suppose $m$ is the least number of a lonely black ball. That meant, that the $m-th$ ball fell in a box, and all other balls fell into other boxes (the probability of that is $\frac{(N-1)^{k - 1}}{N^{k - 1}}$), and that all black balls with lesser numbers are not alone. To find the conditional probability of that let's remove the box with the $m$-th ball, and paint all black balls with number greater than $m$ white. Then this statement will be equivalent to our problem foer a different number of boxes and balls and thus the conditional probability will be $P(m - 1, k-1, N-1)$. Thus, the probability of this configuration will be $\frac{(N-1)^{k - 1}}{N^{k - 1}}P(m - 1, k-1, N-1)$. And from that we can get a recurrence, which solves your problem:

$$P(j, k, N) = 1 - \Sigma_{m = 1}^j\frac{(N-1)^{k - 1}}{N^{k - 1}}P(m - 1, k-1, N-1)$$