# Balls into boxes with double restriction.

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.

Attempt:

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.

## 1 Answer

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

• 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}$ – user2820579 Jun 15 '18 at 20:40
• @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? – saulspatz Jun 15 '18 at 21:16
• 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. – user2820579 Jun 15 '18 at 22:54
• Then what is $N_d?$ The question says to build $N_d$ sub-boxes and choose $n$ of the sub-boxes. – saulspatz Jun 15 '18 at 23:02
• @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.$ – saulspatz Jun 15 '18 at 23:30