20.2: Addition and subtraction rules

As usual in mathematics, breaking a big problem into smaller parts is a useful strategy.

Theorem \(\PageIndex{1}\): Addition Rule

Assume \(U\) is a finite set.

1. If \(U = A_1 \sqcup A_2\text{,}\) then \(\vert U \vert = \vert A_1 \vert + \vert A_2 \vert\text{.}\)
2. If \(U = A_1 \cup A_2\text{,}\) then \(\vert U \vert = \vert A_1 \vert + \vert A_2 \vert - \vert A_1 \cap A_2 \vert\text{.}\)

Proof Idea.

After recalling the definition of disjoint union, Statement 1 should be obvious. To prove Statement 2, apply Statement 1 to the following disjoint unions:

\begin{align*} U & = A_1 \sqcup (A_2 \setminus A_1), & A_2 & = (A_2 \setminus A_1) \sqcup (A_1 \cap A_2). \end{align*}
Then combine the resulting equalities of cardinalities.

Remark \(\PageIndex{1}\)

Statement 1 of Theorem \(\PageIndex{1}\) can be extended to a disjoint union of any number of subsets.

Example \(\PageIndex{1}\): Counting by breaking into cases.

How many words of length \(3\) or less are there using alphabet \(\Sigma = \{ \alpha, \omega \}\text{?}\)

Solution

Write \(\Sigma ^{\ast}_{\le 3}\) to mean the set of words in alphabet \(\Sigma\) of length \(3\) or less. Then

\begin{equation*} \Sigma ^{\ast}_{\le 3} = \Sigma ^{\ast}_0 \sqcup \Sigma ^{\ast}_1 \sqcup \Sigma ^{\ast}_2 \sqcup \Sigma ^{\ast}_3 \text{,} \end{equation*}
so we can break into cases based on length and then apply the Addition Rule.

Count \(\Sigma ^{\ast}_0\).
There is only one word of length \(0\text{:}\) the empty word. So \(\vert \Sigma ^{\ast}_0 \vert = 1\text{.}\)

Count \(\Sigma ^{\ast}_1\).
There are only two words of length \(1\text{:}\) the single-letter words \(w_\alpha = \alpha\) and \(w_\omega = \omega\text{.}\) So \(\vert \Sigma ^{\ast}_1 \vert = 2\text{.}\)

Count \(\Sigma ^{\ast}_2\).
We can count be simply listing the elements:

\begin{equation*} \Sigma ^{\ast}_2 = \{ \alpha \alpha, \alpha \omega, \omega \alpha, \omega \omega \} \text{.} \end{equation*}
So \(\vert \Sigma ^{\ast}_2 \vert = 4\text{.}\)

Count \(\Sigma ^{\ast}_3\).
This time we will just use inductive reasoning. Each word in \(\Sigma ^{\ast}_2\) may be extended to a word in \(\Sigma ^{\ast}_3\) by appending either an \(\alpha\) or an \(\omega\) onto the end. So there must be twice as many words in \(\Sigma ^{\ast}_3\) as in \(\Sigma ^{\ast}_2\text{,}\) i.e. \(\vert \Sigma ^{\ast}_3 \vert = 8\text{.}\)

Total count.
Using the Addition Rule, we obtain the total by adding up our preliminary results:

\begin{equation*} \vert \Sigma ^{\ast}_{\le 3} \vert = 1 + 2 + 4 + 8 = 15 \text{.} \end{equation*}

Another common strategy in mathematics is to consider the opposite.

Theorem \(\PageIndex{2}\): Subtraction Rule.

Assume \(U\) is a finite set. For every subset \(A \subseteq U\text{,}\) we have \(\vert A \vert = \vert U \vert - \vert A^C \vert \text{.}\)

Proof Idea.

Since \(U = A \sqcup A^C \) is always true, simply apply Statement 1 of Theorem 20.2.1 to this disjoint union and rearrange to isolate \(\vert A \vert\text{.}\)

Example \(\PageIndex{2}\): Counting by counting the complement.

For alphabet \(\Sigma = \{a, b, c, \ldots, y, z\} \text{,}\) how many words in \(\Sigma ^{\ast}_2\) do not begin with the letter \(\mathrm{a}\text{?}\) It's much easier to count the number of words in \(\Sigma ^{\ast}_2\) that do begin with \(\mathrm{a}\text{,}\) as there are only \(26\) possibilities for the second letter.

Later in this chapter we will learn a rule that will allow us to easily calculate the total number of words in \(\Sigma ^{\ast}_2\) to be \(26^2\) (see Worked Example 20.3.6). Accepting this fact for the moment, we can then use the Subtraction Rule to compute

\begin{align*} \# \{ 2\text{-letter words not beginning with } \mathrm{a} \} & = \vert \Sigma ^{\ast}_2 \vert - \# \{ 2\text{-letter words beginning with } \mathrm{a} \}\\ & = 26^2 - 26 \\ & = 26 (26 - 1) \\ & = 26 \cdot 25 \text{.} \end{align*}