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*}$$