The Balls in Bins Formula

🔗

Section 2.4 The Balls in Bins Formula

🔗

Objectives

Derive the formulas for permutations and combinations with repetition (Balls in Bins Formula).
Given a counting problem, recognize which of the above techniques is applicable, and use it to solve the problem.

🔗

Consider the following example similar to Example 2.1.12.

🔗

Example 2.4.1. Multiple Choice, again.

A standardized multiple-choice test for high school students has 40 questions and 5 choices each (A to E). How many possible ways can the test be answered?

Solution

For each question, there are 5 options, so using Principle 2.1.9, there are a total of $5^{40}$ possible ways to complete the test.

🔗

The operation in Example 2.4.1 is called a permutation where repetition or replacement is allowed, since

The order in which the answers are picked matters (i.e. A-B-A is different from B-A-A); and
Answers can be repeated. Imagine a bag with five balls labeled A to E; for each question we draw a ball from the bag, record the answer, and put it back.

🔗

We formalize this in the next result.

🔗

Proposition 2.4.2. Permutations with repetition.

If repetition is allowed, the number of permutations of $k$ objects taken from a set of size $n$ is $n^{k} .$

🔗

Proof.

By Principle 2.1.9, since there are $n$ possibilities for each of the $k$ choices, the total number of ways to do so is $n^k\text{.}$

🔗

There is also a counterpart for combinations in which the order does not matter, which the next example illustrates.

🔗

Example 2.4.3. Rice Advice.

Ten participants are recruited to join a focus group discussion on rice, after which they are asked to indicate their preferred type of rice among the following options:

The participants gave their preferences anonymously so the researchers only know how many participants responded with each option. How many combinations of answers can the researchers obtain from the study?

Solution Since we are only concerned with the survey results, outcomes look like the following, where we only record how many respondents picked the corresponding option:

Arborio -- 3, Basmati -- 5, Jasmine -- 2

and

Koshihikari -- 9, Malagkit -- 1

are examples of possible outcomes; we need to count how many there are in total.

Note that we cannot simply take permutations and then divide by an overcounting factor since how much we overcount by depends on the actual distribution of answers.

Instead, we envision the process of collecting survey responses as placing balls into bins with labels `Arborio,' `Basmati,' and so on. (Imagine the participants physically placing their survey forms into one of five ballot boxes!)

For example, the outcome [Arborio -- 3, Basmati -- 5, Jasmine -- 2] corresponds to the following distribution of balls into bins:

$\bullet \bullet \bullet$	$\bullet \bullet \bullet \bullet \bullet$	$\bullet \bullet$
Arborio	Basmati	Jasmine	Koshihikari	Malagkit

This can also be represented concisely as the pattern

\begin{equation*} \bullet \bullet \bullet \mid \bullet \bullet \bullet \bullet \bullet \mid \bullet \, \bullet \mid \, \mid \end{equation*}

where the four vertical lines denote ‘dividers’ in between each pair of adjacent bins. Hence the problem of counting the number of possible outcomes is reduced to counting the number of arrangements of 10 $\bullet$ and 4 $\mid$ symbols, which is

\begin{equation*} \frac{14!}{10!\ 4!} = \binom{14}{4} \end{equation*}

by Proposition 2.2.10.

🔗

Checkpoint 2.4.4. Rice Advice Exercise.

Following Example 2.4.3, express each survey outcome as a pattern of dots $\bullet$ and bars $\mid\text{,}$ or vice-versa.

Jasmine -- 3, Basmati -- 3, Arborio -- 1, Malagkit -- 3
Koshihikari -- 10
$\displaystyle \bullet \ \bullet \mid \mid \bullet \bullet \bullet \bullet \bullet \ \bullet \mid \mid \bullet \ \bullet$
$\displaystyle \mid \mid \bullet \bullet \bullet \bullet \bullet \mid \bullet \mid \bullet \bullet \bullet \ \bullet$

Hint

Make sure the bins are in the right order!

🔗

This is called a combination where repetition is allowed, since

The order in which objects are picked does not matter (i.e., A-B-A is the same as B-A-A); and
Objects can be repeated.

🔗

As we saw in Example 2.4.3, the number of

k

-combinations taken from a set of size

n

when repetition is allowed is equal to the number of ways we can distribute

k

balls into

n

bins. This gives the following formula:

🔗

Video: The Balls in Bins Formula

🔗

Theorem 2.4.5. Balls in Bins.

If repetition is allowed, the number of combinations of $k$ objects taken from a set of size $n$ is

(\binom{n + k - 1}{k}) = (\binom{n + k - 1}{n - 1}) .

This is also equal to the number of ways one can distribute $k$ indistinguishable balls into $n$ bins.

🔗

Proof.

The total number of these combinations is equal to the number of ways to arrange $k$ bullets ($\bullet$ symbols; one for each object), and $n-1$ bars ($\mid$ symbols; to delineate bins):

\begin{equation*} \underbrace{\bullet \ \bullet \ \cdots \ \bullet}_{k \text{ copies}}\ \underbrace{\mid \ \mid \ \cdots \ \mid}_{n-1 \text{ copies}}\text{,} \end{equation*}

which is $\displaystyle\binom{k+n-1}{k}$ or $\binom{k+n-1}{n-1}$ by Proposition 2.2.10.

🔗

Remark 2.4.6. Stars and Bars.

Some textbooks refer to Theorem 2.4.5 as the Stars and Bars Formula, replacing the bullet symbols with stars, i.e.

\underset{k copies}{\underset{⏟}{⋆ ⋆ \dots ⋆}} \underset{n - 1 copies}{\underset{⏟}{∣ ∣ \dots ∣}} .

🔗

Checkpoint 2.4.7. Apples to Students.

A teacher has 20 apples that are to be handed out to 9 students.

How many different ways are there of distributing the apples?
How many different ways are there of distributing the apples so that each student receives at least one apple?

Hint

b. Give one apple to each student to begin, then distribute the rest.

🔗

A nice application of the Balls in Bins Formula is counting the number of nonnegative integer solutions to equations of the form

x_{1} + x_{2} + \dots + x_{n} = k .

🔗

Exploration 2.4.1. Nonnegative integer solutions.

Consider the following equation:

\begin{matrix} (2.4.1) & x_{1} + x_{2} + \dots + x_{5} = 10, \end{matrix}

and suppose we're interested in its nonnegative integer solutions.

🔗

(a)

Verify that $(x_{1}, x_{2}, x_{3}, x_{4}, x_{5}) = (3, 5, 2, 0, 0)$ is a nonnegative integer solution to (2.4.1). Then explain how we can view this solution as an assignment of balls into labeled bins.

🔗

(b)

Using Theorem 2.4.5, count the number of nonnegative integer solutions to (2.4.1).

🔗

(c)

Generalize the above argument to count the number of nonnegative integer solutions to

x_{1} + x_{2} + \dots + x_{n} = k .

State explicitly what the balls and the bins are.

🔗

Proposition 2.4.8. Nonnegative integer solutions.

The number of nonnegative integer solutions to $x_{1} + x_{2} + \dots + x_{n} = k$ is

(\binom{n + k - 1}{k}) .

🔗

Checkpoint 2.4.9. Apply Proposition 2.4.8.

Determine the number of integer solutions to the system

\begin{equation*} \begin{cases} x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 15 \amp \\ x_1, x_2, x_3, x_4, x_5, x_6 \geq 0 \amp \end{cases} \end{equation*}

Answer

$\displaystyle\binom{6+15-1}{15} = \binom{20}{15}\text{.}$

🔗

Checkpoint 2.4.10. Nonnegative integer solutions with additional constraints.

Determine the number of integer solutions to the equation

\begin{equation*} x_1 + x_2 + x_3 + x_4 = 77 \end{equation*}

such that:

$x_1, x_2, x_3, x_4$ are nonnegative.
$x_1 \geq 4\text{,}$ $x_2 \geq 0\text{,}$ $x_3 \geq 12\text{,}$ and $x_4 \geq 9\text{.}$
$0 \leq x_1 \leq 30\text{,}$ and $x_2, x_3, x_4 \geq 0\text{.}$

Hint 1

b. Look at part (b) of Checkpoint 2.4.7.

Hint 2

c. Solve the problem with $x_1 \geq 31$ first then subtract from part (a).

Answer

a. $\displaystyle\binom{80}{77}\text{.}$

b. $\displaystyle\binom{55}{52}\text{.}$ (Solution below.)

c. $\displaystyle\binom{80}{77} - \binom{49}{46}\text{.}$

🔗

Solutions Solutions to Selected Checkpoints

Checkpoint 2.4.7. Apples to Students.

Solution

Checkpoint 2.4.10. Nonnegative integer solutions with additional constraints.

Solution