Skip to main content
Contents Index
Search Book
Search Results:
No results.
Readability settings Prev Up Next \(\require{cancel}
\newcommand{\nth}[1][n]{{#1}^{\mathrm{th}}}
\newcommand{\bbrac}[1]{\bigl(#1\bigr)}
\newcommand{\Bbrac}[1]{\Bigl(#1\Bigr)}
\newcommand{\correct}{\boldsymbol{\checkmark}}
\newcommand{\incorrect}{\boldsymbol{\times}}
\newcommand{\inv}[2][1]{{#2}^{-{#1}}}
\newcommand{\leftsub}[3][1]{\mathord{{}_{#2\mkern-#1mu}#3}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\I}{\mathbb{I}}
\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}
\DeclareMathOperator{\sqrtop}{sqrt}
\newcommand{\lgcnot}{\neg}
\newcommand{\lgcand}{\wedge}
\newcommand{\lgcor}{\vee}
\newcommand{\lgccond}{\rightarrow}
\newcommand{\lgcbicond}{\leftrightarrow}
\newcommand{\lgcimplies}{\Rightarrow}
\newcommand{\lgcequiv}{\Leftrightarrow}
\newcommand{\lgctrue}{\mathrm{T}}
\newcommand{\lgcfalse}{\mathrm{F}}
\newcommand{\boolnot}[1]{{#1}'}
\newcommand{\boolzero}{\mathbf{0}}
\newcommand{\boolone}{\mathbf{1}}
\newcommand{\setdef}[2]{\left\{\mathrel{}#1\mathrel{}\middle|\mathrel{}#2\mathrel{}\right\}}
\newcommand{\inlinesetdef}[2]{\{\mathrel{}#1\mathrel{}\mid\mathrel{}#2\mathrel{}\}}
\let\emptyword\emptyset
\renewcommand{\emptyset}{\varnothing}
\newcommand{\relcmplmnt}{\smallsetminus}
\newcommand{\union}{\cup}
\newcommand{\intersection}{\cap}
\newcommand{\cmplmnt}[1]{{#1}^{\mathrm{c}}}
\newcommand{\disjunion}{\sqcup}
\newcommand{\cartprod}{\times}
\newcommand{\words}[1]{{#1}^\ast}
\newcommand{\length}[1]{\abs{#1}}
\newcommand{\powsetbare}{\mathcal{P}}
\newcommand{\powset}[1]{\powsetbare(#1)}
\newcommand{\funcdef}[4][\to]{#2\colon #3 #1 #4}
\newcommand{\ifuncto}{\hookrightarrow}
\newcommand{\ifuncdef}[3]{\funcdef[\ifuncto]{#1}{#2}{#3}}
\newcommand{\sfuncto}{\twoheadrightarrow}
\newcommand{\sfuncdef}[3]{\funcdef[\sfuncto]{#1}{#2}{#3}}
\newcommand{\funcgraphbare}{\Delta}
\newcommand{\funcgraph}[1]{\funcgraphbare(#1)}
\newcommand{\nmathrel}[1]{\mathrel{\not #1}}
\newcommand{\relset}[3]{#1_{{} #2 #3}}
\newcommand{\gtset}[2]{\relset{#1}{\gt}{#2}}
\newcommand{\posset}[1]{\gtset{#1}{0}}
\newcommand{\geset}[2]{\relset{#1}{\ge}{#2}}
\newcommand{\nnegset}[1]{\geset{#1}{0}}
\newcommand{\neqset}[2]{\relset{#1}{\neq}{#2}}
\newcommand{\nzeroset}[1]{\neqset{#1}{0}}
\newcommand{\ltset}[2]{\relset{#1}{\lt}{#2}}
\newcommand{\leset}[2]{\relset{#1}{\le}{#2}}
\newcommand{\natnumlt}[1]{\ltset{\N}{#1}}
\DeclareMathOperator{\id}{id}
\newcommand{\inclfunc}[2]{\iota_{#1}^{#2}}
\newcommand{\projfunc}[1]{\rho_{#1}}
\DeclareMathOperator{\proj}{proj}
\newcommand{\funcres}[2]{\left.{#1}\right\rvert_{#2}}
\newcommand{\altfuncres}[2]{\left.{#1}\right\rvert{#2}}
\DeclareMathOperator{\res}{res}
\DeclareMathOperator{\flr}{flr}
\newcommand{\floor}[1]{\lfloor {#1} \rfloor}
\newcommand{\funccomp}{\circ}
\newcommand{\funcinvimg}[2]{\inv{#1}\left({#2}\right)}
\newcommand{\card}[1]{\left\lvert #1 \right\rvert}
\DeclareMathOperator{\cardop}{card}
\DeclareMathOperator{\ncardop}{\#}
\newcommand{\EngAlphabet}{\{ \mathrm{a}, \, \mathrm{b}, \, \mathrm{c}, \, \dotsc, \, \mathrm{y}, \, \mathrm{z} \}}
\newcommand{\ShortEngAlphabet}{\{ \mathrm{a}, \, \mathrm{b}, \, \dotsc, \, \mathrm{z} \}}
\newcommand{\eqclass}[1]{\left[#1\right]}
\newcommand{\partorder}{\preceq}
\newcommand{\partorderstrict}{\prec}
\newcommand{\npartorder}{\npreceq}
\newcommand{\subgraph}{\preceq}
\newcommand{\subgraphset}[1]{\mathcal{S}(#1)}
\newcommand{\connectedsubgraphset}[1]{\mathcal{C}(#1)}
\newcommand{\permcomb}[3]{{#1}(#2,#3)}
\newcommand{\permcombalt}[3]{{#1}^{#2}_{#3}}
\newcommand{\permcombaltalt}[3]{{\leftsub{#2}{#1}}_{#3}}
\newcommand{\permutation}[2]{\permcomb{P}{#1}{#2}}
\newcommand{\permutationalt}[2]{\permcombalt{P}{#1}{#2}}
\newcommand{\permutationaltalt}[2]{{\permcombaltalt{P}{#1}{#2}}}
\newcommand{\combination}[2]{\permcomb{C}{#1}{#2}}
\newcommand{\combinationalt}[2]{\permcombalt{C}{#1}{#2}}
\newcommand{\combinationaltalt}[2]{{\permcombaltalt{C}{#1}{#2}}}
\newcommand{\choosefuncformula}[3]{\frac{#1 !}{#2 ! \, #3 !}}
\DeclareMathOperator{\matrixring}{M}
\newcommand{\uvec}[1]{\mathbf{#1}}
\newcommand{\zerovec}{\uvec{0}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
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{.}\) That is,
\(\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*}
