The Urn Problem with Indistinguishable Balls

Recall from the Combinations of Elements in Multisets that if $A$ is a multiset containing $n$ distinct elements $x_1, x_2, ..., x_n$ and the repetition numbers of each element are $\infty$ then the number of $k$-combinations of elements from $A$ is:

(1)

\begin{align} \quad \mathrm{number \: of \:} k-\mathrm{combinations} = \binom{k + n - 1}{k} = \binom{k + n - 1}{n - 1} \end{align}

We will now look further into this formula but in terms of urns and indistinguishable balls. Suppose that we have $n$ urns, say $u_1, u_2, ..., u_n$ and we want to place $k$ indistinguishable balls in these urns. Say that we place $b_1$ balls in $u_1$, $b_2$ balls in $u_2$, …, and $b_n$ balls in $u_n$. If we only have $k$ bals to place into these urns and the $b$'s represent the number of balls placed into each urn then we must have that:

(2)

\begin{align} \quad b_1 + b_2 + ... + b_n = k \end{align}

Since we have $n$ urns, we must break up the $k$ balls $n - 1$ times to form $n$ groups of balls (i.e., this is analogous to cutting a piece of paper once to get two pieces) which each correspond to the number of balls $b_1, b_2, ..., b_n$ in each of the urns. In the following theorem we see the relationship between $k$-combinations and the urn problem with indistinguishable balls.

Theorem 1: If $k$ indistinguishable balls are to be placed in $n$ distinguishable urns then $\binom{k + n - 1}{k} = \binom{k + n - 1}{n - 1}$ such combinations exist.

• Proof: Place $n - 1$ placeholders $*_1, *_2, ..., *_{n-1}$:

(3)

\begin{align} \quad \underbrace{\quad}_{b_1 \: \mathrm{many \: balls}} *_1 \underbrace{\quad}_{b_2 \: \mathrm{many \: balls}} *_2 \quad ... \quad *_{n-2} \underbrace{\quad}_{b_{n-1} \: \mathrm{many \: balls}}*_{n-1} \underbrace{\quad}_{b_n \: \mathrm{many \: balls}} \end{align}

• We must also place $k$ balls in between some order of the $n - 1$ positions chosen above where $b_1 + b_2 + ... + b_n = k$. There are thus $k + n - 1$ positions to place our objects (placeholders and balls). We must choose $k$ positions to place the balls which automatically selects the remaining $n - 1$ positions for our placeholders or we must choose $n - 1$ positions to place the placeholders which automatically selects the remaining $k$ positions for our balls. Therefore:

(4)

\begin{align} \quad \mathrm{number \: of \: combinations} = \binom{k + n - 1}{k} = \binom{k + n - 1}{n - 1} \quad \blacksquare \end{align}

Corollary 1: If $k$ distinguishable balls are to be placed in $n$ distinguishable urns such that each urn has at least $1$ ball then $\binom{k-1}{n-1}$ such combinations exist.

• Proof: We must first assume that there are at least equal or more balls to urns. Let $k \geq n$. Take $n$ of these balls and place $1$ into each urn. We then have $k - n$ balls remaining. We then decide to place $k - n$ balls amongst $n$ urns. We set up $n - 1$ placeholders as before and now place $k - n$ balls into $n$ urns. By Theorem 1 we have:

(5)

\begin{align} \quad \mathrm{number \: of \: combinations} = \binom{(k - n) + n - 1}{k - n} = \binom{k - 1}{k -n} = \binom{k - 1}{n- 1} \quad \blacksquare \end{align}

Corollary 2: If $k$ distinguishable balls are to be placed in $n$ distinguishable urns such that earn urn $u_i$ has at least $b_i$ balls for each $i \in \{1, 2, ..., n \}$ then $\binom{k - \sum_{i=1}^{n} b_i + n - 1}{n - 1}$ such combinations exist.

• Proof: Once again we must assume that there are at least $\sum_{i=1}^{n} b_i$ balls. Let $k \geq \sum_{i=1}^n b_i$. Place $b_1$ balls in $u_1$, $b_2$ balls in $u_2$, …, and $b_n$ balls in $u_n$. We therefore have $k - \sum_{i=1}^{n} b_i$ balls remaining. We set up $n - 1$ placeholders as before and now place $k - \sum_{i=1}^{n} b_i$ balls into $n$ turns. By Theorem 1 we have:

(6)

\begin{align} \quad \mathrm{number \: of \: combinations} = \binom{k - \sum_{i=1}^{n} b_i + n - 1}{k - \sum_{i=1}^{n} b_i } = \binom{k - \sum_{i=1}^{n} b_i + n - 1}{n - 1} \quad \blacksquare \end{align}