Section 20.2 Addition and subtraction rules
As usual in mathematics, breaking a big problem into smaller parts is a useful strategy.
Theorem 20.2.1. Addition Rule.
Assume \(U\) is a finite set.
If \(U = A_1 \disjunion A_2\text{,}\) then \(\card{U} = \card{A_1} + \card{A_2}\text{.}\)
If \(U = A_1 \union A_2\text{,}\) then \(\card{U} = \card{A_1} + \card{A_2} - \card{A_1 \intersection A_2}\text{.}\)
Proof idea.
\begin{align*}
U \amp = A_1 \disjunion {(A_2 \relcmplmnt A_1)}, \amp
A_2 \amp = {(A_2 \relcmplmnt A_1)} \disjunion {(A_1 \intersection A_2)}.
\end{align*}
Then combine the resulting equalities of cardinalities.
Worked Example 20.2.3. Counting by breaking into cases.
How many words of length \(3\) or less are there using alphabet \(\Sigma = \{ \alpha, \omega \}\text{?}\)
Solution.
Write \(\leset{\words{\Sigma}}{3}\) to mean the set of words in alphabet \(\Sigma\) of length \(3\) or less. Then
\begin{equation*}
\leset{\words{\Sigma}}{3} = \words{\Sigma}_0 \disjunion \words{\Sigma}_1 \disjunion \words{\Sigma}_2 \disjunion \words{\Sigma}_3 \text{,}
\end{equation*}
so we can break into cases based on length and then apply the
Addition Rule.
Count \(\words{\Sigma}_0\).
There is only one word of length \(0\text{:}\) the empty word. So \(\card{\words{\Sigma}_0} = 1\text{.}\)
Count \(\words{\Sigma}_1\).
There are only two words of length \(1\text{:}\) the single-letter words \(w_\alpha = \alpha\) and \(w_\omega = \omega\text{.}\) So \(\card{\words{\Sigma}_1} = 2\text{.}\)
Count \(\words{\Sigma}_2\).
We can count be simply listing the elements:
\begin{equation*}
\words{\Sigma}_2 = \{ \alpha \alpha, \alpha \omega, \omega \alpha, \omega \omega \} \text{.}
\end{equation*}
So \(\card{\words{\Sigma}_2} = 4\text{.}\)
Count \(\words{\Sigma}_3\).
This time we will just use inductive reasoning. Each word in \(\words{\Sigma}_2\) may be extended to a word in \(\words{\Sigma}_3\) by appending either an \(\alpha\) or an \(\omega\) onto the end. So there must be twice as many words in \(\words{\Sigma}_3\) as in \(\words{\Sigma}_2\text{,}\) i.e. \(\card{\words{\Sigma}_3} = 8\text{.}\)
Total count.
Using the
Addition Rule, we obtain the total by adding up our preliminary results:
\begin{equation*}
\card{\leset{\words{\Sigma}}{3}} = 1 + 2 + 4 + 8 = 15 \text{.}
\end{equation*}
Another common strategy in mathematics is to consider the opposite.
Theorem 20.2.4. Subtraction Rule.
Assume \(U\) is a finite set. For every subset \(A \subseteq U\text{,}\) we have \(\card{A} = \card{U} - \card{\cmplmnt{A}} \text{.}\)
Proof idea.
Since
\(U = A \disjunion \cmplmnt{A} \) is always true, simply apply
Statement 1 of
Theorem 20.2.1 to this disjoint union and rearrange to isolate
\(\card{A}\text{.}\)
Example 20.2.5. Counting by counting the complement.
For alphabet \(\Sigma = \EngAlphabet\text{,}\) how many words in \(\words{\Sigma}_2\) do not begin with the letter \(\mathrm{a}\text{?}\) It’s much easier to count the number of words in \(\words{\Sigma}_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
\(\words{\Sigma}_2\) to be
\(26^2\) (see
Worked Example 20.3.10). Accepting this fact for the moment, we can then use the
Subtraction Rule to compute
\begin{align*}
\ncardop \{ 2\text{-letter words not beginning with } \mathrm{a} \}
\amp = \card{\words{\Sigma}_2} - \ncardop \{ 2\text{-letter words beginning with } \mathrm{a} \}\\
\amp = 26^2 - 26 \\
\amp = 26 (26 - 1) \\
\amp = 26 \cdot 25 \text{.}
\end{align*}
