Arranging $n$ balls in $k$ bins so that $m$ consecutive bins are empty
Denote the sizes of the runs of empty bins as $x_1, \ldots, x_{n + 1}$. (Note that there are at most this many runs, so runs may be empty; i.e., $x_j = 0$.) Now, count the number of nonnegative integer solutions to
$$ x_1 + \cdots + x_{n + 1} = k - n $$
that have at least one $x_j \ge m$. This is equivalent to solving the problem.
To count this quantity, use the facts that:
- The number of nonnegative integer solutions to $$ x_1 + \cdots + x_k = n $$ is $$ \binom{n + k - 1}{k - 1}\text. $$ This is a simple stars and bars argument.
- The number of nonnegative integer solutions to $$ x_1 + \cdots + x_k = n $$ with each $x_j < c$ is $$ \binom{n + k - 1}{k - 1} - \sum_{i = 1}^{\lfloor n / {c} \rfloor} {(-1)}^{i + 1} \binom{k}{i}\binom{n - c i + k - 1}{k - 1}\text.\tag{*}\label{*} $$ To show (\ref{*}), recall the complementary form of the inclusion–exclusion principle. Namely, we can count the number of nonnegative integer solutions with each $x_j < c$ as $$ \begin{align} && \text{the number of all (unrestricted) solutions} \\ &-& \text{the number of solutions with one } x_j \geq c \\ &+& \text{the number of solutions with two } x_j \geq c \\ &-& \cdots \\ &{(-1)}^{\lfloor n / {c} \rfloor}& \text{the number of solutions with }\lfloor n / {c} \rfloor \text{ } x_j \geq c\text. \end{align} $$ Now, how do you count the number of solutions that have $i$-many $x_j \geq c$? It's quite simple; write those $x_j$ as $c + y_j$ (since we already know they're greater than or equal to $c$), and you already have a reduction to the stars and bars argument, but with $n' = n - c i$. This tells us that the number of solutions with $i$-many $x_j \geq c$ is $\binom{n - c i + k - 1}{k - 1}$. The $\binom{k}{i}$ factor counts the number of ways to have this scenario.
There is the possibility to calculate numerically the result with a rather simple recursive equation.
We will assume $m = 2$ in the following.
To simplify the notation, we will consider that $0$ represents the case "no ball" and $1$ the case "with a ball".
We note $f(k, n)$ the probability associated with $k$ and $n$.
We represent the set of possibilities as a graph.
We consider three cases for the first bins:
- 1 in the first bin. Probability $\frac{n}{k}$. The subgraph corresponds to $f(k-1, n-1)$
- 01 in the first 2 bins: Probability $\frac{k-n}{k} \times \frac{n}{k-1}$. The subgraph corresponds to $f(k-2, n-1)$
- 00 in the first 2 bins: Probability $\frac{k-n}{k} \times \frac{k-1-n}{k-1}$ -> we get the $m$ holes.
Then, we obtain, for $m = 2$
$$f(k,n) = \frac{n}{k} f(k-1, n-1) + \frac{n(k-n)}{k(k-1)} f(k-2, n-1) + \frac{(k-n)(k-1-n)}{k(k-1)}$$
We note in addition that $f() = 0$ if $k-n \le m-1$ and that $f() = 1$ if $n=0$ and $k \ge m$
This recursive formula can be generalised for higher values of $m$, although it becomes more difficult.
This is clearly not as satisfactory as a close form formula. However, it can be represented on a graph rather easily, and it is easy to program.
It may be used for secondary school students.
Note: the program gives $f(10, 7, 2) = \frac{8}{15}$
EDIT:
When I arrived at this point, I suspected something ...
Is there a much simpler solution ?
I thought having found a simple formula, it was a mistake ...
EDIT 2: C++ programme for $m = 2$
#include <iostream>
#include <iomanip>
double f2(int k, int n) { // m = 2
if ((k - n) <= 1) return 0.0;
if (n == 0) return 1.0;
double res = double ((k-n)*(k-1-n)) / (k*(k-1))
+ (double (n*(k-n)) / (k*(k-1))) * f2(k-2, n-1)
+ (double (n)/k) * f2(k-1, n-1);
return res;
}
int main() {
int k = 10;
int n = 7;
double prob = f2(k, n);
std::cout << "f = " << std::setprecision(12) << prob << "\n";
return 0;
}
EDIT 3: Display of a part of the graph.
"0:3/10" means that the line above corresponds to "0" (no ball), and that the corresponding probability is equal to 3/10. SB means "subgraph", and the near figure corresponds to the probability associated to this subgraph. This also illustrates the low efficiency of the scheme in terms of computation. However, again, it was not the goal of this proposal.
f(10,7)=8/15
/ \
/ \
/ \
0:3/10 1:7/10
SB:1/8 SB:f(9,6)=7/12
/ \ | \
/ \ | \
/ \ | \
0:2/9 1:7/9 0:1/3 1:2/3
SB:1.0 SB:f(8,6)=1/4 SB:13/28 SB:f(8,5)=9/14
/ \ | \ | \
/ \ | \ | \
| \
0:1/4 1:3/4
SB:1.0 SB:f(7,5)=2/7
/ \
/ \
This is supposed to be an integration to d125q's answer, as to better explain how to reach to the formula he gave, but it is too long for a comment.
You are placing $0$ or $1$ ball in every bin.
We are clearly speaking of undistiguishable balls.
While, speaking of consecutive bins, that implies that the bins
be distinguishable (i.e. labelled, i.e. aligned in a row).
Then your problem is equivalent to :
given all the binary strings of length $k$, with $n$ ones (and $n-k$ zeros), how many of them will contain one or more runs of consecutive zeros whose length is $m$ or greater ?
The number of binary strings of length $k$ and with $n$ ones is $\binom{k}{n}$.
So the complement of the above will be the number of strings where the length of each run of consecutive
zeros is less than $m$, and naturally, in a binary string we can exchange the zeros with the ones.
Now, to keep congruence with the precedent posts I am going to cite, let me change the formulation and the parameters of the problem with the following:
Consider a binary string with $s$ "$1$"'s and $m$ "$0$"'s in total. Let's put an additional (dummy) fixed $0$ at the start and at the end of the string.
We individuate as a run the consecutive $1$'s between two zeros, thereby including runs of null length.
With this scheme we have a fixed number of $m+1$ runs.
(refer also to the similar post).
Then, imposing that each run does not contain more than $r$ ones is equivalent to compute $$N_{\,b} (s,r,m+1) = \text{No}\text{. of solutions to}\;\left\{ \begin{gathered} 0 \leqslant \text{integer }x_{\,j} \leqslant r \hfill \\ x_{\,1} + x_{\,2} + \cdots + x_{\,m+1} = s \hfill \\ \end{gathered} \right.$$ which as explained in this other post is expressed as $$ N_b (s,r,m + 1)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s} {r}\, \leqslant \,m + 1} \right)} {\left( { - 1} \right)^k \left( \begin{gathered} m + 1 \\ k \\ \end{gathered} \right)\left( \begin{gathered} s + m - k\left( {r + 1} \right) \\ s - k\left( {r + 1} \right) \\ \end{gathered} \right)} $$ Note that by rewriting the binomial in the way shown above render the summation bounds implicit in the binomial, so that they can be omitted (that's why they are indicated in brackets), which is of great advantage in performing algebraic manipulations.
I think that an effective way to understand the above is by developing the polynomial $$ \eqalign{ & \underbrace {\left( {1 + x + x^{\,2} + \cdots + x^{\,r} } \right) \cdot \left( {1 + \cdots + x^{\,r} } \right) \cdot \; \cdots \; \cdot \left( {1 + \cdots + x^{\,r} } \right)}_{m\;times} = \cr & = \left( {{{1 - x^{\,r + 1} } \over {1 - x}}} \right) = \sum\limits_{0\, \le \,\,s\,\,\, \le \,m\,r} {N_b (s,r,m)\;x^{\,s} } \cr} $$ thereby having the o.g.f. in $s$, and from there easily getting the recursion $$ N_{\,b} (s,r,m + 1) = \sum\limits_{i\, = \,0}^r {N_{\,b} (s - i,r,m)} $$
Finally note that the $N_b$ are called "r-nomial coefficients" in OEIS: see e.g. Table A008287.