2.1: Counting Methods

Addition Principle

Counting?  You already know how to count or you wouldn’t be taking a college-level math class, right?  Well yes, but what we’ll really be investigating here are ways of counting efficiently.  When we get to the probability situations a bit later in this chapter we will need to count some very large numbers, like the number of possible winning lottery tickets.  One way to do this would be to write down every possible set of numbers that might show up on a lottery ticket, but believe me: you don’t want to do this.

We encounter a wide variety of counting problems every day. There is a branch of mathematics devoted to the study of counting problems such as this one. Other applications of counting include secure passwords, horse racing outcomes, and college scheduling choices. We will examine this type of mathematics in this section

A company that sells customizable cases offers cases for tablets and smartphones. There are 3 supported tablet models and 5 supported smartphone models. The Addition Principle tells us that we can add the number of tablet options to the number of smartphone options to find the total number of options. By the Addition Principle, there are 8 total options.

Multiplication Principle

We will start with an example to illustrate the Multiplication Principle.

Example 2

Suppose at a particular restaurant you have three choices for an appetizer (soup, salad or breadsticks) and five choices for a main course (hamburger, sandwich, quiche, fajita or pasta). If you are allowed to choose exactly one item from each category for your meal, how many different meal options do you have?

---

Solution

Solution 1: One way to solve this problem would be to systematically list each possible meal:

soup + hamburger	soup + sandwich	soup + quiche
soup + fajita	soup + pizza	salad + hamburger
salad + sandwich	salad + quiche	salad + fajita
salad + pizza	breadsticks + hamburger	breadsticks + sandwich
breadsticks + quiche	breadsticks + fajita	breadsticks + pizza

Assuming that we did this systematically and that we neither missed any possibilities nor listed any possibility more than once, the answer would be 15.  Thus you could go to the restaurant 15 nights in a row and have a different meal each night.

Solution 2: Another way to solve this problem would be to list all the possibilities in a table:

	hamburger	sandwich	quiche	fajita	pizza
soup	soup+burger
salad	salad+burger
bread	etc.

In each of the cells in the table we could list the corresponding meal: soup + hamburger in the upper left corner, salad + hamburger below it, etc.  But if we didn’t really care what the possible meals are, only how many possible meals there are, we could just count the number of cells and arrive at an answer of 15, which matches our answer from the first solution.  (It’s always good when you solve a problem two different ways and get the same answer!)

Solution 3: We already have two perfectly good solutions.  Why do we need a third?  The first method was not very systematic, and we might easily have made an omission.  The second method was better, but suppose that in addition to the appetizer and the main course we further complicated the problem by adding desserts to the menu: we’ve used the rows of the table for the appetizers and the columns for the main courses—where will the desserts go?  We would need a third dimension, and since drawing 3-D tables on a 2-D page or computer screen isn’t terribly easy, we need a better way in case we have three categories to choose form instead of just two.

So, back to the problem in the example.  What else can we do?  Let’s draw a tree diagram:

This is called a “tree” diagram because at each stage we branch out, like the branches on a tree.  In this case, we first drew five branches (one for each main course) and then for each of those branches we drew three more branches (one for each appetizer).  We count the number of branches at the final level and get (surprise, surprise!) 15.

If we wanted, we could instead draw three branches at the first stage for the three appetizers and then five branches (one for each main course) branching out of each of those three branches.

Video Solution (1 min 39 secs – CC) Another example starts after 1:39 mark on the video.

OK, so now we know how to count possibilities using tables and tree diagrams.  These methods will continue to be useful in certain cases, but imagine a game where you have two decks of cards (with 52 cards in each deck) and you select one card from each deck.  Would you really want to draw a table or tree diagram to determine the number of outcomes of this game?

Let’s go back to the previous example that involved selecting a meal from three appetizers and five main courses, and look at the second solution that used a table. Notice that one way to count the number of possible meals is simply to number each of the appropriate cells in the table, as we have done above.  But another way to count the number of cells in the table would be multiply the number of rows (3) by the number of columns (5) to get 15.  Notice that we could have arrived at the same result without making a table at all by simply multiplying the number of choices for the appetizer (3) by the number of choices for the main course (5). We generalize this technique as the Multiplication Principle, or sometimes called the Basic Counting Rule.

The Multiplication Principle can be extended when there are more than two categories by applying it repeatedly, as we see in the next example.

Permutations

The Multiplication Principle can be used to solve a variety of problem types. One type of problem involves placing objects in order. We arrange letters into words and digits into numbers, line up for photographs, decorate rooms, and more. An ordering of objects is called a permutation.

To solve permutation problems, it is often helpful to draw line segments for each option. That enables us to determine the number of each option so we can multiply. For instance, suppose we have four paintings, and we want to find the number of ways we can hang three of the paintings in order on the wall. We can draw three lines to represent the three places on the wall.

There are four options for the first place, so we write a 4 on the first line.

After the first place has been filled, there are three options for the second place so we write a 3 on the second line.

After the second place has been filled, there are two options for the third place so we write a 2 on the third line. Finally, we find the product.

There are 24 possible permutations of the paintings.

In the above example, we needed to calculate $9\cdot 8\cdot \cdots 3\cdot 2\cdot 1$. This calculation shows up often in mathematics, and is called a factorial, and is notated 9!.

If you are wondring why 0!=1 we can think of 0! as representing the number of ways to arrange 0 items, and there is exactly 1 way to do this (do nothing).

For some permutation problems, it is inconvenient to use the Multiplication Principle because there are so many numbers to multiply. Fortunately, we can solve these problems using a formula. Before we learn the formula, let’s look at two common notations for permutations. If we have a set of n objects and we want to choose r objects from the set in order, we write $P\left(n,r\right)$. Another way to write this is $nPr$, a notation commonly seen on computers and calculators. To calculate $P\left(n,r\right)$, we begin by finding $n!$, the number of ways to line up all n objects. We then divide by $\left(n-r\right)!$ to cancel out the $\left(n-r\right)$ items that we do not wish to line up.

Let’s see how this works with a simple example. Imagine a club of six people. They need to elect a president, a vice president, and a treasurer. Six people can be elected president, any one of the five remaining people can be elected vice president, and any of the remaining four people could be elected treasurer. The number of ways this may be done is $6\cdot 5\cdot 4=120$. Using factorials, we get the same result.

$$\frac{6!}{3!}=\frac{6\cdot 5\cdot 4\cdot 3!}{3!}=6\cdot 5\cdot 4=120$$

There are 120 ways to select 3 officers in order from a club with 6 members. We refer to this as a permutation of 6 taken 3 at a time. The general formula is as follows.

$$P\left(n,r\right)=\frac{n!}{\left(n-r\right)!}$$

Note that the formula stills works if we are choosing all n objects and placing them in order. In that case we would be dividing by $\left(n-n\right)!$ or $0!$, which we said earlier is equal to 1. So the number of permutations of n objects taken n at a time is $\frac{n!}{1}$ or just $n!$.

In practicality, we usually use technology rather than factorials or repeated multiplication to compute permutations. Although with some calculations the technology may fail as the numbers can get extremely large.

Combinations

So far, we have looked at problems asking us to put objects in order. There are many problems in which we want to select a few objects from a group of objects, but we do not care about the order. When we are selecting objects and the order does not matter, we are dealing with combinations. A selection of r objects from a set of n objects where the order does not matter can be written as $C\left(n,r\right)$. Just as with permutations, $C\left(n,r\right)$ can also be written as ${}_{\mathrm{n}}{C}_{\mathrm{r}}=$. In this case, the general formula is as follows.

$$C\left(n,r\right)=\frac{n!}{r!\left(n-r\right)!}$$

An earlier problem considered choosing 3 of 4 possible paintings to hang on a wall. We found that there were 24 ways to select 3 of the 4 paintings in order. But what if we did not care about the order? We would expect a smaller number because selecting paintings 1, 2, 3 would be the same as selecting paintings 2, 3, 1. To find the number of ways to select 3 of the 4 paintings, disregarding the order of the paintings, divide the number of permutations by the number of ways to order 3 paintings. There are $3!=3\cdot 2\cdot 1=6$ ways to order 3 paintings. There are $\frac{24}{6}$, or 4 ways to select 3 of the 4 paintings. This number makes sense because every time we are selecting 3 paintings, we are not selecting 1 painting. There are 4 paintings we could choose not to select, so there are 4 ways to select 3 of the 4 paintings.

In the preceding Try it Now problem we assumed that the 19 members of the Defense Subcommittee were chosen without regard to party affiliation.  In reality this would never happen: if Republicans are in the majority they would never let a majority of Democrats sit on (and thus control) any subcommittee.  (The same of course would be true if the Democrats were in control.)  So let’s consider the problem again, in a slightly more complicated form:

A coach selects three players from a team of 8 to represent the team at an award banquet is a combination problem as the three players selected do not have to be in any particular order. A problem where a coach select 3 players from a team of 8, but those three players will be wearing different uniforms would be a permutation problem as the same 3 players can be selected in a variety of ways by changing what uniform each wears (here the order was based on them having something different … we could have they were selected and arranged in order from #1 to #3.

Exercises

1. A person owns 4 pairs of pants, 8 shirts, 2 pairs of shoes, and 1 jacket. How many different outfits can they wear to school if they must wear one of each item?
   
   Answer (click to Show/Hide)

   $4\cdot 8\cdot 2\cdot 1=64$ outfits

2. At a restaurant you can choose from 3 appetizers, 8 entrees, and 2 desserts. How many different three-course meals can you have if you must choose one of each?
3. How many three-letter “words” can be made from 4 letters “FGHI” if
   1. Repetition of letters is allowed
   2. Repetition of letters is not allowed
   Answer (click to Show/Hide)

   $\begin{array}{l}a.4\cdot 4\cdot 4=64\\ b.4\cdot 3\cdot 2=24\end{array}$

4. How many four-letter “words” can be made from 6 letters “AEBWDP” if
   1. Repetition of letters is allowed
   2. Repetition of letters is not allowed
5. All of the license plates in a particular state feature three letters followed by three digits (e.g. ABC 123). How many different license plate numbers are available to the state’s Department of Motor Vehicles?
   
   Answer (click to Show/Hide)

   $26\cdot 26\cdot 26\cdot 10\cdot 10\cdot 10=17,576,000$

6. A computer password must be eight characters long.  How many passwords are possible if only the 26 letters of the alphabet are allowed?
7. A pianist plans to play 4 pieces at a recital. In how many ways can she arrange these pieces in the program?
   
   Answer (click to Show/Hide)

   ${}_4{P}_4=4\cdot 3\cdot 2\cdot 1=24$ possible orders

8. In how many ways can first, second, and third prizes be awarded in a contest with 210 contestants?
9. Seven Olympic sprinters are eligible to compete in the 4 x 100 m relay race for the USA Olympic team. How many four-person relay teams can be selected from among the seven athletes?
   
   Answer (click to Show/Hide)

   Order matters. ${}_7{P}_4=840$ possible teams

10. A computer user has downloaded 25 songs using an online file-sharing program and wants to create a CD-R with ten songs to use in his portable CD player. If the order that the songs are placed on the CD-R is important to him, how many different CD-Rs could he make from the 25 songs available to him?
11. In western music, an octave is divided into 12 pitches (notes). For the film Close Encounters of the Third Kind, director Steven Spielberg asked composer John Williams to write a five-note theme, which aliens would use to communicate with people on Earth. If we stay in the same octave and disregard rhythm changes, how many five-note themes are possible if no pitch (note) is repeated?
    Answer (click to Show/Hide)

    Order matters. ${}_{12}{P}_5=95,040$ possible themes

12. In the early twentieth century, proponents of the Second Viennese School of musical composition (including Arnold Schönberg, Anton Webern and Alban Berg) devised the twelve-tone technique, which utilized a tone row consisting of all 12 pitches from the chromatic scale in any order, but with no pitches repeated in the row.  Disregarding rhythm and octave changes, how many tone rows are possible?
13. In how many ways can 4 pizza toppings be chosen from 12 available toppings?
    
    Answer (click to Show/Hide)

    Order does not matter. ${}_{12}{C}_4=495$

14. At a baby shower 17 guests are in attendance and 5 of them are randomly selected to receive a door prize.  If all 5 prizes are identical, in how many ways can the prizes be awarded?
15. In the 6/50 lottery game, a player picks six numbers from 1 to 50. How many different choices does the player have if order doesn’t matter?
    
    Answer (click to Show/Hide)

    ${}_{50}{C}_6=15,890,700$

16. In a lottery daily game, a player picks three numbers from 0 to 9. How many different choices does the player have if order doesn’t matter?
17. A jury pool consists of 27 people. How many different ways can 11 people be chosen to serve on a jury and one additional person be chosen to serve as the jury foreman?
    
    Answer (click to Show/Hide)

    We have two things happening here. We need the number of ways to select 11 to serve on the regular jury out of the 27. Once those 11 are selected we are left with 16 choices for the one to be selected as foreman.
    ${}_{27}{C}_{11}\cdot 16=208,606,320$

    An alternative approach to this is look at how many ways there are to select 12 jurors out of the 27 and then multiply by the number of ways to select 1 of those 12 to be the forman. Both yield the same results (try this to see if you get the same answer).

18. The United States Senate Committee on Commerce, Science, and Transportation consists of 23 members, 12 Republicans and 11 Democrats.  The Surface Transportation and Merchant Marine Subcommittee consists of 8 Republicans and 7 Democrats.  How many ways can members of the Subcommittee be chosen from the Committee?

Attributions

• This page contains modified content from David Lippman, “Math In Society, 2nd Edition.” Licensed under CC BY-SA 4.0.
• This page contains modified content from “College Algebra 2017.” Lumen Learning. Licensed under CC BY 4.0.
• This page contains content by Robert Foth, Math Faculty, Pima Community College, 2021. Licensed under CC BY 4.0.