14.2: Counting Sequences
- Page ID
- 48394
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)The Bijection Rule lets us count one thing by counting another. This suggests a general strategy: get really good at counting just a few things, then use bijections to count everything else! This is the strategy we’ll follow. In particular, we’ll get really good at counting sequences. When we want to determine the size of some other set \(T\), we’ll find a bijection from \(T\) to a set of sequences \(S\). Then we’ll use our super-ninja sequence-counting skills to determine \(|S|\), which immediately gives us \(|T|\). We’ll need to hone this idea somewhat as we go along, but that’s pretty much it!
The Product Rule
The Product Rule gives the size of a product of sets. Recall that if \(P_1, P_2, \ldots P_n\) are sets, then
\[\nonumber P_1 \times P_2 \times \cdots \times P_n\]
is the set of all sequences whose first term is drawn from \(P_1\), second term is drawn from \(P_2\) and so forth.
Rule 14.2.1 (Product Rule). If \(P_1, P_2, \ldots P_n\) are finite sets, then:
\[\nonumber |P_1 \times P_2 \times \cdots \times P_n| = |P_1| \cdot |P_2| \cdots |P_n|\]
For example, suppose a daily diet consists of a breakfast selected from set \(B\), a lunch from set \(L\), and a dinner from set \(D\) where:
\[\begin{aligned} B &= \{\text{pancakes, bacon and eggs, bagel, Doritos}\} \\ L &= \{\text{burger and fries, garden salad, Doritos}\} \\ D &= \{\text{macaroni, pizza, frozen burrito, pasta, Doritos}\} \end{aligned}\]
Then \(B \times L \times D\) is the set of all possible daily diets. Here are some sample elements:
\[\nonumber (\text{pancakes, burger and fries, pizza})\]
\[\nonumber (\text{bacon and eggs, garden salad, pasta})\]
\[\nonumber (\text{Doritos, Doritos, frozen burrito})\]
The Product Rule tells us how many different daily diets are possible:
\[\begin{aligned} |B \times L \times D| &= |B| \cdot |L| \cdot |D| \\ &= 4 \cdot 3 \cdot 5 \\ &=60. \end{aligned}\]
Subsets of an n-element Set
The fact that there are \(2^n\) subsets of an n-element set was proved in Theorem 4.5.5 by setting up a bijection between the subsets and the length-\(n\) bit-strings. So the original problem about subsets was tranformed into a question about sequences— exactly according to plan! Now we can fill in the missing explanation of why there are \(2^n\) length-\(n\) bit-strings: we can write the set of all \(n\)-bit sequences as a product of sets:
\[\nonumber \{0,1\}^n ::= \underbrace{\{0,1\} \times \{0,1\} \times \cdots \times \{0,1\}}_{n \text{ terms}}.\]
Then Product Rule gives the answer:
\[\nonumber |\{0,1\}^n| = |\{0,1\}|^n = 2^n.\]
The Sum Rule
Bart allocates his little sister Lisa a quota of 20 crabby days, 40 irritable days, and 60 generally surly days. On how many days can Lisa be out-of-sorts one way or another? Let set \(C\) be her crabby days, \(I\) be her irritable days, and \(S\) be the generally surly. In these terms, the answer to the question is \(|C \cup I \cup S|\). Now assuming that she is permitted at most one bad quality each day, the size of this union of sets is given by the Sum Rule:
Rule 14.2.2 (Sum Rule). If \(A_1, A_2, \ldots, A_n\) are disjoint sets, then:
\[\nonumber |A_1 \cup A_2 \cup \ldots A_n| = |A_1| + |A_2| + \cdots + |A_n|\]
\[\begin{aligned} |C \cup I \cup S| &= |C| + |I| + |S| \\ &= 20+40+60 \\ &=120 \text{ days}. \end{aligned}\]
Notice that the Sum Rule holds only for a union of disjoint sets. Finding the size of a union of overlapping sets is a more complicated problem that we’ll take up in Section 14.9.
Counting Passwords
Few counting problems can be solved with a single rule. More often, a solution is a flurry of sums, products, bijections, and other methods.
For solving problems involving passwords, telephone numbers, and license plates, the sum and product rules are useful together. For example, on a certain computer system, a valid password is a sequence of between six and eight symbols. The first symbol must be a letter (which can be lowercase or uppercase), and the remaining symbols must be either letters or digits. How many different passwords are possible?
Let’s define two sets, corresponding to valid symbols in the first and subsequent positions in the password.
\[\begin{aligned} F &= \{a, b, \ldots, z, A, B, \ldots, Z\} \\ S &= \{a, b, \ldots, z, A, B, \ldots, Z, 0, 1, \ldots, 9\} \end{aligned}\]
In these terms, the set of all possible passwords is:1
\[\nonumber (F \times S^5) \cup (F \times S^6) \cup (F \times S^7)\]
Thus, the length-six passwords are in the set \(F \times S^5\), the length-seven passwords are in \(F \times S^6\), and the length-eight passwords are in \(F \times S^7\). Since these sets are disjoint, we can apply the Sum Rule and count the total number of possible passwords as follows:
\[\begin{aligned} |(F \times S^5) &\cup (F \times S^6) \cup (F \times S^7)| \\ &= |F \times S^5| + |F \times S^6| + |F \times S^7| & \text{Sum Rule} \\ &= |F| \times |S|^5 + |F| \times |S|^6 + |F| \times |S|^7 & \text{Product Rule} \\ &= 52 \cdot 62^5 + 52 \cdot 62^6 + 52 \cdot 62^7 \\ & \approx 1.8 \cdot 10^{14} \text{ different passwords}. \end{aligned}\]
1The notation \(S^5\) means \(S \times S \times S \times S \times S\).