Skip to main content

Section 7.6 The Addition and Subtraction Rules; Inclusion-Exclusion

Let's imagine that OAFC intends to open at most three (and at least one) mobile health clinics in separate municipalities within Walworth County. How many different ways could they do this?

Solution.

First, note that order does not matter in choosing clinic locations, as in Example 7.5.5, so combinations will probably be involved. Next, the words at most are crucial, and suggest a way of breaking up our problem. Assuming that we will place at least one clinic, we can either place one, or two, or three clinic locations in the \(30\) municipalities. There is no overlap in these different categories (since, for example, a way of placing three clinics will necessarily be distinct from a way of placing two clinics). Thus, we can simply count the number of ways to place one, two, or three clinics, and then add them up! As in Example 7.5.5, there are \(30C3\) ways of placing three clinics. Similarly, there are \(30C2\) ways of placing four clinics, and \(30C1\) ways of placing one clinic. Thus there are a total of

\begin{equation*} 30C1+30C2+30C3 \end{equation*}
\begin{equation*} =\frac{30!}{(30-1)!*1!}+\frac{30!}{(30-2)!*2!}+\frac{30!}{(30-3)!*3!} \end{equation*}
\begin{equation*} =4525 \end{equation*}

ways.

Example 7.6.1 illustrates the addition rule:

Addition rule.

Suppose that a procedure may be done in either \(n_1\) ways or \(n_2\) ways, and that there is no overlap between the ways. Then there are \(n_1+n_2\) ways of completing the procedure.

More generally, if there are \(m\) types of ways of completing a procedure, with \(n_i\) ways of completing the procedure using the \(i^\text{th}\) type of way, and no overlap between any of the types, then there are \(n_1+n_2+n_3+\cdots+n_m\) ways of completing the procedure.

But what happens if there is overlap in the types of ways?

Suppose that the \(7\) northernmost municipalities of Walworth county (Whitewater city, Whitewater town, La Grange town, Troy town, Mukwonago village, East Troy town, East Troy village) as well as the \(9\) easternmost municipalities of Walworth county (Mukwonago village, East Troy town, East Troy village, Spring Prairie town, Burlington city, Lyons town, Bloomfield town, Bloomfield village, and Genoa City village) have access to medical resources in neighoring counties, so that OAFC intends to remove them from consideration. How many different municipalities must be removed from consideration? If OAFC intends to place 2 clinics in separate remaining municipalities, how many possibilities for clinic placements are there?

Solution.

Note that there are exactly three municipalities which are both northernmost and easternmost (those being Mukwonago village, East Troy town, and East Troy village). Thus there are

\begin{equation*} 9+7-3=13 \end{equation*}

municipalities that are either northernmost or easternmost, and this is the number to remove from consideration. Thus there are \(30-13=17\) municipalities to consider for clinic placement. Since order does not matter in choosing clinic locations, as in Example 7.5.5, the number of possible ways to place clinics is

\begin{equation*} 17C2=136\text{.} \end{equation*}

Example 7.6.2 illustrates inclusion-exclusion, which is closeWindow()ly related to the subtraction rule:

Subtraction rule.

Suppose that a procedure may be done in \(n\) total ways, \(m\) of which are not allowed. Then there are \(n-m\) allowable ways of completing the procedure.

Inclusion-exclusion.

Suppose that a procedure may be done in \(n_1\) ways or \(n_2\) ways, and that there are exactly \(n_3\) ways which are counted in both categories. Then there are \(n_1+n_2-n_3\) ways of completing the procedure.