8.1: The Fundamental Counting Principle
- Page ID
- 138218
\( \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}\)A tree diagram is a useful tool for visualizing systematic counting.
Let’s say that a person walks into a restaurant for a three course dinner. There are four different salads, three different entrees, and two different desserts to choose from. Assuming the person wants to eat a salad, an entrée and a desert, how many different meals are possible?
Solution
Looking at the tree diagram we can see that the total number of meals is 24. The first meal is salad 1, entrée 1, and dessert 1. The 24th meal is salad 4, entrée 3, dessert 2.
The Three Course Dinner example is easier to count the possible meals by using The Fundamental Counting Principle
If there are \(n_1\) ways to of choosing the first item, \(n_2\) ways of choosing the second item after the first item is chosen, \(n_3\) ways of choosing the third item after the first two have been chosen, and so on until there are \(n_k\) ways of choosing the last item after the earlier choices, then the total number of choices overall is given by
\[n_1 \times n_2 \times n_3 \times n_4 \times n_5 ... \times n_k. \label{Multiplication Principle}\]
Let’s look at the number of ways that four people can line up. We can choose any of the four people to be first. Then there are three people who can be second and two people who can be third. At this point there is only one person left to be last. Using the multiplication principle there are
\[4 \times 3 \times 2 \times 1 = 24\, \text{ways} \nonumber\]
for four people to line up.
This type of calculation occurs frequently in counting problems so we have some notation to simplify the problem.
The factorial of \(n\), read “n factorial” is
\[n! = n(n-1)(n-2)(n-3)...(2)(1).\]
By this definition, \(0! = 1.\)
\[\begin{align*} 5! &= 5 \times 4 \times 3 \times 2 \times 1 \\[4pt] &= 120 \\[5pt] 8! &= 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 \\[4pt] &= 40,320 \end{align*}\]
Factorials get very large very fast.
\[20! = 2.43 \times 10^{18} \nonumber\]
and
\[40! = 8.16 \times 10^{47}. \nonumber\]
70! is larger than most calculators can handle.
The fundamental counting principle may seem like a very simple idea but it is very powerful. Many complex counting problems can be solved using the fundamental counting principle.
Some license plates in Arizona consist of three digits followed by three letters. How many license plates of this type are possible if:
- There are 10 digits (0, 1, 2, 3, …, 9) and 26 letters. \[\underbrace{(10 \cdot 10 \cdot 10) \cdot (26 \cdot 26 \cdot 26)}_{\text{digits}}=17,576,000\, \text{license plates } \nonumber\]
- letters can be repeated but digits cannot? \[\underbrace{(\underline{10} \cdot \underline{9} \cdot \underline{8}) \cdot(26 \cdot 26 \cdot 26)}_{\text {letters}}=12,654,720\, \text{license plates} \nonumber\]
- the first digit cannot be zero and both digits and letters can be repeated? \[\underbrace{(\underline{9} \cdot \underline{10} \cdot \underline{10})}_{\text{digits}} \cdot \underbrace{(\underline{26} \cdot 26 \cdot 26)}_{\text{letters}}=15,818,400\, \text{license plates} \nonumber\]
- neither digits nor numbers can be repeated. \[\underbrace{(\underline{10} \cdot \underline{9} \cdot \underline{8})}_{\text{digits}} \cdot \underbrace{(\underline{26} \cdot \underline{25} \cdot \underline{24})}_{\text{letters}}=11,232,000 \, \text{license plates} \nonumber\]