Skip to main content

Section 2.2 Counting with Steps and Cases

Sometimes we want to count how many objects are in a list. We might want to know if there will be enough different ID numbers for students (past, present, and future) or if we need new area codes for telephone numbers (as happened when people first started using cellphones). In this section, we practice counting including two rules related to steps and cases. We also discuss factorial notation that arises frequently in counting.
Mathematicians who like to count things famously ask The Three Questions.
  • Is there (or does there exist) an example of …?
  • If so, then is it unique, which means it is the only example of …?
  • If it exists but is not unique, then how many examples of … are there?
The third question asks us to count, which means to determine how many examples of something there are.
Try your hand at counting.

Activity 2.2.A Lunch.

My favorite cafe offers three types of salad, five types of pizza, and four types of cookies for lunch.
  1. How many lunch options are there if I decide to have a salad and a pizza? Hint: What would the possibility tree look like with salads (\(\str{s1}\text{,}\) \(\str{s2}\text{,}\) \(\str{s3}\)) and pizzas (\(\str{p1}\text{,}\) \(\str{p2}\text{,}\) \(\str{p3}\text{,}\) \(\str{p4}\text{,}\) \(\str{p5}\))?
  2. How does your answer to (a) relate to the number of salads and the number of pizzas?
  3. How many lunch options are there if I choose a salad or pizza (but not both) instead? Hint: Consider cases.
  4. How does your answer to (c) relate to the number of salads and the number of pizzas?
  5. How many lunch options are there if I order the special “Pick Two” which is either a salad and a pizza, a salad and a cookie, or a pizza and a cookie? Hint: Consider cases.

Subsection 2.2.A Counting with Steps and Cases

Be sure to try Activity 2.2.A before continuing to read because we are about to discuss two strategies– steps and cases, that help us find the solution.

Example 2.2.2 Salad and pizza.

As in Activity 2.2.A, my favorite cafe offers three types of salad, five types of pizza, and four types of cookies for lunch. How many lunch options are there if I decide to have a salad and a pizza? This question was (a).
Solution.
The possibility tree would have three branches from \(\bullet\text{,}\) one to each of \(\str{s1}\text{,}\) \(\str{s2}\text{,}\) and \(\str{s3}\text{.}\)
Then each of those nodes would have five branches, one to each of \(\str{p1}\text{,}\) \(\str{p2}\text{,}\) \(\str{p3}\text{,}\) \(\str{p4}\text{,}\) \(\str{p5}\text{.}\)
Our list would have each possible lunch option.
\(\str{s1}\) & \(\str{p1}\text{,}\) \(\str{s1}\) & \(\str{p2}\text{,}\) \(\str{s1}\) & \(\str{p3}\text{,}\) \(\str{s1}\) & \(\str{p4}\text{,}\) \(\str{s1}\) & \(\str{p5}\text{,}\)
\(\str{s2}\) & \(\str{p1}\text{,}\) \(\str{s2}\) & \(\str{p2}\text{,}\) \(\str{s2}\) & \(\str{p3}\text{,}\) \(\str{s2}\) & \(\str{p4}\text{,}\) \(\str{s2}\) & \(\str{p5}\text{,}\)
\(\str{s3}\) & \(\str{p1}\text{,}\) \(\str{s3}\) & \(\str{p2}\text{,}\) \(\str{s3}\) & \(\str{p3}\text{,}\) \(\str{s3}\) & \(\str{p4}\text{,}\) \(\str{s3}\) & \(\str{p5}\text{.}\)
Notice that we have three rows with five options in each row. The total number of lunch options is \(3 \times 5 = 15\text{.}\)
Formally, we can build each lunch option through a sequence of two steps. Step 1: choose a salad and then Step 2: choose a pizza. There are three ways to do Step 1 and then, no matter which salad we choose, there are five ways to do Step 2.
In general, when there are the same number of branches at each step, we can multiply to find the total number. We state this rule formally.
Notice the phrase “and then”, which often indicates that steps are involved.
A special situation that is counted using steps is the number of permutations of the set \(\{\str{1}, \str{2}, \ldots, \str{n}\}\text{.}\)

Definition 2.2.4 Permutation of the set \(\{\str{1},\str{2},\ldots,\str{n}\}\).

  For a positive integer \(n\text{,}\) a permutation of the set \(\{\str{1},\str{2},\ldots,\str{n}\}\) is a string of length \(n\) using each of the digits \(\bs{1}\text{,}\) \(\str{2}\text{,}\) …, and \(\str{n}\) exactly once. For example, \(\str{2413}\) is a permutation of the set \(\{\str{1},\str{2},\str{3},\str{4}\}\text{.}\)
We consider the case where \(n=4\) in our next example.

Example 2.2.5 Permutations of the set \(\{\str{1},\str{2},\str{3},\str{4}\}\).

How many permutations of the set \(\{\str{1},\str{2},\str{3},\str{4}\}\) are there?
Solution.
Imagine building each permutation by filling in four spaces:
\begin{equation*} \underline{\phantom{X}}~\underline{\phantom{X}}~\underline{\phantom{X}}~\underline{\phantom{X}} \end{equation*}
Step 1: Fill in the first space. There are four ways to fill the first space because the first digit can be any of \(\bs{1}\text{,}\) \(\str{2}\text{,}\) \(\str{3}\text{,}\) or \(\str{4}\text{.}\) (4 ways)
Step 2: Fill in the second space. There are only three ways to fill the second space, because the second digit cannot be the same as the first digit. For example, if we filled in the first space with a \(\str{2}\) as
\begin{equation*} \underline{\str{2}}~\underline{}~\underline{}~\underline{} \end{equation*}
then the second space can only be \(\bs{1}\text{,}\) \(\str{3}\text{,}\) or \(\str{4}\text{.}\) (3 ways)
Step 3: Fill in the third space. There are only two ways to fill in the third space because the third digit cannot be the same as the first or second digit. For example, if we filled in the first two spaces with \(\str{2}\) and then \(\str{4}\) as
\begin{equation*} \underline{\str{2}}~\underline{\str{4}}~\underline{}~\underline{} \end{equation*}
then the third space can only be \(\bs{1}\) or \(\str{3}\text{.}\) (2 ways)
Step 4: Fill in the fourth space. There is “no choice”, which means that there is only one way to fill in the fourth space. It must be the last missing digit. For example, if we filled in the first three spaces with \(\str{2}\text{,}\) and then \(\str{4}\text{,}\) and then \(\bs{1}\) as
\begin{equation*} \underline{\str{2}}~\underline{\str{4}}~\underline{\str{1}}~\underline{} \end{equation*}
then the fourth space can only be \(\str{3}\) and so our final permutation would be
\begin{equation*} \underline{\str{2}}~\underline{\str{4}}~\underline{\str{1}}~\underline{\str{3}}\text{.} \end{equation*}
(1 way)
Since steps multiply Theorem 2.2.3, there are
\begin{equation*} (4)(3)(2)(1) = 24 \end{equation*}
permutations of the set \(\{\str{1},\str{2},\str{3},\str{4}\}\text{.}\) You can check by drawing the possibility tree, as in Section 2.1 Exercise 17.
Products such as the answer to Example 2.2.5 occur often enough that they have a name and notation. For example, our product is 4 factorial
\begin{equation*} 4! = (4)(3)(2)(1) = 24\text{.} \end{equation*}
We state the formal definition and discuss factorials in Subsection 2.2.C.
Let’s continue our discussion of Activity 2.2.A.

Example 2.2.6 Salad or pizza.

As in Activity 2.2.A, my favorite cafe offers three types of salad, five types of pizza, and four types of cookies for lunch. How many lunch options are there if I decide to have a salad or a pizza (but not both)? This question was (c).
Solution.
We could make a list by considering cases. On our list would be each of the three salads and each of the five pizzas: \(\str{s1}\text{,}\) \(\str{s2}\text{,}\) \(\str{s3}\text{,}\) \(\str{p1}\text{,}\) \(\str{p2}\text{,}\) \(\str{p3}\text{,}\) \(\str{p4}\text{,}\) \(\str{p5}\text{,}\) The total number of lunch options is \(3 + 5 = 8\text{.}\)
Formally, we separate lunch options into two cases: in the first case, we choose a salad (in 3 ways) and in the second case, we choose a pizza (in 5 ways). Notice that we do Case 1 or Case 2, but not both.
In general, when there are separate cases, we can add to find the total number. We state this rule formally.
Notice the word “or” which often indicates that cases are involved. When we refer to separate cases, we mean that each example is covered by exactly one case.
An application of cases Theorem 2.2.7 is to count the opposite.

Example 2.2.8 Counting 0-99.

How many integers from 0 to 99 include the digit 5?
Solution.
We can list the integers that include the digit 5. They are:
\begin{equation*} 5, 15, 25, 35, 45, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 65, 75, 85, 95 \end{equation*}
A direct count gives 19 such integers. This strategy would not generalize well if we wanted 0 to 999 instead.
Alternatively, we can use cases to count the opposite. Each integer from 0 to 99 can be written as 2-digit numbers. For example, write 05 instead of 5. We know that there are 100 integers from 0 to 99. We can list the integers from 0 to 99 that do not include the digit 5 in steps.
Step 1: Choose the first (non-5) digit from \(\{0,1,2,3,4,6,7,8,9\}\) (9 ways)
Step 2: Choose the second (non-5) digit from \(\{0,1,2,3,4,6,7,8,9\}\) (9 ways)
Since steps multiply Theorem 2.2.3, there are \(9*9=81\) integers from 0 to 99 that do not include the digit 5.
Since cases add, the number of integers from 0 to 99 that include the digit 5 plus the number of integers from 0 to 99 that do not include the digit 5 must equal the total number of integers from 0 to 99. That is, if \(n\) is the number of integers from 0 to 99 that include the digit 5, then
\begin{equation*} n + 81 = 100 \end{equation*}
or, equivalently
\begin{equation*} n = 100-81=19\text{.} \end{equation*}
We summarize the strategy from Example 2.2.8 in a theorem.
In more complicated examples, we can combine steps and cases.

Example 2.2.10 Pick two lunch.

As in Activity 2.2.A, my favorite cafe offers three types of salad, five types of pizza, and four types of cookies for lunch. How many lunch options are there if I order the “Pick Two” special, which is either a salad and a pizza, a salad and a cookie, or a pizza and a cookie? This question was (e).
Solution.
We consider cases.
Case 1: Order salad and pizza. As in Example 2.2.2, we can build each lunch option through a sequence of two steps. Step 1: choose the salad (3 ways) and then step 2: choose the pizza (5 ways). Since steps multiply Theorem 2.2.3, there are \(3 \times 5 = 15\) options listed in this case.
Case 2: Order salad and a cookie. We can build each lunch choice through a sequence of two steps. Step 1: choose the salad (3 ways) and then step 2: choose the cookie (4 ways). Since steps multiply, there are \(3 \times 4 = 12\) options listed in this case.
Case 3: Order pizza and a cookie. We can build each lunch choice through a sequence of two steps. Step 1: choose the pizza (5 ways) and then step 2: choose the cookie (4 ways). Since steps multiply, there are \(5 \times 4 = 20\) options listed in this case.
Since cases add Theorem 2.2.7, there are \(15+12+20 = 47\) “Pick Two” lunch options.
It would be reasonable to report the answer to Example 2.2.10, as
\begin{equation*} (3)(5) + (3)(4) + (5)(4)\text{.} \end{equation*}
In fact, the unevaluated version can help us to see generalizations. For example, if there were \(s\) salads, \(p\) pizzas, and \(c\) cookies, then the total number of “Pick Two” lunches would be
\begin{equation*} sp + sc + pc \end{equation*}
In some counting situations, we want an exact number as an answer. For example, we usually evaluate the answer if it is 20 or less. More often, it is acceptable not to evaluate the answer.

Remark 2.2.11 Not evaluating counts, version 1.

Unless stated otherwise, when counting you may leave any answer greater than twenty in a format that could easily be evaluated on a calculator. In particular, your answer may involve addition, subtraction, multiplication, division, and parentheses.
Now it is your turn to practice counting using steps and uses.

Activity 2.2.B Passwords.

In this problem, a password is a string of eight characters. Imagine building each password by filling in the eight spaces:
Figure 2.2.13. Eight spaces to fill when building a password.
Use steps and/or cases to count how many different passwords are possible in each situation. Follow Remark 2.2.11 to determine whether you should simplify your answer.
  1. All characters are digits (\(\bs{0}\)-\(\str{9}\)). Hint: Step 1: fill in the first space, Step 2: fill in the second space, …, Step 8: fill in the eighth space.
  2. The first three characters must be letters (\(\str{a}\)-\(\str{z}\text{,}\) \(\str{A}\)-\(\str{Z}\)) and the rest of the characters are digits or, vice versa
     1 
    The phrase “vice versa” means in reverse.
    , the first three characters are digits and the rest of the characters are letters. Hint: Consider two cases.
  3. The characters are lowercase letters (\(\str{a}\)-\(\str{z}\)), but no letters may be repeated.
  4. The characters are uppercase letters, and exactly one of the characters must be the letter \(\str{X}\text{.}\) Hint: Step 1: select which space is \(\str{X}\text{,}\) Step 2: fill in the first open space with an uppercase letter other than \(\str{X}\text{,}\) Step 3: fill in the next open space with an uppercase letter other than \(\str{X}\text{,}\) etc.

Subsection 2.2.B When Counting Goes Awry

In each of the examples so far in this section, we have been able to count using steps, cases, or a combination of steps and cases. Some situations do not fit these rules. For example, to use steps Theorem 2.2.3, there must be the same number of options at each step. That means that in the possibility tree, there must be the same number of branches at any given level. Here is an example where steps do not work.

Example 2.2.14 Steps do not work.

Explain why we cannot use steps Theorem 2.2.3 to count the number of tilings of the \(1 \times 5\) board using squares (\(\bullet\)) and dominoes (\(\boldsymbol{-}\)), as in Activity 2.1.A.
Solution.
In Example 2.1.18, we drew the possibility tree shown in Figure 2.1.19.
If we think of building the tiling in steps, the first step is to choose the first tile, which can be a square or a domino. In the tree, we see two branches from the root.
The second step is to choose the second tile, which can also be a square or a domino. In the tree, we see two branches from the original square or domino. So far, so good.
But in the third step, when we choose the third tile, the situation changes. In most cases, the third tile can be a square or domino, but if we started with two dominoes , then the next tile must be a square because the total length is five (and three dominoes would have length six). In the tree, we see only one branch following the option \(\boldsymbol{-}\boldsymbol{-}\bullet\text{.}\)
In the fourth step, when we choose the fourth tile, the situation becomes even more complicated. In some cases, we still have the option of a square or a domino, which corresponds to two branches of the tree. In other cases, we only have the option of a square, which corresponds to one branch in the tree. In some cases, we are done, so there are no options, which corresponds to zero branches in the tree.
To use the steps rule Theorem 2.2.3, we would need each step to have a constant number of branches. Since the third step could have one or two branches and the fourth (and fifth) steps could have zero, one, or two branches, we cannot use the steps rule.
Similarly, to use cases Theorem 2.2.7, the cases must be separate. Here is an example where cases do not work.

Example 2.2.15 Cases do not work.

Explain why we cannot use cases Theorem 2.2.7 to count the number of tilings of the \(1 \times 4\) board using squares and dominoes that begin or end with a square.
Solution.
Let’s see what happens if we try to count using cases. Even though we do not normally make a list when counting, it will be illustrative here to make a list in each case.
Case 1: The tiling begins with a square. The remainder of the tiling can be any square and domino tiling of a \(1 \times 3\) board: \(\bullet\bullet\bullet\text{,}\) \(\bullet\boldsymbol{-}\text{,}\) or \(\boldsymbol{-}\bullet\text{.}\) Therefore, we have three strings in this case:
\begin{equation*} \bullet\bullet\bullet\bullet, \bullet\bullet\boldsymbol{-}, \bullet\boldsymbol{-}\bullet \end{equation*}
Case 2: The tiling ends with a square. Now, the beginning of the tiling can be any square and domino tiling of a \(1 \times 3\) board: \(\bullet\bullet\bullet\text{,}\) \(\bullet\boldsymbol{-}\text{,}\) or \(\boldsymbol{-}\bullet\text{.}\) Therefore, we also have three strings in this case:
\begin{equation*} \bullet\bullet\bullet\bullet, \bullet\boldsymbol{-}\bullet, \boldsymbol{-}\bullet\bullet \end{equation*}
Notice that the tilings \(\bullet\bullet\bullet\bullet\) and \(\bullet\boldsymbol{-}\bullet\) appear on both lists, so there are only four distinct tilings:
\begin{equation*} \bullet\bullet\bullet\bullet, \bullet\bullet\boldsymbol{-}, \bullet\boldsymbol{-}\bullet, \boldsymbol{-}\bullet\bullet\text{.} \end{equation*}
The answer is 4, but if we had added the numbers from our cases, we would have \(3+3=6\text{,}\) which is not correct.
There is a workaround when we have cases that are not separate. See Exercise 14 for an example. For now, try to keep your cases separate.

Activity 2.2.C Counting incorrectly.

Consider all strings of length four
\begin{equation*} \underline{\phantom{X}}~\underline{\phantom{X}}~\underline{\phantom{X}}~\underline{\phantom{X}} \end{equation*}
that use only the characters \(\str{X}\text{,}\) \(\str{f}\text{,}\) and \(\str{2}\) and include at least one \(\str{X}\text{.}\) When explaining why the given count does not work, your reasons might be that we missed counting some of the options, that we counted some options that we should not have counted, or that we counted some (or all) options more than once.
  1. Explain why the following count does not work.
    Step 1: Fill in the first space. (3 ways).
    Step 2: Fill in the second space. (3 ways).
    Step 3: Fill in the third space. (3 ways).
    Step 4: Fill in the fourth space. (3 ways).
    Since steps multiply Theorem 2.2.3, there are \(3^4=81\) such strings.
    Is the correct answer larger or smaller than 81?
  2. Explain why the following count does not work.
    Step 1: Choose where an \(\str{X}\) goes. (4 ways)
    Step 2: Fill in the first blank space with \(\str{f}\) or \(\str{2}\text{.}\) (2 ways)
    Step 3: Fill in the second blank space with \(\str{f}\) or \(\str{2}\text{.}\) (2 ways)
    Step 4: Fill in the third blank space with \(\str{f}\) or \(\str{2}\text{.}\) (2 ways).
    Since steps multiply Theorem 2.2.3, there are \((4)2^3 = 32\) ways.
    Is the correct answer larger or smaller than 32?
  3. Explain why the following count does not work.
    Step 1: Choose where an \(\str{X}\) goes. (4 ways)
    Step 2: Fill in the first blank space. (3 ways)
    Step 3: Fill in the second blank space. (3 ways)
    Step 4: Fill in the third blank space. (3 ways).
    Since steps multiply Theorem 2.2.3, there are \((4)3^3 = 108\) ways.
  4. Find a way to count to get the answer of \(3^4-2^4\text{.}\) Hint: Count the strings that do not use the character \(\str{X}\text{.}\)

Subsection 2.2.C Algebra: Factorials

In Example 2.2.5, we saw that the number of permutations of the set \(\{\str{1},\str{2},\str{3},\str{4}\}\) was is \(4!\) where
\begin{equation*} 4!=(4)(3)(2)(1)\text{.} \end{equation*}
This product of consecutive integers denoted 4! is pronounced “4 factorial”.
Before formally defining factorials, it is convenient to define consecutive integers.

Definition 2.2.17 Consecutive integers.

 
  1. A pair of integers \(a,b\) is consecutive if \(b=a+1\text{.}\) For example, 5 and 6 are consecutive integers because \(6=5+1\text{.}\)
  2. In general, a list of integers is consecutive if we get from each integer to the next by adding one. For example, \(5,6,7,8,9\) are consecutive integers. We often refer to consecutive integers as appearing “in a row” on the list of integers in Definition 2.1.7.
Let’s practice writing consecutive integers.

Example 2.2.18 Consecutive integers.

 
  1. List the three integers immediately after the integer \(n\text{.}\)
    Solution.
    Notice that \((n+1)+1=n+2\) and \((n+2)+1 = n+3\text{.}\) The next three integers after the integer \(n\) are: \(n+1\text{,}\) \(n+2\text{,}\) and \(n+3\text{.}\)
  2. List the three integers immediately before the integer \(n\text{.}\)
    Solution.
    Since we add one to get from an integer to the next consecutive integer, we must subtract one to get from an integer to the previous consecutive integer. That is, the integer before \(n\) must be \(n-1\text{.}\) Similarly, the integer before \(n-1\) must be \((n-1)-1=n-2\) and the integer before that is \((n-2)-1=n-3\text{.}\) The three integers immediately before the integer \(n\) are \(n-1\text{,}\) \(n-2\text{,}\) and \(n-3\)
It can be helpful to think of the sequence around an integer \(n\) as
\begin{equation*} \ldots, n-3, n-2, n-1, n, n+1, n+2, n+3, \ldots \end{equation*}
Now we are ready to give a formal definition of a factorial.

Definition 2.2.19 Factorial.

 
  1. When \(n\) is a positive integer, the factorial \(n!\) is the product of the consecutive integers \(1, 2, \ldots n\text{,}\) usually written in reverse order. For example,
    \begin{equation*} 5!=(5)(4)(3)(2)(1) = 120\text{.} \end{equation*}
  2. We often write
    \begin{equation*} n! = n(n-1)\cdots(3)(2)(1) \end{equation*}
    which can be misleading for small powers of \(n\text{.}\) For example, by definition,
    \begin{equation*} 2!=(2)(1) = 2 \ \ \text{ and } 1!=(1) = 1\text{.} \end{equation*}
    Neither of these factorials includes the integer 3 as a factor, even though the \(\ldots\) notation shows a factor of (3).
  3. It is convenient to define \(0!=1\text{.}\)
  4. Factorials are at the same priority in the order of operations as exponents in Definition 2.1.20. For example,
    \begin{equation*} 20+5! = 20 + 120 = 140\text{,} \end{equation*}
    while
    \begin{equation*} (20 +5)! = 25! \approx 1.55 \times 10^{25}\text{,} \end{equation*}
    definitely a different value.
Let’s practice applying this definition.

Example 2.2.20 Factorials.

On this problem, we only use technology to check our answers.
  1. Evaluate 6!.
    Solution.
    By definition and using that \(5!=120\) from Definition 2.2.19(a), we get
    \begin{equation*} 6! = (6)\underbrace{(5)(4)(3)(2)(1)}_{5!} = 6(5!)= 6(120) = 720 \end{equation*}
  2. Evaluate \(2n!\) when \(n=3\text{.}\)
    Solution.
    Since factorials come before products in the order of operations Definition 2.1.20, we have
    \begin{equation*} 2 \times 3! = 2 \times (3\times 2 \times 1) = 2 \times 6 = 12\text{.} \end{equation*}
  3. Evaluate \((2n)!\) when \(n=3\text{.}\)
    Solution.
    Since parentheses come first in the order of operations, we calculate the product first to get
    \begin{equation*} (2 \times 3)! = 6! = 720\text{,} \end{equation*}
    as in (a).
Now it is your turn to work with factorials.

Activity 2.2.D Factorials.

On this problem, you may only use technology to verify your answers. All letters represent positive integers.
  1. Evaluate \(4!\)
  2. Evaluate \(3(k+1)!\) when \(k=3\text{.}\)
  3. Write as a single factorial: \(8(7!)\)
  4. Make a conjecture about how to simplify \(n(n-1)!\text{.}\)
  5. Make a conjecture about how to simplify \((m+1)m!\text{.}\)
Be sure to complete Activity 2.2.D because we are about to reveal some of the answers.

Example 2.2.22 Simplifying \(n(n-1)!\)

 
  1. Write as a single factorial: \(7(6!)\)
    Solution.
    We have
    \begin{equation*} 7(6!) = (7)\underbrace{(6)(5)(4)(3)(2)(1)}_{6!} = \underbrace{(7)(6)(5)(4)(3)(2)(1)}_{7!}=7! \end{equation*}
  2. Write as a single factorial \(n(n-1)!\)
    Solution.
    Similarly, we have
    \begin{equation*} \begin{aligned} n((n-1)!) &= (n)\underbrace{(n-1)(n-2)\cdots(3)(2)(1)}_{(n-1)!} \\ &= \underbrace{(n)(n-1)(n-2)\cdots(3)(2)(1)}_{n!}\\ & = n! \end{aligned} \end{equation*}
  3. Write as a single factorial \((m+1)m!\)
    Solution.
    Similarly, we have
    \begin{equation*} \begin{aligned} (m+1)(m!) &= (m+1)\underbrace{(m)(m-1)\cdots (3)(2)(1)}_{m!} \\ &= \underbrace{(m+1)(m)(m-1)\cdots(3)(2)(1)}_{(m+1)!}\\ &=(m+1)! \end{aligned} \end{equation*}
You may also leave factorials in your answers.

Remark 2.2.23 Not evaluating counts, version 2.

Unless stated otherwise, when counting, you may leave any answer greater than twenty in a format that could easily be evaluated on a calculator. In particular, your answer may involve addition, subtraction, multiplication, division, factorials, and parentheses.

Subsection 2.2.D Exercises

Subsubsection Exercises for 2.2.ACounting with Steps and Cases

When counting, follow Remark 2.2.23. In particular, if the answer is greater than 20, leave it in a format that could be easily evaluated on a calculator.

1. Practice.

As in Activity 2.2.B, a password is a string of eight characters. Use steps to count how many different passwords are possible in each situation.
  1. All of the characters are lower-case letters (\(\str{a}\)-\(\str{z}\)).
  2. The characters must be alpha-numeric (\(\bs{0}\)-\(\str{9}\text{,}\) \(\str{a}\)-\(\str{z}\text{,}\) \(\str{A}\)-\(\str{Z}\)).
  3. The first character must be an uppercase letter (\(\str{A}\)-\(\str{Z}\)), and the rest of the characters are digits (0-9).
Check.
  1. \(26^8 = \underbrace{26 \times 26 \times \cdots \times 26}_{8 \text{ times } }\text{.}\) See Definition 2.4.15 for additional explanation of exponential notation.
  2. Hint: \(10+26+26 = 62\) possible characters in each of the eight spaces.
  3. Hint: The answer is of the form \(26 \times 10 \times 10 \times \cdots \times 10\text{.}\)

2. Practice.

In this problem, a Personal Identification Number (PIN) is a string of digits. Use steps to count how many different PINs are possible in each situation.
  1. Each PIN has length four.
  2. Each PIN has length eight.
  3. Each PIN has length four, but the digits cannot be repeated.
  4. Each PIN has length eight, but digits may not be repeated.
Check.
  1. \(\displaystyle 10^4\)
  2. Hint: Now the length is eight.
  3. \(\displaystyle (10)(9)(8)(7)\)
  4. Hint: Continue as in the previous part.

3. Practice.

 
  1. How many permutations are there of the set \(\{\str{1},\str{2},\str{3}\}\text{?}\) List them using a possibility tree.
  2. Show how to use steps to count the number of permutations of \(\{\str{1},\str{2},\str{3}, \str{4}, \str{5}\}\text{.}\) Hint: Look at Example 2.2.5.
Check.
  1. Six
  2. Hint: You should get \((5)(4)(3)(2)(1)\text{.}\)

4. Practice.

A small technology firm has six designers, ten engineers, 20 analysts, and five business people.
  1. If a tech team has one designer, one engineer, one analyst, and one business person, how many different tech teams are possible?
  2. The CEO proposes that the firm pay up to $30 for a designer and analyst or for an engineer and business person to go to lunch in order to help build community. If every possible pair takes the offer, what will the total cost be to the firm?
Check.
  1. \(\displaystyle (6)(10)(20)(5)\)
  2. Hint: There are \(6(120)\) designer-analyst pairs. Now count how many engineer-business pairs there are. Do not forget to multiply by $30.

5. Understand.

As in Activity 2.2.B, a password is a string of length eight. Use steps to count how many different passwords are possible in each situation.
  1. The first character must be a special character (one of: \(\str{\%}\text{,}\) \(\str{\&}\text{,}\) \(\str{\$}\text{,}\) \(\str{\#}\text{,}\) or \(\str{?}\)), and the rest of the characters are alpha-numeric.
  2. One of the characters must be a special character (one of: \(\str{\%}\text{,}\) \(\str{\&}\text{,}\) \(\str{\$}\text{,}\) \(\str{\#}\text{,}\) or \(\str{?}\)) and the rest are alpha-numeric.
    Hint: Try these steps.
    Step 1: select which space is the special character.
    Step 2: fill in the special character.
    Step 3: fill in the first open space.
    Step 4: fill in the next open space, etc.
Check.
  1. Hints: There are five choices for the special character and then 62 choices for each of the remaining seven spaces. Your answer should look like \(5 \times 62 \times 62 \times \cdots \times 62\text{.}\)
  2. Hint: Follow the hint. There are eight spaces, so there are eight ways to complete Step 1. There are five ways to complete Step 2. For each of the next steps, there are 62 ways to pick the alpha-numeric character.

6. Understand.

Each state of the United States decides on its own format for license plates. All states use only upper case letters (A-Z) and digits and allow repeated characters, such as \(\str{MOM445}\text{.}\) Use steps to count how many license plates are possible in each format.
  1. Minnesota standard license plates are in the format \(\str{ABC123}\) consisting of three uppercase letters followed by three digits.
  2. California standard license plates are in the format \(\str{1ABC234}\) consisting of one digit, then three uppercase letters, and then three digits.
  3. Arizona standard license plates are in an unusual format consisting of strings of six characters, either uppercase letters or digits, with the restriction that the fourth character is always a digit. Some examples are \(\str{ABC1DE}\text{,}\) \(\str{0001AB}\text{,}\) and \(\str{123456}\text{.}\)
Check.
  1. \(\displaystyle 26^3 10^3\)
  2. Hint: This part is similar to the previous part.
  3. Hint: The first character can be any of \(26+10=36\) characters. The other characters also have 36 choices, except the fourth character only has ten choices.

7. Understand.

Telephone numbers in the United States have the format \(\str{201-345-6789}\text{.}\) The first three digits (\(\str{201}\)) are the area code, the next three digits (\(\str{345}\)) are the exchange, and the last four digits (\(\str{6789}\)) are the extension.
  1. Historically, area codes were strings of length three in the format \(\str{ABC}\) where each character was a digit but the first digit \(\str{A}\) could not be \(\bs{0}\) or \(\bs{1}\text{,}\) the second digit \(\str{B}\) had to be \(\bs{0}\) or \(\bs{1}\text{,}\) and the third digit \(\str{C}\) could be any digit. There were a few more restrictions that we ignore here. How many different area codes were there?
  2. I grew up in New Jersey. When I was a child, the entire state of New Jersey shared one area code: \(\str{201}\text{,}\) the smallest possible area code. How many \(\str{201}\) telephone numbers were there if neither the first nor the second digit of the exchange was \(\bs{0}\) or \(\bs{1}\text{?}\) That is, each telephone number is of the form \(\str{201-ABC-DEFG}\) where \(\str{A}\) and \(\str{B}\) can be any digit other than \(\bs{0}\) or \(\bs{1}\) and \(\str{C}\text{,}\) \(\str{D}\text{,}\) \(\str{E}\text{,}\) \(\str{F}\text{,}\) and \(\str{G}\) can be any digit.
  3. My neighborhood in Saint Paul, Minnesota, has historically had telephone numbers in the format \(\str{651-698-DEFG}\) or \(\str{651-699-DEFG}\) where \(\str{D}\text{,}\) \(\str{E}\text{,}\) \(\str{F}\text{,}\) and \(\str{G}\) can be any digit. How many of those telephone numbers are there? Hint: Consider two cases.
Check.
  1. Hint: There are eight choices for \(\str{A}\text{,}\) two choices for \(\str{B}\text{,}\) and ten choices for \(\str{C}\text{.}\)
  2. Hint: Now there are eight choices for \(\str{A}\) and \(\str{B}\) and ten choices for the rest of the characters.
  3. Hint: There are \(10^4\) in each case.

8. Recap.

Do you know …
  1. What a question beginning “how many …” asks for?
  2. When to add and when to multiply when counting?
  3. How to think of a counting problem as a sequence of steps?
  4. How to think of a counting problem as a set of separate cases?
  5. How to combine steps and cases?

9. Explore.

How many permutations of \(\{\str{1},\str{2},\str{3},\str{4},\str{5},\str{6}\}\) satisfy each restriction?
  1. Start with an even number (\(\str{2}\text{,}\) \(\str{4}\text{,}\) or \(\str{6}\))?
  2. Start with the three even numbers followed by the three odd numbers (\(\bs{1}\text{,}\) \(\str{3}\text{,}\) and \(\str{5}\))?
  3. Alternate between even and odd numbers. Hint: Consider cases based on whether the first number is even or odd.
  4. Have \(\str{3}\) always followed by \(\str{6}\text{?}\) Hint: Think of five blanks to fill in with the five objects: \(\bs{1}\text{,}\) \(\str{2}\text{,}\) \(\str{36}\text{,}\) \(\str{4}\text{,}\) and \(\str{5}\text{.}\)
Check.
Note: You should leave your answers unsimplified as part of showing your work.
  1. Hint: The answer is equal to 360.
  2. Hint: The answer is equal to 36.
  3. Hint: The answer is not equal to 36 because there are two cases.
  4. Hint: Follow the hint to get an answer equal to 120.

Subsubsection Exercises for 2.2.B When Counting Goes Awry

10. Practice.

In this problem, a Personal Identification Number (PIN) is a string of three characters– \(\bs{0}\text{,}\) \(\bs{1}\text{,}\) \(\str{2}\text{,}\) or \(\str{3}\text{,}\) where the digits appear in nondecreasing order. For example, \(\str{023}\) and \(\str{112}\) are possible PINs but the string \(\str{203}\) is not allowed because \(0\lt 2\text{.}\) Hint: You can think of the digits of a PIN as being arranged from the smallest to the largest.
  1. Draw a possibility tree showing all possible PINs.
  2. How many different PINs are there?
  3. Explain why we cannot use steps Theorem 2.2.3 to count.

11. Practice.

In Example 2.2.8, we counted 19 integers from 0 to 99 that include the digit 5.
  1. What (incorrect) answer would we get from the following cases: Case 1: The integer starts with the digit 5. Case 2: The integer ends with the digit 5.
  2. Why do we get the incorrect answer? Did we forget to count some of the integers, count some integers that we should not have counted, or count some (or all) of the integers more than once?
Check.
  1. 20
  2. We double counted the integer 55.

12. Understand.

In the Handshakes puzzle Activity 1.1.A, we counted the number of handshakes between a group of students. Suppose that there are six students.
  1. Explain why the following count does not work. Reasons might be that we missed counting some of the options, that we counted some options that we shouldn’t have, or that we counted some (or all) options more than once. “Step 1: pick the first student (6 ways). Step 2: pick the second student (5 ways). Since steps multiply Theorem 2.2.3, there are \(6 \times 5=30\) handshakes.”
  2. Explain how to find the correct answer using 30 as a starting point.
Check.
  1. We double count each pair of students.
  2. Hint: We got twice the correct answer.

13. Recap.

Do you know …
  1. When steps do not work and what we might do instead?
  2. When cases do not work, and what we might do instead?
  3. What are three reasons we might get the incorrect answer when counting?

14. Explore.

 
  1. There are 28 students in the discrete class, 32 students in the programming class, and 15 students in both classes. In a list of students who are in at least one of the classes, how many students are on that list? Use cases to count. Hint: Be careful! Once the discrete students are listed, only add programming students who are not already on the list.
  2. Let’s generalize. If there are \(s\) students in the Discrete class, \(t\) students in the Programming class, and \(u\) students in both classes, how many students are in at least one of the classes? State your answer as a conjecture involving \(s\text{,}\) \(t\text{,}\) and \(u\text{.}\) This conjecture is known as the Inclusion-Exclusion Principle.
Check.
  1. 45
  2. Hint: There are \(t-u\) students who are in the Programming class only.

Subsubsection Exercises for 2.2.C Algebra: Factorials

15. Practice.

Show how to calculate each quantity without using technology.
  1. Evaluate \(0!\text{,}\) \(1!\text{,}\) and \(2!\text{.}\)
  2. Evaluate \(10m!\) when \(m=4\text{.}\)
Check.
  1. Note: \(0!=1\) by definition. Then \(1! =1\) and \(2! = (2)(1) = 2\text{.}\)
  2. Hint: Evaluate \((10)(4!)\text{.}\)

16. Practice.

 
  1. How many integers are in the set \(\{0,1,2,3\}\text{?}\)
  2. How many integers are in the set \(\{0,1,2,\ldots,n\}\text{?}\) Your answer should depend on \(n\text{.}\)

17. Practice.

 
  1. You are taking a picture of four friends. How many ways can they line up for the photo? Write your answer as a factorial.
  2. A standard deck of playing cards has 52 distinct cards. In how many ways can a deck be ordered? Write your answer as a factorial and then use technology to calculate how large that is.
Check.
  1. \(\displaystyle 4!\)
  2. Hint: Explain why the answer has about 68 digits.

18. Understand.

 
  1. It turns out that \(9!=\)362,880. Use that information to evaluate \(10!\text{.}\)
  2. Write as a single factorial: \(11(10!)\text{.}\)
Check.
  1. Hint: When multiplying \(9!\) by ten, you get another zero at the end.
  2. \(\displaystyle 11!\)

19. Understand.

Factor and simplify \(m!+m(m!)\text{.}\) Hint: See Example 2.2.22.
Check.
Hint: first factor out the \(m!\text{.}\) Then use the hint to further simplify your answer.

20. Recap.

Do you know …
  1. What consecutive means?
  2. What \(n!\) stands for and how to pronounce it?
  3. How to evaluate \(5!\text{?}\)
  4. How \(0!\) is defined?
  5. Where factorials rank in the order of operations?
PrevTopNext