2
$\begingroup$

Put $13$ identical balls in $8$ different holes. What is the probability that there is one empty hole?

For all the options it's easy. divide into $7$ partition, and - $\binom{8+13-1}{13}=\binom{20}{13}$

Now I want to calculate the options for one empty hole. What I did:

I left out one of the holes, and divided into $6$ partitions. This way there will be one empty hole for sure. In order to get ONLY one empty hole, I put in each hole 1 ball, and then I get: $\binom{12}{6}$

The probability:

$P(A)=\frac{\binom{12}{6}}{\binom{20}{13}}$

I'm not sure about this answer, because I checked only for $1$ specific hole. Should I multiple it by $8$?

$\endgroup$
5
  • 1
    $\begingroup$ Your calculation addresses the case where a specific hole is empty (and all the others have at least one ball). That's not what was asked. I would interpret the question as asking for "at least one empty hole", no? $\endgroup$
    – lulu
    Oct 31, 2017 at 10:17
  • $\begingroup$ I think it's only one hole is empty $\endgroup$
    – sheldonzy
    Oct 31, 2017 at 10:20
  • 1
    $\begingroup$ To clarify: "multiplying by $8$" works if you interpret the question as asking for "exactly one empty hole" but that's not how I would read the question. I agree the phrasing is ambiguous. $\endgroup$
    – lulu
    Oct 31, 2017 at 10:20
  • 1
    $\begingroup$ The problem "at least one empty hole" is considerably harder. You can do it with Inclusion-Exclusion...more information can be found, e.g., here $\endgroup$
    – lulu
    Oct 31, 2017 at 10:21
  • 1
    $\begingroup$ You are not told to compute the number of ways to distribute the $13$ balls in the $8$ holes. You are told to compute a certain probability. A priori there are $8^{13}$ equally like outcomes. You now have to count the favorable ones. $\endgroup$ Oct 31, 2017 at 10:48

1 Answer 1

1
$\begingroup$

The overall number of ways to put $n$ balls in $m$ holes corresponds to the number of weak compositions of $n$ into (exactly) $m$ parts.

A weak composition of $n$ is a $m$-tuple which is a integral solution to $$ \left\{ \matrix{ 0 \le x_{\,j} \hfill \cr x_{\,1} + x_{\,2} + \cdots + x_{\,m} = n \hfill \cr} \right. $$ and $x_k$ represents the number of balls in hole $k$, which can be even $0$.

The number of solutions is given by $$ N_{ \le \,m} (n,m) = \left( \matrix{ n + m - 1 \cr m - 1 \cr} \right) $$

The standard combinations are instead the $m$-tuples with strictly positive parts $$ \left\{ \matrix{ 1 \le y_{\,j} \hfill \cr y_{\,1} + y_{\,2} + \cdots + y_{\,m} = n \hfill \cr} \right. $$ corresponding to the case in which no hole is empty and their number is $$ N_0 (n,m) = \left( \matrix{ n - 1 \cr m - 1 \cr} \right) $$

Clearly we have $$ N_{ \le \,m} (n,m) = \left( \matrix{ n + m - 1 \cr m - 1 \cr} \right) = \sum\limits_{0\, \le \,k \le \,m} {\left( \matrix{ m \cr k \cr} \right)\left( \matrix{ n - 1 \cr m - k - 1 \cr} \right)} = \sum\limits_{0\, \le \,k \le \,m} {N_{k} \left( {n,m} \right)} $$ and $N_k$ represents the number of compositions with exactly $k$ zeros.

Now you have all the components to solve your problem, either under the meaning of "exactly one" or "at least one" empty hole .

Note

What said above, when translated into probability dividing by $N_{ \le \,m} (n,m)$, will assume that each composition is equiprobable.
That it the case for instance for points in a $m$-D space, uniformly distributed on the diagonal plane $x_1+x_2+\cdots +x_m=n$.

But randomly throwing $n$ balls into $m$ holes prefigures a different probability space.
Consider in fact the balls to be labelled according to the throwing sequence.
Then you have a total of $m^n$ equiprobable layouts of "balls-in-holes", differing by occupancy number or by the labeling of the occupants. However, in each hole, the balls will be arranged bottom-up (consider the hole diameter equal to that of the balls) in an increasing order.
So their disposition will correspond to the number of ways to partition the set ${1,2,\cdots ,n}$ into $j$ non-empty subsets (= occupied holes), multiplied by the falling factorial ${m^{\;\underline {\,j\,} } }$, the number of ways to place the $j$ subsets into $m$ places.
Thus $$ m^{\,\,n} = \sum\limits_{0\, \le \,j \le \,\min (n,m)} {\left\{ \matrix{ n \hfill \cr j \hfill \cr} \right\}m^{\;\underline {\,j\,} } } $$

So in this scheme the number of configurations with exactly $k$ empty holes is $$ N_{\,k} (n,m) = \left\{ \matrix{ n \cr m - k \cr} \right\}m^{\;\underline {\,m - k\,} } $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .