Balls into boxes with double restriction.

130 Views Asked by At

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

There are 1 best solutions below

6
On

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