5
$\begingroup$

We have $n$ distinct balls ($n>7$) and want to randomly (and independently) distribute them into $N$ distinct boxes ($N>n$) which are placed one next to the other.

a) What is the probability that all balls are placed in consecutive boxes?

b) What is the probability that all balls are placed in consecutive boxes and balls with number $1$, $4$ and $7$ are also placed in consecutive boxes?

I am not sure but I will try:

a) There is a block of n balls which must be placed in one of the $N-n+1$ gaps formed if we arrange the boxes and fill $n$ consecutive of them. So there are $N-n+1$ places place this block. The $n$ balls in the block can be arranged in $n!$ ways. Also the N boxes can be arranged in $N!$ ways. So all in all we have $n!N!(N-n+1)$.

b) Again we have $N!$ ways to arrange the boxes but the balls can be arranged in $(n-3)!$ ways, right?

I don't know what is the total number of ways to place all balls in the boxes - plus that I see no restriction regarding the number of balls per box.

Any help?

$\endgroup$
  • 1
    $\begingroup$ Do the $n$ balls have to go into $n$ different consecutive boxes, or could they in theory go into any number $k$ of consecutive boxes ($1 \le k \le n$), which would for $k<n$ imply that some boxes contain more than 1 ball? The boxes are placed in a line, so there is a first and last box? Or is it a circle, or something else? $\endgroup$ – Ingix Aug 20 at 17:30
  • $\begingroup$ @Ingix This is not specified in the problem. I would assume that each box contains only 1 ball, but I am not sure. As for the second part of your question, the boxes are placed in a line. $\endgroup$ – Pradeep Suny Aug 20 at 18:15
2
$\begingroup$

In this answer (only on a)) a subset $S\subseteq\left\{ 1,\dots,N\right\} $ gets the label consecutive if no $k\in\left\{ 1,\dots,N\right\} $ exists with $k\notin S$, $\left\{ 1,\dots,k-1\right\} \cap S\neq\varnothing$ and $\left\{ k+1,\dots,N\right\} \cap S\neq\varnothing$.

Let $\hat{S}$ denote the random subset of $\left\{ 1,\dots,N\right\} $ determined by: $$s\in\hat{S}\iff\text{at least one ball is placed in box }s$$


If every box can contain at most one ball then $\hat{S}$ will be a subset of cardinality $n$ and there are $\binom{N}{n}$ equiprobable candidates of which $N-n+1$ are consecutive.

This leads to: $$P\left(\hat{S}\text{ is consecutive}\right)=\left(N-n+1\right)\binom{N}{n}^{-1}$$


If every box can contain more than one ball then we will use the following nice formula: $$P\left(\hat{S}=S\right)=\sum_{T\subseteq S}P\left(\hat{S}\subseteq T\right)\left(-1\right)^{\left|S\right|-\left|T\right|}\tag1$$

This formula arises if we first write: $$P\left(\hat{S}=S\right)=P\left(\hat{S}\subseteq S\right)-P\left(\bigcup_{s\in S}\left\{ \hat{S}\subseteq S-\left\{ s\right\} \right\} \right)$$ and then apply the principle of inclusion/exclusion on the second term on RHS.

In our situation $P\left(\hat{S}\subseteq T\right)=N^{-n}\left|T\right|^{n}$ and $\binom{\left|S\right|}{i}$ subsets $T\subseteq S$ have cardinality $i$.

Based on that we can further expand $\left(1\right)$ with:

$$P\left(\hat{S}=S\right)=\cdots=N^{-n}\sum_{T\subseteq S}\left|T\right|^{n}\left(-1\right)^{\left|S\right|-\left|T\right|}=N^{-n}\sum_{i=1}^{\left|S\right|}\binom{\left|S\right|}{i}i^{n}\left(-1\right)^{\left|S\right|-i}$$

If we denote $\mathcal{C}_{k}$ as the collection of consecutive subsets of $\left\{ 1,\dots,N\right\} $ that have exactly $k$ elements then $\left|\mathcal{C}_{k}\right|=N-k+1$ so that by symmetry: $$P\left(\hat{S}\text{ is consecutive}\right)=\sum_{k=1}^{n}P\left(\hat{S}\in\mathcal{C}_{k}\right)=\sum_{k=1}^{n}\left(N-k+1\right)P\left(\hat{S}=\left\{ 1,\dots,k\right\} \right)=$$$$N^{-n}\sum_{k=1}^{n}\left(N-k+1\right)\sum_{i=1}^{k}\binom{k}{i}i^{n}\left(-1\right)^{k-i}$$

$\endgroup$
  • $\begingroup$ Though we use slightly different indices, our formulas agree. $\endgroup$ – Ingix Aug 21 at 13:02
  • $\begingroup$ @Ingix Indeed. Always nice to be confirmed. $\endgroup$ – drhab Aug 21 at 13:44
1
$\begingroup$

I'm going to answer the problem based on my interpretation(s). I try to state them as clearly as possible. I'm only dealing with part a) of the problem.

The boxes will be numbered from left to right as $1$ to $N$. They are already distinguished by their position and thus their assigned number.

The balls will be numbered from $1$ to $n$.

Interpretation 1: Each box can contain at most 1 ball.

That goes against the independent distribution of balls, but is mathemaically the easier interpretation.

How many possible distributions are there?

Well, ball $1$ can go into any of $N$ boxes, then ball $2$ can go into any of the remaining empty $N-1$ boxes, a.s.o. In each step it doesn't matter which boxes were already filled with a ball before, the number of empty boxes decreases by $1$.

That makes the number of possible distribution equal to

$$\text{#Possible}_1 = N(N-1)\ldots(N-n+1) = {N \choose n}n!$$

How many 'good' distributions are there, that means where all balls are in consecutive boxes? Since each box can hold at most 1 ball, that means those boxes must be exactly $n$ boxes forming a continuous sequence of boxes.

In other words, the box numbers with balls must form a sequence of $n$ consecutive integers, all in the range $1$ to $N$. There are $N-n+1$ such sequences ($N-n+1$ is the largest possible first entry such that the last entry is still $\le N$).

If we have fixed one such sequence (of integers or, equivalently, of boxes), there are $n!$ possibilities to distribute the $n$ balls into those boxes, just the usual way to count permutations. That means:

$$\text{#Good}_1 = n!(N-n+1)$$

Together this means the probability to get the desired distribution of balls is

$$\text{Pr}_1=\frac{\text{#Good}_1}{\text{#Possible}_1} = \frac{n!(N-n+1)}{{N \choose n}n!} = \frac{N-n+1}{N \choose n}$$

Note that the $n!$ could be cancelled from both enumerator and denominator. That corresponds to the fact that under the given interpretation, the balls always end up in different boxes, so continue to be always distinguishable even after distribution. A similar argument can be made without distinguishing the balls under this interpretation, leading to the same result.

Interpretation 2: Each box can contain any number of balls.

This is more in line with how I would interpret the question, mostly because it can make the choice where a ball goes really independent from where any other ball goes. Unfortunately, the math becomes more complicated as in interpretation 1.

How many possible distributions are there?

Well, ball $1$ can go into any of the $N$ boxes. Then ball $2$ can again go into any of the $N$ boxes, a.s.o. That makes the number of possible distributions

$$\text{#Possible}_2 = N^n$$

How many 'good' distributions are there, that means where all balls are inn consecutive boxes? In difference to interpretation $1$, the number of boxes that contain all the balls can now be any number from $1$ to $n$. I'll it it $l$.

So given that number $l, 1\le l \le n$, how many sets of $l$ boxes are there that form a consecutive sequence`of numbers? We answered that question already in interpretation $1$, just for the special case of $l=n$. The answer here is obtaind the same way:

There are $N-l+1$ sequences of consecutive numbers/boxes of length $l$ in the range from $1$ to $N$.

For ball distribution is only matters that there are $l$ consecutive boxes, there is no difference if they are number $3,4,\ldots,l+2$ or $1001,1002,\ldots,1000+l$. So what we need to find is the following number:

$$\text{Dist}(n,l)=\text{number of ways to distribute $n$ balls into $l$ boxes,} \textbf{ such that all boxes contain at least $1$ ball}$$

Notice the bold part. If you just count the number of ways to distribute $n$ balls into $l$ boxes, you overcount. That is because, in a simple example for $l=3,n=3$, this also counts the distribution where balls $1$ and $3$ go into box $1$, and ball $2$ goes into box $3$. That, however, is not a 'good' distribution for the question at hand, because the balls are not in consecutive boxes, they are in boxes $1$ and $3$.

From the above, we see that

$$\text{#Good}_2 = \sum_{l=1}^n(N-l+1)\text{Dist}(n,l)$$

Unfortunately, there does not seem to be a simple formula for Dist$(n,l)$. The method I use is called Principle of Inclusion and Exclusion (wikpedia link). You can read more about it in the link, but the basic idea is as follows:

We know how many ways there are to distribute $n$ balls in $r$ boxes: $r^n$.

So in determining the number of ways to distribute $n$ balls into $l$ boxes, such that all boxes contain at least $1$ ball, we start with determining the number of ways to distribute $n$ balls into $l$ boxes ($l^n$) and try to take away all those distributions that don't fit our additional condition.

If a distribution does not not contain a ball in each box, then there must be a box that is empty. Let's count how many distributions of $n$ balls into $l$ boxes are there that leave the first box empty? Well, that's just a fancy way to ask "How many ways are there to distribute $n$ balls into the remaining $l-1$ boxes?" The answer to that is $(l-1)^n$.

Also note that this answer does not depend on the fact that the first box was empty, it could have been any of the $l$ boxes. So, when we subtract this value $(l-1)^n$ $l$ times from the initial value $l^n$, we get

$$\text{Dist2}(n,l)=l^n - l (l-1)^n$$

We subtract it $l$ times, because any of the $l$ boxes could have been left empty. Now it seems that this is already our number Dist$(n,l)$, but this is not true. See, we now overcounted the number of distributions to remove, because all the distributions that leave box 1 and box 2 empty have been substracted twice, once when removing distributions that leave box 1 empty and a second time when removing distributions that leave box 2 empty!

This is a complicated procedure to make the counting go right, and that is what the mentioned Principle of Inclusion and Exclusion is for. If you go to wikipedia to the section called "Statement", there are a bunch of sets $A_i$ that make up the meat of the formula.

In our case $A_i$ is the set distributions of $n$ distinguishable balls into $l$ boxes that leave box $i$ empty, $1 \le i \le$ l.

The good news is that calculating the number of elements in $A_{i_1} \cap A_{i_2} \ldots \cap A_{i_k}$ is easy if all the indices are different. It just means to ask "How many ways are there to distribute $n$ balls into $l-k$ boxes?", which we can answer as $(l-k)^n$. There are $l-k$ boxes because we 'forbade' $k$ boxes, those with indices $i_1,i_2,\ldots,i_k$. Now, there are $l \choose k$ ways to choose such indices, so we finally get the following formula

$$\text{Dist}(n,l)=\sum_{k=0}^l(-1)^k{l \choose k}(l-k)^n$$

The terms for $k=0$ and $k=1$ are the ones we determined already for Dist2$(n,l)$. I'm not sure if there is a closed formula for Dist$(n,l)$, but I don't think so.

Putting all the parts together, we get

$$\text{#Good}_2 = \sum_{l=1}^n(N-l+1)\sum_{k=0}^l(-1)^k{l \choose k}(l-k)^n$$

and finally

$$\text{Pr}_2=\frac{\text{#Good}_2}{\text{#Possible}_2} = \frac{\sum_{l=1}^n(N-l+1)\sum_{k=0}^l(-1)^k{l \choose k}(l-k)^n}{N^n}$$

$\endgroup$
  • $\begingroup$ +1 A closed form for Dist(n,l) does indeed not exist. $\endgroup$ – drhab Aug 21 at 12:12

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.