Suppose that you have $N$ boxes in which one can distribute $b_T\leq N$ indistinguishable balls such that there is at most one ball in every box.

Now from the $N$ boxes contruct $N_d$ boxes with $\nu=N/N_d$ boxes each. The question is to find the probability that, choosing $n$ boxes from the $N_d$, each box contains at least one ball.


The possible ways in which the $n$ boxes can get at least one ball is

$$ X=\binom{N_d}{n}\times \nu^n\times\binom{(v-1)n}{b_T - n}, $$

where each of the terms are:

  1. $\binom{N_d}{n}$ is the number of ways in which we can choose the $n$ non-empty boxes

  2. $\nu^n$ is the number of ways in which we can accomodate at least one ball in each box (Remember that from the $n$-boxes, each box has another $\nu$ boxes inside).

  3. $\binom{(v-1)n}{b_T - n}$ is the number of ways in which we can distribute the rest of the balls $b_T-n$ in the remaining allowed $(\nu-1)n$ sites.

The probability we are looking for is

$$ \frac{X}{\binom{N}{b_T}}. $$

EDIT: I just found an overcounting regarding the last two factors, but I don't know how to get rid off.


I believe I have a correct formula for the probability in the form of a sum involving binomial coefficients that I don't recognize. It may be possible to simplify it, but I can't see how.

First, let's reformulate the problem a little. Consider all the $N-$bit strings with exactly $b_T$ one bits. There are $\binom{N}{b_T}$ of these. We want to know in how many of these strings is each of the first $n$ non-overlapping $\nu-$ bit substrings not identically zero. (Clearly, there is no loss of generality in assuming that the $n$ "boxes" chosen are the first ones.)

It seems a lot easier to calculate the probability that at least one of the substrings is $0.$ There are $n$ ways to choose a substring, and then $\binom{N-\nu}{b_t}$ ways to distribute the one-bits to the rest of the string. However, we have to to subtract the strings with $2$ zero substrings, or $\binom{n}{2}\binom{N-2\nu}{b_t}$. Proceeding by inclusion-exclusion gives$$ \frac{\sum_{k=0}^n(-1)^k\binom{n}{k}\binom{N-k\nu}{b_T}}{\binom{N}{b_T}}$$

  • $\begingroup$ I think there is something amiss, because if the number of boxes $n$ is one, then the probability should be equal to 1, i.e. the numerator must equal $\binom{N}{b_T}$ $\endgroup$ – user2820579 Jun 15 '18 at 20:40
  • $\begingroup$ @user2820579 I don't see that at all. If $n=1$ we are choosing just one of the group of $\nu$ boxes aren't we? Why does there have to be a ball in one of those $\nu$ boxes? $\endgroup$ – saulspatz Jun 15 '18 at 21:16
  • $\begingroup$ I think I wasn't clear enough. We have $N$ boxes and from them the aim is to divide these into $n$ sub-boxes with the same number of boxes each. That is, if $n=1$, then we have one big box with $N$ (even) boxes in it. If $n=2$, then we have 2 sub-boxes, each one with $N/2$ boxes in it; etc. $\endgroup$ – user2820579 Jun 15 '18 at 22:54
  • $\begingroup$ Then what is $N_d?$ The question says to build $N_d$ sub-boxes and choose $n$ of the sub-boxes. $\endgroup$ – saulspatz Jun 15 '18 at 23:02
  • 1
    $\begingroup$ @user2820579 $N_d=1\implies\nu=N,$ so for $n=1,$ the formula does give $1.$ (It also gives $1$ for $n=0,$ which is vacuously correct.) I guess I should have stated that the formula is correct only for $0\le n\le N_d.$ $\endgroup$ – saulspatz Jun 15 '18 at 23:30

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.