Skip to main content

Section 7.5 The Product and Division Rules; Permutations and Combinations

Open Arms Free Clinic 1  (OAFC) in Elkhorn, Wisconsin serves uninsured residents living below \(200\%\) of the poverty line in Walworth County, Wisconsin. This clinic and the geographical area they serve will be a running example for us.

The map below shows the \(30\) municipalities in Walworth County. Later, we will remove the municipality of Burlington City from our analysis since it barely overlaps the county and there was no data for it available for any of the variables we will consider.

Figure 7.5.1. A map of the \(30\) municipalities in Walworth County, WI. Image Description 1.

Subsection 7.5.1 The product rule and permutations

Consider the following motivating example.

Let's imagine that OAFC intends to open three mobile health clinics in separate municipalities within Walworth County, each one staffed by a different volunteer. How many different ways could they do this?

Solution.

Let's label the clinics \(A\text{,}\) \(B\text{,}\) and \(C\) according to the volunteer staffing them, and imagine placing the clinics in that order. For clinic \(A\text{,}\) we have \(30\) municipalities to choose from. For clinic \(B\text{,}\) we have \(21\) choices since we already used one. Thus there are \(30*29\) ways of placing clinic \(A\text{,}\) and then clinic \(B\text{.}\) Then, there are \(28\) choices for the placement of clinic \(C\) (since we already used two). Thus there are \(30*29*28=24360\) ways of placing the clinics.

This example illustrates a counting principle called the product rule:

Product rule.

Suppose that a procedure can be broken down into a sequence of \(n\) tasks. The first task can be done in \(m_1\) ways, the second task can be done in \(m_2\) ways after doing the first task, the third task can be done in \(m_3\) ways after doing the first two tasks, and in general the \(i^{\text{th}}\) task can be done in \(m_i\) ways after doing all the tasks preceding it. Then there are

\begin{equation*} m_1*m_2*m_3*\cdots*m_n \end{equation*}

ways to do the procedure.

The form that the product rule takes in Example 7.5.2 comes up so often that it has its own notation, the factorial.

Factorials.

For a positive integer \(n\text{,}\) we write \(n!\) to stand for the product of the numbers \(1\) through \(n\text{.}\) That is,

\begin{equation*} n!=n*(n-1)*(n-2)*\cdots *3*2*1\text{.} \end{equation*}

In order to make common formulas involving factorials work in edge cases, we also define \(0!=1\text{.}\)

Find \(n!\) for \(n=0,1,2,3,4,5\text{.}\)

Solution.

\(0!=1\) by convention.

\(1!=1\text{.}\)

\(2!=2*1=2\text{.}\)

\(3!=3*2*1=6\text{.}\)

\(4!=4*3*2*1=24\text{.}\)

\(5!=5*4!=120\text{.}\)

A permutation is a way of creating a sequence of labeled objects from some larger collection when replacement is not allowed. The most common formula for counting permutations uses factorials.

Permutations.

Suppose \(n\) and \(m\) are nonnegative integers with \(m\leq n\text{.}\) Then the number of ways to place \(m\) labeled objects in sequence from a larger collection of \(n\) objects is

\begin{equation*} \frac{n!}{(n-m)!}\text{.} \end{equation*}

We call these ways permutations and write this number as \(nPm\text{,}\) that is,

\begin{equation*} nPm=\frac{n!}{(n-m)!}\text{.} \end{equation*}

Another notation which is commonly used in place of \(nPm\) is \(P(n,m)\text{.}\)

Let's recall Example 7.5.2 in which OAFC intended to open three mobile clinics in separate municipalities within Walworth County, each one staffed by a different volunteer. We saw that the number of ways to do this was \(30*29*28\text{.}\) Explain this answer in terms of permutations.

Solution.

We can think of the municipalities as a collection of objects (\(n=30\)) and note that a sequence of three municipalities (a permutation) exactly corresponds to a way of staffing three clinic locations. Thus we can imagine the municipalities as a large collection of objects from which we must count the number of permutations of size \(3\text{,}\) or \(30P3\text{.}\) By the formula above,

\begin{equation*} 30P3=\frac{30!}{(30-3)!}=\frac{30!}{27!} \end{equation*}
\begin{equation*} =\frac{30*29*28*27*26*25*24*23\cdots*3*2*1}{27*26*25*\cdots*3*2*1} \end{equation*}
\begin{equation*} =30*29*28\text{,} \end{equation*}

the same as our answer. Note the large amount of cancellation in the numerator and denominator arising from the factorial!

Subsection 7.5.2 The division rule and combinations

Next, consider the following variant of Example 7.5.2:

Suppose now that OAFC is interested only in the possible clinic locations, and is not concerned with staffing at the moment. In other words, they simply intend to open three mobile health clinics in separate municipalities within Walworth County. How many different ways could they do this?

Solution.

Let's again label the clinics \(A\text{,}\) \(B\text{,}\) and \(C\text{.}\) As in Example 7.5.2, there are \(30P3=30*29*28=24360\) ways of placing the clinics with their labels. What has changed in the current example? In short, we no longer care about the labels of the clinics. As in Figure 7.5.6, a placement in the same municipalities which only switches the labels on clinics \(A\) and \(B\) should be considered equivalent to the original. The question becomes "How many placements are equivalent to a given placement?" And the answer to this is \(3!=3*2*1=120\text{,}\) since this number represents the number of ways we can label the clinics for this specific choice of \(3\) municipalities. Now, since each of the \(24360\) clinic placements has \(5\) other equivalent placements, we can find the answer to our question by dividing \(24360\) by \(6\text{.}\) In other words, there are

\begin{equation*} \frac{30*29*28}{3*2*1}=\frac{24360}{6}=4060 \end{equation*}

ways of placing the clinics in this way.

Figure 7.5.6. Two equivalent clinic placements. Image Description 2.

This example illustrates a counting principle called the division rule:

Division rule.

Suppose that there are \(n\) ways of completing a procedure, but that those ways are not unique in the sense that each of the them is equivalent to \(m\) others including itself. Then the task can be done in \(n/m\) unique ways.

A combination is a way of choosing a subset of labeled objects from some larger collection when replacement is not allowed. The formula for the number of combinations comes from the division rule.

Combinations.

Suppose \(n\) and \(m\) are nonnegative integers with \(m\leq n\text{.}\) Then the number of ways to choose \(m\) labeled objects in sequence from a larger collection of \(n\) objects is

\begin{equation*} \frac{n!}{(n-m)!m!}\text{.} \end{equation*}

We call these ways combinations and write this number as \(nCm\text{,}\) that is,

\begin{equation*} nCm=\frac{n!}{(n-m)!m!}\text{.} \end{equation*}

Another notation which is commonly used in place of \(nCm\) is \(\binom{n}{m}\text{.}\) Some authors also write \(C(n,m)\text{.}\) The numbers that arise in this way are sometimes called binomial coefficients. There is a good reason for this which you may enjoy exploring [7.12.1.131]. Some of the many beautiful patterns that can be seen in these numbers are explored in the exercises.

Let's recall Example 7.5.5 in which OAFC intended to open three mobile clinics in separate municipalities within Walworth County. We saw that the number of ways to do this was

\begin{equation*} \frac{30*29*28}{3*2*1}\text{.} \end{equation*}

Explain this answer in terms of combinations.

Solution.

We can think of the municipalities as a collection of objects (\(n=30\)) and note that a choice of three municipalities (a combination), where order does not matter, is exactly what we are after counting. Thus we can imagine the municipalities as a large collection of objects from which we must count the number of combinations of size \(3\text{,}\) or \(30C3\text{.}\) By the formula above,

\begin{equation*} 30C3=\frac{30!}{(30-3)!*3!}=\frac{30!}{27!*3!} \end{equation*}
\begin{equation*} =\frac{30*29*28*27*26*25*24*23\cdots*3*2*1}{(27*26*25*\cdots*3*2*1)*(3*2*1)} \end{equation*}
\begin{equation*} =\frac{30*29*28}{3*2}\text{,} \end{equation*}

the same as our answer.

Warning: When plugging an expression such as \(\frac{30*29*28}{3*2}\) into your calculator, be careful to put the product in the denominator (\(3*2\)) in parenthesis (i.e. you should type \(30*29*28/(3*2)\)). If you type \(30*29*28/3*2\) the calculator will interpret the \(2\) as being in the numerator. This is because multiplications and divisions are done from left to right, and both have equal priority under the usual conventions.

openarmsfreeclinic.com