Skip to main content

Section 2.4 The Balls in Bins Formula

Consider the following example similar to Example 2.1.12.

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.

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.

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.

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

  1. Jasmine -- 3, Basmati -- 3, Arborio -- 1, Malagkit -- 3
  2. Koshihikari -- 10
  3. \(\displaystyle \bullet \ \bullet \mid \mid \bullet \bullet \bullet \bullet \bullet \ \bullet \mid \mid \bullet \ \bullet\)
  4. \(\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

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.

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

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

  1. How many different ways are there of distributing the apples?
  2. 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

\begin{equation*} x_1 + x_2 + \cdots + x_n = k\text{.} \end{equation*}
Exploration 2.4.1. Nonnegative integer solutions.

Consider the following equation:

\begin{equation} x_1 + x_2 + \cdots + x_5 = 10\text{,}\label{equation-nonnegative}\tag{2.4.1} \end{equation}

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.

(c)

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

\begin{equation*} x_1 + x_2 + \cdots + x_n = k\text{.} \end{equation*}

State explicitly what the balls and the bins are.

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{.}\)

Determine the number of integer solutions to the equation

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

such that:

  1. \(x_1, x_2, x_3, x_4\) are nonnegative.
  2. \(x_1 \geq 4\text{,}\) \(x_2 \geq 0\text{,}\) \(x_3 \geq 12\text{,}\) and \(x_4 \geq 9\text{.}\)
  3. \(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