2.2: Introduction to Counting
- Page ID
- 130486
\( \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}\)In the last section, we saw how to use the theorems we developed to answer some questions concerning the probability of an event. In this section (and in the following), we will learn how to count. After doing so, we will then connect counting to probability. We first start off with the following definition:
Combinatorial analysis refers to the mathematical theory of counting.
For many students, the topic of counting is often met with much dismay. Our goal here is to make counting as intuitive as possible. In order to do so, we will take a motivated approach to mostly every topic.
We first begin with a simple question that many students have heard of before. (However, if you did not hear of this question, then still try to answer it!).
Motivating Question: A man has 3 different shirts and 4 different pants. How many outfits does the man have? (For us, an outfit is a specification of the shirt and pants).
Most students correctly answer that the man has a total of 12 different shirts which is indeed correct. But if you are unsure as to why the answer is 12 or if you obtained a different answer, then let us explain where the 12 comes from. There are a few ways to prove your answer is correct. You may generate a chart or a tree diagram. The method of using a chart is discussed below:
A man has 3 different shirts and 4 different pants. How many outfits does the man have?
Solution
Let us call the three shirts \( S_1, S_2 \) and \( S_3 \) and the four pants \(P_1, P_2, P_3 \) and \( P_4 \). We may think of an outfit as being described by an order pair \( (x,y) \) where \(x \) represents the shirt and \( y \) represents the pants. To keep track of all the outfits, we make a table as shown below:
| \( S_1 \) | \(S_2 \) | \( S_3 \) | |
|---|---|---|---|
| \(P_1 \) | \( (S_1, P_1)\) | \((S_2, P_1)\) | \((S_3, P_1)\) |
| \( P_2 \) | \((S_1, P_2)\) | \((S_2, P_2)\) | \((S_3, P_2)\) |
| \( P_3 \) | \((S_1, P_3)\) | \((S_2, P_3)\) | \((S_3, P_3)\) |
| \( P_4 \) | \((S_1, P_4)\) | \((S_2, P_4)\) | \((S_3, P_4)\) |
We now must count the number of ordered pairs which appears in our chart. We see that there are \( 3 \times 4 = 12 \) entries, and hence 12 total possibilities.
For us, we would like to have a theorem which justifies the above multiplication. That theorem is what we will call The Basic Principle of Counting.
Suppose an experiment satisfies the following two criteria:
- The experiment is performed in two distinct parts or steps.
- The first part of the experiment has \( m \) possible outcomes and regardless of which of these outcomes may occur, the second part of the experiment has \( n \) possible outcomes.
Then the sample space, \( S \), has a total of \( m \times n \) possible outcomes.
Proof: We use a similar technique as presented in the above solution. Let the \( m \) possible outcomes in the first part be denoted by $\(s_1, s_2, \ldots, s_m \) and let the \( n \) possible outcomes in the second part be denoted by \( w_1, w_2, \ldots, w_n \). We now generate a chart to keep track of all possible outcomes:
| \( s_1 \) | \(s_2 \) | \( \ldots \) | \( s_m \) | |
|---|---|---|---|---|
| \(w_1 \) | \( (s_1, w_1)\) | \((s_2, w_1)\) | \( \ldots \) | \((s_m, w_1)\) |
| \( w_2 \) | \((s_1, w_2)\) | \((s_2, w_2)\) | \( \ldots \) | \((s_m, w_2)\) |
| \( \ldots \) | \((s_1, w_3)\) | \((s_2, w_3)\) | \( \ldots \) | \((s_m, w_3)\) |
| \( w_n \) | \((s_1, w_n)\) | \((s_2, w_n)\) | \( \ldots \) | \((s_m, w_n)\) |
Counting the number of ordered pairs, we see that there are \( \underbrace{m+m+\ldots + m}_{n ~ \text{times}} = mn \) possible outcomes.
We now have a more concise way of answering Example 1.
A man has 3 different shirts and 4 different pants. How many outfits does the man have?
Solution
We can think of choosing an outfit as a two stage experiment. We first must select a shirt and then we select a pants. Let us proceed in steps:
Step 1) We first select a shirt. There are 3 possible choices.
Step 2) We now select a pants. Regardless of the shirt selected in step 1, there are 4 possible choices.
Hence, by The Basic Principle of Counting, there are \( 3 \times 4 = 12 \) possible outcomes.
Suppose there are four different routes from Ozone Park to Kew Gardens and six different routes from Kew Gardens to Flushing. How many different routes are there from Ozone Park to Flushing which passes through Kew Gardens?
Solution
We must generate a route/path from Ozone Park to Flushing which passes through Kew Gardens. To do this, we can imagine the route/path as being constructed in two steps.
Step 1) We first select a path from Ozone Park to Kew Gardens. There are 4 possible choices.
Step 2) We now select a path from Kew Gardens to Flushing. Regardless of the path selected in step 1, there are 6 possible choices.
Hence, by The Basic Principle of Counting, there are \( 4 \times 6 = 24 \) possible paths.
There is no need to restrict ourselves to studying experiments where the experiment can be thought of as a two step process. Instead, we may wish to study experiments that have three steps or four steps or in general \( k \) steps. For instance, if we now consider an outfit to be a specification of shirt, pants, and shoes worn, then we can ask the following question: A man has 3 different shirts, 4 different pants, and 2 different shoes. How many outfits does the man have?
In situations like these, we must generalize The Basic Principle of Counting. Doing so yields The Generalized Principle of Counting.
Suppose an experiment satisfies the following two criteria:
- The experiment is performed in \(k \) distinct parts or steps.
- The first part of the experiment has \( n_1 \) possible outcomes and regardless of which of these outcomes may occur, the second part of the experiment has \( n_2 \) possible outcomes and regardless of which of these outcomes may occur, the third part of the experiment has \{ n_3 \) possible outcomes, and \( \ldots \), the \( (k-1)^{st} \) part of the experiment has \( n_{k-1} \) possible outcomes and regardless of which of these outcomes may occur, the \( (k)^{th} \) part of the experiment has \( n_{k} \) possible outcomes.
Then the sample space, \( S \), has a total of \( n_1 \times n_2 \times n_3 \times \ldots \times n_k \) possible outcomes.
A man has 3 different shirts, 4 different pants, and 2 different shoes. How many outfits does the man have?
Solution
We can now think of choosing an outfit as a three stage experiment. We first must select a shirt, then a pants, and then select the shoes. Let us proceed in these steps:
Step 1) We first select a shirt. There are 3 possible choices.
Step 2) We now select a pants. Regardless of the shirt selected in step 1, there are 4 possible choices.
Step 3) We now select the shoes. Regardless of the shirt and pants selected, there are 2 possible choices.
Hence, by The Generalized Principle of Counting, there are \( 3 \times 4 \times 2= 24 \) possible outcomes.
Although this completes the above example, it might be useful to note how The Generalized Principle of Counting and be thought of as an iterated version of The Basic Principle of Counting. To show this, allow us to consider the three stage experiment above as two separate two-stage experiments. In the first stage, we select a shirt and pants. Then in the second stage, we select a pair of shoes. Similar to what was done before, allow us to denote the three shirts by \( S_1, S_2 \) and \( S_3 \), the four pants by \(P_1, P_2, P_3 \) and \( P_4 \), and the two shoes by \( J_1 \) and \(J_2 \). Doing so gives us the following chart:
| \( J_1 \) | \( J_2 \) | |
| \( (S_1, P_1)\) | \( \big((S_1, P_1) , J_1 \big) \) | \( \big((S_1, P_1) , J_2 \big) \) |
| \( (S_1, P_2)\) | \( \big((S_1, P_2) , J_1 \big) \) | \( \big((S_1, P_2) , J_2 \big) \) |
| \( (S_1, P_3)\) | \( \big((S_1, P_3) , J_1 \big) \) | \( \big((S_1, P_3) , J_2 \big) \) |
| \( (S_1, P_4)\) | \( \big((S_1, P_4) , J_1 \big) \) | \( \big((S_1, P_4) , J_2 \big) \) |
| \( (S_2, P_1)\) | \( \big( (S_2, P_1) , J_1 \big) \) | \( \big((S_2, P_1) , J_2 \big) \) |
| \( (S_2, P_2)\) | \( \big((S_2, P_2) , J_1 \big) \) | \( \big((S_2, P_2) , J_2 \big) \) |
| \( (S_2, P_3)\) | \( \big((S_2, P_3) , J_1 \big) \) | \( \big((S_2, P_3) , J_2 \big) \) |
| \( (S_2, P_4)\) | \( \big((S_2, P_4) , J_1 \big) \) | \( \big((S_2, P_4) , J_2 \big) \) |
| \( (S_3, P_1)\) | \( \big((S_3, P_1) , J_1 \big) \) | \( \big((S_3, P_1) , J_2 \big) \) |
| \( (S_3, P_2)\) | \( \big((S_3, P_2) , J_1 \big) \) | \( \big((S_3, P_2) , J_2 \big) \) |
| \( (S_3, P_3)\) | \( \big((S_3, P_3) , J_1 \big) \) | \( \big((S_3, P_3) , J_2 \big) \) |
| \( (S_3, P_4)\) | \( \big( (S_3, P_4) , J_1 \big) \) | \( \big((S_3, P_4) , J_2 \big) \) |
How many diferent 7-place license plates are possible if the first three places are to be occupied with letters and the last four places are to be occupied with the digits where each digit ranges from 0-9 inclusively? You may assume that repetition of letters and digits are allowed.
Solution
A license plate may be thought of as a seven stage experiment. We proceed in steps:
- Select a letter for position 1: 26 choices
- Select a letter for position 2: 26 choices
- Select a letter for position 3: 26 choices
- Select a digit for position 4: 10 choices
- Select a digit for position 5: 10 choices
- Select a digit for position 6: 10 choices
- Select a digit for position 7: 10 choices
By The Generalized Principle of Counting, there are \( 26^3 \times 10^4 = 175,760,000 \) different license plates.
Allow us to modify the above example by considering how the solution would change if repetition was not allowed.
How many diferent 7-place license plates are possible if the first three places are to be occupied with letters and the last four places are to be occupied with the digits where each digit ranges from 0-9 inclusively?
Solution
A license plate may be thought of as a seven stage experiment. We proceed in steps:
- Select a letter for position 1: 26 choices
- Select a letter for position 2: 25 choices
- Select a letter for position 3: 24 choices
- Select a digit for position 4: 10 choices
- Select a digit for position 5: 9 choices
- Select a digit for position 6: 8 choices
- Select a digit for position 7: 7 choices
By The Generalized Principle of Counting, there are \( 26^3 \times 10^4 = 78,624,000 \) different license plates.
At this point in time, we may feel that the above framework seems like overkill for such a simple problem and it appears to be unnecessary. However, our counting questions will become more complicated and the process will not be as short as the above problem. For those types of complex problems, we will need the above framework and so we will continue to stick to this framework to gain familiarity with it. Moreover, our focus at this point is not the end answer. Instead, our objective is to write a clear solution.
Let us suppose we have the following simplified model of Chipotle. At Chipotle, we must select:
- One of five possible entrees (a burrito, burrito bowl, Quesadilla, salad, or taco).
- One of seven different proteins (chicken al pastor, chicken, steak, barbacoa, carnitas, sofritas, veggie).
- One of three possible rices (white rice, brown rice, no rice).
- One of three possible beans (black beans, pinto beans, no beans).
- Any amount of ten different toppings (guacamole, fresh tomato salsa, roasted chili-corn salsa, tomatillo green chili salsa, tomatillo-red chili salsa, sour cream, fajita veggies, cheese, romaine lettuce, queso blanco).
How many different dishes are available to a customer?
Critique This Solution:
By The Generalized Principle of Counting, there are \( 5 \times 7 \times 3 \times 3 \times 10 = 3150 \) possible outcomes. Is this solution correct? What do you think?
- Answer
-
The above solution is incorrect! Do not fall into the trap that The Basic Principle of Counting states that we simply multiple a bunch of numbers. Allow us to use our framework to fully answer this question:
- Select one entree: 5 choices
- Select one protein: 7 choices.
- Select one option for rice: 3 choices
- Select one option for beans: 3 choices
- Select one option for guacamole: 2 choices
- Select one option for fresh tomato salsa: 2 choices
- Select one option for roasted chili-corn salsa: 2 choices
- Select one option for tomatillo green chili salsa: 2 choices
- Select one option for tomatillo red salsa: 2 choices
- Select one option for sour cream: 2 choices
- Select one option for fajita veggies: 2 choices
- Select one option for cheese: 2 choices
- Select one option for romaine lettuce: 2 choices
- Select one option for queso blanco: 2 choices
By The Generalized Principle of Counting, there are \( 5 \times 7 \times 3 \times 3 \times 2^{10} = 322,560\) possible outcomes.
The above example illustrates that we should be careful while applying The Generalized Principle of Counting. Specifically, proceeding in steps can help us minimize mistakes.