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