2
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ it now appears you have two valid answers. Take your pick of which one to use :) $\endgroup$ Mar 27, 2019 at 15:49
  • $\begingroup$ Sorry for not getting back in touch quicker! Worked my way through both and was happy to understand the different approaches suggested by everyone :) I'm not an expert at combinatorics by any means, but I'm going places! Thanks for your time everyone :) $\endgroup$
    – AlexM
    Mar 28, 2019 at 16:09
  • $\begingroup$ if this solves your problem, maybe mark one of the solutions as your answer? $\endgroup$ Mar 28, 2019 at 16:24

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Hi, thanks for the suggestion! I'm following along but have a bit of trouble understanding 'There are j balls to place in box Br', and consequently the apparition of j*(j-1)*...*(j-m) in the number of ways of placing them. $\endgroup$
    – AlexM
    Mar 26, 2019 at 17:52
  • $\begingroup$ Another concern I have is that among the (n-m) remaining balls after we have placed m balls alone in boxes, some are black. Distributing all of them randomly could result in some of those being left alone in boxes, no? $\endgroup$
    – AlexM
    Mar 26, 2019 at 18:01
  • $\begingroup$ Correct. That is where Inclusion/Exclusion comes into play. Here is my first Google search result that describes it and how it works: cs.sfu.ca/~ggbaker/zju/math/pie.html $\endgroup$ Mar 26, 2019 at 18:37
  • $\begingroup$ Note that I point out that $B_r\cap B_s$ may be nonempty. The Inclusion/Exclusion principle essentially says, consider the problem without restriction. Subtract off all of the cases where at least one box has a lone black ball. However, each case where two boxes have a lone black ball are being removed twice. So, add back in all of the cases where at least two boxes have a lone black ball. But, now we added in all of the cases where three boxes have a lone black ball multiple times, so we subtract them off, etc. $\endgroup$ Mar 26, 2019 at 18:44
  • $\begingroup$ And when I say "There are $j$ balls to place in box $B_r$", that is because you have $j$ distinguishable black balls. So, you have to choose the specific black ball you are placing in there. When you have $m+1$ boxes and you are placing a single black ball in each, there are $j$ balls you can place in the first box, $j-1$ balls for the second box, ..., $j-m$ balls for the $(m+1)$st box. $\endgroup$ Mar 26, 2019 at 18:46
1
$\begingroup$

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)$$

$\endgroup$
2
  • $\begingroup$ @InterstellarProbe, as far as I understand, it was me, who made a mistake. It should have been $P(m - 1, k - 1, N - 1)$ instead of $P(m - 1, k - m, N - 1)$, as the only ball removed is the $m$-th one. $\endgroup$ Mar 27, 2019 at 15:28
  • $\begingroup$ that looks much better. Now I get the same result either approach. $\endgroup$ Mar 27, 2019 at 15:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .