Skip to main content

Section 2.2 Basic Counting Rules

A Theoretical Approach.

The simulations that we saw in the last section can be thought of as an experimental approach to understanding a random process. While this is a good way to investigate a random process, it can be time consuming and will yield different results each time it is performed, due to its random nature.

An alternative approach is to be more theoretical. Instead of simulating the process, we try to understand the process by counting the number of different outcomes that could happen and the number of outcomes that lead to each value of the response variable in which we are interested. In order to use this more theoretical approach, which we will talk more about in Section 2.3, we first need to know how to count.

In this section we will introduce several important counting rules. Many of these rules may be familiar to you already. Some of them, however, will probably be new. We will focus not only on understanding the formulas that go with these counting rules, but also when to use each rule.

Subsection 2.2.1 Sets and the Addition Rule

In this first section of the lesson, we will remind you of one of the most basic counting rules: the addition rule. We will also introduce the idea of set notation.

To see this counting rule in action, consider the following example.

You have won a church raffle. The winning ticket entitles you to choose either one of eight possible home-made pies, or one of six types of home-made cakes. In how many ways can you make your choice?

Solution

Since you may choose either a pie or a cake, and none of your choices are both a pie and a cake, you have \(8+6=14\) choices, according to the addition rule.

Note the emphasized word or in the above solution. The addition rule can be thought of as going with the word “or” because we have one of two types of objects from which we must choose. In terms of mathematical sets, the word or goes with the notion of a union.

Definition 2.2.3.

The union of two sets, \(A\) and \(B\text{,}\) is \(A\cup B\text{,}\) the set containing all elements that are in \(A\) or in \(B\) (or both).

The union of the pies and the cakes in Example 2.2.2 above is the set of all 14 baked goods from which you can choose your prize. You may have also noticed that the word both was emphasized in the solution above. This is because it is important that when we use the addition rule, none of the choices be members of both groups—that is, none of the elements are in both sets. Being in both sets \(A\) and \(B\) also has a mathematical name.

Definition 2.2.4.

The intersection of two sets, \(A\) and \(B\text{,}\) is \(A \cap B\text{,}\) the set containing all elements that are in both \(A\) and \(B\text{.}\)

One way to keep the union and intersection straight is to associate them with the common English terms. If the word “or” is used, chances are that we are talking about a union. If the word “and” is used, we are probably referring to an intersection. While associating specific English words with the set operations is one way to help remember what each does, sometimes a picture can help even more. When drawing pictures of combinations of sets, we typically use a special type called a Venn diagram.

Definition 2.2.5.

A Venn diagram is a picture used to represent sets and their relationships. Each set is represented by a circle, with the area inside the circle representing the elements that are in the set. The entire diagram is enclosed in a rectangle representing the set of all possible elements, called the universal set.

Perhaps the best way to understand what a Venn diagram is, is to construct an example.

Let \(A = \lbrace a, c, d, e \rbrace\) and \(B = \lbrace d, e, f \rbrace\) be subsets of the universal set \(U = \lbrace a, b, c, d, e, f \rbrace\text{.}\) Draw a Venn diagram representing these sets.

Solution

We draw a box to represent \(U\) and one circle for each of \(A\) and \(B\text{,}\) making sure that there is a region inside both circles. Then we place the elements in the appropriate region as shown below.

A Venn Diagram with two circles, one for A and one for B, which overlap in the middle. Elements a and c are in circle A but not circle B, element f is in circle B but not circle A, elements d and e are in both circles, and element b is not in either circle.
Figure 2.2.7. Venn Diagram

As you can see in the Venn diagram example above, any element that is in the intersection of two sets is in both sets. So if we add together the number of elements in both sets, we will wind up double counting anything in the intersection. To avoid this, we need to make sure that two sets are mutually exclusive before we use the addition rule to count their union.

Definition 2.2.8.

Two sets, \(A\) and \(B\text{,}\) are said to be mutually exclusive if their intersection is empty. Symbolically, we write this as \(A\cap B = \emptyset\text{.}\)

Using these more formal ideas involving sets, we can restate the addition rule as follows.

The next example will give us a little more practice using sets and the addition rule.

Use the sets \(A = \lbrace a, b, c \rbrace\text{,}\) \(B = \lbrace 1, 2, 3 \rbrace\text{,}\) and \(C = \lbrace 1, a, 2, c \rbrace\) to answer the following questions.

  1. Find \(A \cup B\)

  2. Use the addition rule to find \(n(A\cup B)\text{.}\)

  3. Find \(A \cap C\text{.}\)

  4. Can you use the addition rule to find \(n(A\cup C)\text{?}\) Explain.

  5. What are \(A\cup C\) and \(n(A\cup C)\text{?}\)

Solution

  1. \(A\cup B = \lbrace a,b,c,1,2,3 \rbrace\) since those are the elements in \(A\) or \(B\text{.}\)

  2. According to the addition rule, because \(A\) and \(B\) are mutually exclusive, \(n(A\cup B) = n(A) + n(B) = 3 + 3 = 6\text{.}\)

  3. \(A\cap C = \lbrace a,c \rbrace\) because those are the elements in both \(A\) and \(C\text{.}\)

  4. We can not use the addition rule because \(A\cap C\) is not empty.

  5. \(A\cup C = \lbrace a,b,c,1,2 \rbrace\text{.}\) Note that \(n(A\cup C) = 5\) (there are 5 things in \(A\cup C\text{,}\) but \(n(A) + n(C) = 3+4 = 7\)). The addition rule fails because the intersection was not empty.

Figure 2.2.11. Sets and the Addition Rule I
Figure 2.2.12. Sets and the Addition Rule II

Consider the following sets:

\begin{equation*} A = \lbrace 1, 3, x, 5, y, 8 \rbrace \qquad B = \lbrace w, 2, x, 5, z, 8 \rbrace \end{equation*}

Question: Find the number of elements in the intersection of these two sets. That is, find: \(n(A\cap B)\text{.}\)

Answer

3

Consider the following sets:

\begin{equation*} A = \lbrace 1, 3, x, 5, y, 8 \rbrace \qquad B = \lbrace w, 2, x, 5, z, 8 \rbrace \end{equation*}

Question: Find the number of elements in the union of these two sets. That is, find: \(n(A\cup B)\text{.}\)

Answer

9

Consider the following sets:

\begin{align*} A = \lbrace x, y, z \rbrace\amp \qquad B = \lbrace 1, 2, 3 \rbrace\amp \quad C = \lbrace a, 1, x \rbrace\\ D = \lbrace a, 2, b \rbrace\amp \qquad E = \lbrace x, a, 3 \rbrace\amp \quad F = \lbrace a, b, c \rbrace \end{align*}

Question: Identify each of the following pairs of sets as mutually exclusive or intersecting.

  1. \(A\) and \(B\)

  2. \(B\) and \(E\)

  3. \(C\) and \(F\)

  4. \(B\) and \(F\)

  5. \(A\) and \(D\)

  6. \(E\) and \(F\)

Answer

  1. \(A\) and \(B\) are mutually exclusive

  2. \(B\) and \(E\) are intersecting

  3. \(C\) and \(F\) are intersecting

  4. \(B\) and \(F\) are mutually exclusive

  5. \(A\) and \(D\) are mutually exclusive

  6. \(E\) and \(F\) are intersecting

Subsection 2.2.2 Inclusion/Exclusion Rule

The addition rule only applies if the two sets whose union we are counting are mutually exclusive. What do we do then if we are asked to count the union of two sets that are not mutually exclusive?

Mary is enrolled in a statistics class and a religion class this term. There are 23 total students, including Mary, in her statistics class. There are 34 in her religion class. Again including Mary, 10 people are taking both classes. How many people are in the two classes combined?

Solution

If the two classes were mutually exclusive, then we could use the addition rule to get \(23+34 = 57\)57 total people. However, doing this would double-count the 10 people who took both classes. To remedy this, we compute \(23+34-10=47\text{,}\) subtracting out those who were double-counted.

In the above example, those who were in both classes are included in both the 23 and the 34. So to make up for the fact that they were counted twice, we have to subtract them back out, or exclude them, to get the final total.

You have already seen the inclusion/exclusion rule at work when you worked with contingency tables in Subsubsection 1.2.1.3. Consider the following example.

Those wishing to take a driving test at a certain DMV office are asked what type of vehicle they will be driving, and what history of driving they have. Use the contingency table below, which summarizes their responses, to answer the following questions.

car van truck
\(\lt\) 1 year 19 2 11
1-20 years 7 13 7
20+ years 9 3 1
Table 2.2.19. DMV Responses

  1. How many people indicated that they drive a van?

  2. How many people indicated that they drive a van and have between 1 and 20 years driving experience?

  3. How many people indicated that they drive a van or have between 1 and 20 years driving experience?

Solution

  1. The first question can be answered using the addition rule. There are three “sets” of individuals which together make up the set “drive a van.”These are:

    • “Drive a van” and “less than 1 year experience” — 2 drivers

    • “Drive a van” and “1-20 years experience” — 13 drivers

    • “Drive a van” and “20+ years experience” — 3 drivers

    Adding these all together yields \(2+13+3 = 18\) drivers.

  2. This is an intersection. The intersection of “drives a van” and “1-20 years experience” is the cell with 13 drivers in it.

  3. Here we need to use inclusion/exclusion. If we add the “van drivers”, 18 from (a), to those with “1-20 years of experience”, \(7+13+7 = 27\text{,}\) we double count those from (b) who both drive a van and have 1-20 years experience. Using inclusion/exclusion, our answer is \(18 + 27-13 = 32\text{.}\)

Figure 2.2.20. Inclusion/Exclusion I
Figure 2.2.21. Inclusion/Exclusion II

In a survey of 200 Americans, people were asked two questions. They were first asked if they lived in an urban, suburban, or rural area. Next, they were asked if they had a large garden, small garden, or no garden at all. The results of this survey are tabulated below.

Urban Suburban Rural
Large Garden 7 18 13
Small Garden 12 42 6
No Garden 51 47 4
Table 2.2.23. Living Situation and Garden Size

Question: How many of the survey participants live a rural area or have a large garden?

Answer

48

In a survey of 200 Americans, people were asked two questions. They were first asked if they lived in an urban, suburban, or rural area. Next, they were asked if they had a large garden, small garden, or no garden at all. The results of this survey are tabulated below.

Urban Suburban Rural
Large Garden 7 18 13
Small Garden 12 42 6
No Garden 51 47 4
Table 2.2.25. Living Situation and Garden Size

Question: How many of the survey participants have a small garden or live in an urban area?

Answer

118

In a survey of 200 Americans, people were asked two questions. They were first asked if they lived in an urban, suburban, or rural area. Next, they were asked if they had a large garden, small garden, or no garden at all. The results of this survey are tabulated below.

Urban Suburban Rural
Large Garden 7 18 13
Small Garden 12 42 6
No Garden 51 47 4
Table 2.2.27. Living Situation and Garden Size

Question: How many of the survey participants live a suburban area or have no garden?

Answer

162

Subsection 2.2.3 The Multiplication Rule

In some instances, a process may have two or more steps, each of which can happen in several different ways. In order to determine the total number of ways that such a multi-step process can happen, we need to use a new rule, called the multiplication rule.

To see how this rule works, let's look at several examples.

A certain model of car comes in seven different colors, with a choice of 3 different engines. If you limit yourself to these options, how many different configurations are possible?

Solution

The process of configuring the car has two steps:

  1. Choose a color — 7 choices

  2. Chose an engine — 3 choices

So the total number of configurations is:

\begin{equation*} 7 \times 3 = 21\text{.} \end{equation*}

To put together your wardrobe on a certain morning, you must select from 5 pairs of slacks, 3 shirts, and 2 pairs of shoes. How many different outfits are possible?

Solution

The process of putting together a wardrobe has three steps:

  1. Choose your pants — 5 different choices

  2. Choose your shirt — 3 choices

  3. Choose your shoes — only 2 choices

So the total number of outfits is:

\begin{equation*} 5\times 3\times 2 = 30\text{.} \end{equation*}

Both of the examples above could be modeled using a tree diagram. A tree diagram is a useful way of picturing the multiplication rule. It can also be used to help us work through multiple-step problems that don't fit the multiplication rule above.

Definition 2.2.31.

In a tree diagram, each step in a process is represented by a set of branches leading to the possible outcomes in that step.

Notice that we can model a particular sequence of choices in this process by following a path through the tree. For example, in the second tree diagram, going along the third branch to pant 3, then the first branch to shirt 1, and then the second branch to shoes 2 gives us one complete outfit. Therefore, the total number of outfits is the same as the total number of branches at the last step.

There are some instances where the number of choices we have at a given step depends on the choice we made at the previous step. In these cases the multiplication rule will not work. However, a tree diagram can still be a useful tool for counting the total number of ways to complete such a process.

A certain vacation package allows you to pick from three destinations: Hawaii, Florida, and Alaska. There are two resorts available in Hawaii, three in Florida, and one in Alaska. How many choices are available to you in this vacation package?

Solution

This process can be broken up into two steps:

  1. pick a destination (there are three of them)

  2. pick a resort (the number depends on the destination chosen in step 1)

A three with one branch from the starting point for each destination, Hawaii, Florida, and Alaska. Hawaii has two branches for its two resorts, Florida has three branches for its three resorts, and Alaska has one branch.
Figure 2.2.36. Vacations

Because the number of options in step 2 depends on our choice in step 1, we can not use the multiplication rule. Instead, we create a tree diagram as shown to the right. Note that there are a total of six branches in the last step, so there are six different choices in this vacation package. The tree diagram allows us to represent the different number of choices that are available depending on our destination.

Figure 2.2.37. Multiplication Rule and Tree Diagrams I
Figure 2.2.38. Multiplication Rule and Tree Diagrams II

A cable company offers a special deal in which subscribers can choose one of three base packages, add on one of four different special movie channels and finally choose to either upgrade to a DVR or receive $5 off their monthly bill for six months.

Question: How many different packages are available under this special deal?

Answer

24

A value meal consists of your choice of one sandwich, one drink, and one side. The restaurant offers four different sandwiches, six types of drink, and four sides.

Question: How many different value meals are possible?

Answer

96

A new car comes in your choice of three engine types. The highest performing engine is only available with a manual transmission. The other two engines are available with either manual or automatic transmissions.

Question: How many different choices of engine and transmission are available for this car?

Answer

5

Subsection 2.2.4 Factorials

Let's look at an example that gives a special case of the multiplication rule.

You wish to arrange your four most treasured possessions: your troll doll, Darth Vader action figure, toy Ewok, and GI Joe doll, in a row on your desk. In how many ways can you order these four items?

Solution

This is an example of the multiplication rule using the following steps.

  1. Chose which of the 4 items to place first (4 choices)

  2. Choose which of the 3 remaining items to place 2nd (3 choices)

  3. Choose which of the 2 remaining items to place 3rd (2 choices left)

  4. Choose which of the 1 remaining items to place at the end of the row (only one choice).

Therefore, according to the multiplication rule, the number of orderings is:

\begin{equation*} 4\times 3\times 2 \times 1 = 24\text{.} \end{equation*}

Notice that because we were selecting from our group of items without replacing them, the number of choices went down by one each time. When we use the multiplication rule with this sort of process, we wind up multiplying the numbers between 1 and the original number of choices. This product has a special name.

Definition 2.2.43.

For any positive integer \(n\text{,}\) \(n!\) (read “\(n\) factorial”) is the product of the numbers between \(1\) and \(n\text{.}\) That is:

\begin{equation*} n! = n\times(n-1)\times \cdots \times 2\times 1\text{.} \end{equation*}

Note that \(0!\) is defined to be 1.

In the next example we practice computing factorials. Note how quickly the value of a factorial grows as \(n\) grows. Also, note that when dividing factorials, canceling can be a very useful tool.

Find the value of each expression below.

  1. \(5!\)

  2. \(8!\)

  3. \(\frac{8!}{5!}\)

Solution

Using the definition above,

  1. \(5! = 5\times 4\times 3\times 2\times 1 = 120\)

  2. \(8! = 8\times 7\times 6\times 5! = 336\times 120 = 40320\)

  3. \(\frac{8!}{5!} = \frac{8\times 7\times 6\times 5!}{5!} = \frac{8\times 7\times 6}{1} = 336\text{.}\)

We finish our brief discussion of factorials with one final counting example.

In how many ways can the digits from 0 through 9 be arranged in order?

Solution

There are 10 such digits to be arranged in order. According to the multiplication rule, the total number of orderings is:

\begin{equation*} 10! = 10\times 9\times 8\times 7\times 6\times 5\times 4\times 3\times 2\times 1 = 3628800\text{.} \end{equation*}

Factorials will be used in the next two counting rules, but to see more computations and counting problems involving just the factorial operation, watch the following video examples.

Figure 2.2.46. Factorials
Figure 2.2.47. Factorials

An athletic coordinator needs to arrange six games into the six time slots available during a given week.

Question: In how many ways can the director make up this schedule?

Answer

720

Consider the expression \(\frac{200!}{198!}\text{.}\)

Question: What is the value of this expression? Hint: simplify by canceling before attempting to use your calculator.

Answer

39800

Suppose that the nine Supreme Court justices are lining up to enter the courtroom on the last day of the court term.

Question: In how many ways could they line up?

Answer

362880

Subsection 2.2.5 Permutations

In some counting problems, we will find a process that looks much like the “factorial” questions from the last page, but in which we are not asked to use up or arrange all of the items. One such example can be found below.

Suppose that ten runners compete in a race in which first, second, and third prizes are awarded. In how many ways can these prizes be won?

Solution

Using the multiplication rule, the steps in this process are:

  1. Award first prize to the winner (10 choices since anybody could win).

  2. Award second prize (9 choices since the winner is excluded).

  3. Award third prize (8 choices).

This gives the following total number of ways that the prizes can be won:

\begin{equation*} 10\times 9\times 8 = 720\text{.} \end{equation*}

While the solution to this problem started off looking like a factorial, \(10 \times 9 \times 8\text{,}\) it stopped after 8 because we didn't need to order the remaining seven runners in this race. In general, when we need to count the number of ways to order or arrange \(r\) items chosen from \(n\) possible items, we are using a permutation.

Applying this formula to the foot-race example above, we could have computed:

\begin{equation*} P(10,3) = \frac{10!}{(10-3)!} = \frac{10\times 9\times 8\times 7!}{7!} = 10\times 9\times 8 = 720\text{.} \end{equation*}

Permutations are a general rule that can be used to count the number of ways to complete a process in which the order of completion matters. A race is a good example of when order matters. Another example can be found below.

Six bands have expressed interest in performing at a concert with time slots for three performances. In how many ways can the concert manager make up a schedule for the concert?

Solution

Since there are 6 bands to choose from, and only 3 are needed, and since the order of performance matters (changing the order would make a different schedule) the number of ways to schedule these bands is:

\begin{equation*} P(6,3) = \frac{6!}{3!} = 6\times 5\times 4 = 120\text{.} \end{equation*}

There are a few general rules which work no matter what \(n\) is used in a permutation. Three of these are shown below.

  • \(P(n,n) = \frac{n!}{(n-n)!} = \frac{n!}{0!} = n!\)

  • \(P(n,0) = \frac{n!}{(n-0)!} = \frac{n!}{n!} = 1\)

  • \(P(n,1) = \frac{n!}{(n-1)!} = \frac{n\times (n-1)!}{(n-1)!} = n\)

Additionally, there is a short-cut that can be used instead of the formula. This is:

\begin{equation*} P(n,r) = \underbrace{n\times (n-1) \times \cdots \times (n-r+1)}_{r \text { items}}\text{.} \end{equation*}

Use the rules and short-cut seen above to find each of the following.

  1. \(P(5,1)\)

  2. \(P(17,3)\)

  3. \(P(200,0)\)

Solution

The values of these expressions are:

  1. \(P(5,1) = 5\) (the third rule above)

  2. \(P(17,3) = 17\times 16\times 15 = 4080\) (short-cut formula above)

  3. \(P(200,0) = 1\) (the second rule above)

Figure 2.2.55. Permutations I
Figure 2.2.56. Permutations II

A law school wishes to schedule speaking appointments for 3 of the 9 Supreme Court justices.

Question: In how many ways can this be done if the order of the speeches matters?

Answer

504

A “32-flavors” ice cream shop is offering a special deal. For only $3.00 you can get a large cone with two scoops of your favorite flavors. The only condition is that you can not repeat flavors.

Question: How many ice cream cones are possible if the order in which you choose the scoops matters?

Answer

992

A librarian wishes to designate books in a special collection using five letter codes in which letters are not repeated. Note that there are 26 letters in the list of allowable letters.

Question: How many codes are possible using this scheme?

Answer

7,893,600

Subsection 2.2.6 Combinations

Permutations are particularly useful when the order in which we select individuals makes a difference—such as in running a race or creating a schedule. But order does not always matter, as seen in the next example.

You have two extra movie tickets and wish to share them with two of your four good friends. In how many ways can you pick the friends to go with you to the movies?

Solution

Let's say that your friends names are: Alice, Bob, Candace, and David. If you try to count this using a permutation, you get:

\begin{equation*} P(4,2) = 4\times 3 = 12\text{.} \end{equation*}

Unfortunately, this is not the correct answer. Consider the actual list of possible choices that this produces.

AB AC AD BA BC BD
CA CB CD DA DB DC
Table 2.2.61. Possible Selections

Notice that each pair appears twice. For example, AB and BA are counted separately. This is because in a permutation, the order in which we hand out the tickets makes a difference. But really, we don't care who got the first ticket—we just want to know who is going. Since there are two of each possible pairs, the actual number of ways to pick the two friends to go with us is:

\begin{equation*} \frac{P(4,2)}{P(2,2)} = \frac{12}{2} = 6\text{.} \end{equation*}

In the example above, we arrived at the final solution using two steps. First, we counted the number of ways to pick the friends to go with us if the order did matter, in this case it was 12. Then we counted the number of ways that those two friends could be arranged, which was 2. Finally, we divide the 12 ordered ways by the 2 different orderings to get a total of 6 ways to choose our two friends if the order does not matter. This process can be combined into a single counting rule called a combination.

Applying this formula to the movie ticket example, we get:

\begin{equation*} C(4,2) = \frac{4!}{2!(4-2)!} = \frac{4\times 3\times 2!}{2!\times 2!} = \frac{4\times 3}{2\times 1} = 6\text{.} \end{equation*}

Let's try applying this to another example.

A committee of 10 business executives wishes to choose a sub-committee of 3 to research a certain topic. In how many ways can this sub-committee be chosen?

Solution

The order in which a sub-committee is selected does not matter—a person is either on the committee or not on the committee. Therefore, this is a combination and the solution is:

\begin{equation*} C(10,3) = \frac{10!}{3!(10-3)!} = \frac{10\times 9\times 8 \times 7!}{3!\times 7!} = \frac{10\times 9\times 8}{3\times 2\times 1} = 120\text{.} \end{equation*}

As with permutations, there are a few general rules that combinations follow no matter what the value of \(n\) is. Several of these rules are shown below.

  • \(C(n,n) = 1\)

  • \(C(n,1) = n\)

  • \(C(n,r) = C(n,n-r)\)

And finally, a short-cut that can be easier to use than the formula above.

\begin{equation*} C(n,r) = \frac{\overbrace{n\times (n-1) \times \cdots \times (n-r+1)}^{r \text{ values}}}{r!}\text{.} \end{equation*}

We finish with an example of how these rules and shortcuts can be useful.

Use the rules and short-cut seen above to find the value of each expression.

  1. \(C(12,12)\)

  2. \(C(250,1)\)

  3. \(C(12,0)\)

  4. \(C(250,247)\)

Solution

Applying the rules and short-cut seen above, we get the following values.

  1. \(C(12,12) = 1\).

    Here we use the first rule. You could also recognize that there is only one way to pick all 12 of the 12 things we have

  2. \(C(250,1) = 250\).

    We use the second rule.

  3. \(C(12,0) = C(12,12-0) = C(12,12) = 1\).

    We use the third rule and (a) above. We could also note that there is only 1 way to pick nothing

  4. \(C(250,247) = C(250,250-247) = C(250,3) = \frac{250\times 249\times 248}{3\times 2\times 1} = 2573000\).

    We used the third rule and the shortcut formula.

Figure 2.2.65. Combinations I
Figure 2.2.66. Combinations II

A pizza restaurant has a special deal—a large thin-crust pizza with your choice of 4 toppings for only $13.99. The restaurant offers 12 different toppings.

Question: How many different pizzas are possible if the order of the toppings does not matter?

Answer

495

A student needs to make up a class schedule for summer classes. She has 10 possible classes to choose from, and wants to take 3 of them. None of the classes have scheduling conflicts.

Question: How many class schedules are possible?

Answer

120

A church group of 20 young people wishes to select four of their members to plan a mission trip. Every member of the group is interested in being one of the four selected.

Question: In how many ways can the four planners be chosen?

Answer

4845

Subsection 2.2.7 Mixed Counting Techniques

One of the hardest parts of counting problems is determining which rules or combinations of rules to use to answer a given question. Here are a few basic things to remember:

Let's apply these ideas to several examples. Remember that our fist step should always be to identify the rule or rules that we are going to use to count our options.

The back row of Professor Duncan's classroom has only 4 seats. There are 8 students who wish to sit in these seats. In how many ways can the seats be assigned?

Solution

In a seating chart, the order would matter. This must therefore be a permutation, and the solution is:

\begin{equation*} P(8,4) = 8\times 7\times 6\times 5 = 1680\text{.} \end{equation*}

A committee contains 6 men and 3 women. Four members of the committee are selected for a fact-finding junket. In how many ways can these four be selected if three of them are men and one is a woman?

Solution

The order in which we pick members of a committee to go on a trip does not matter—a member either goes on the trip or does not. However, notice that we have two steps to this problem.

  1. Pick the three men to go on the trip.

  2. Pick the one woman to go on the trip.

The number of ways to pick the three men from the 6 male committee members is:

\begin{equation*} C(6,3) = \frac{6\times 5\times 4}{3\times 2\times 1} = 20\text{.} \end{equation*}

The number of ways to pick the one woman is:

\begin{equation*} C(3,1) = 3\text{.} \end{equation*}

Therefore, using the multiplication rule, the total number of ways to pick the four people to go on the junket is:

\begin{equation*} C(6,3)\times C(3,1) = 20\times 3 = 60\text{.} \end{equation*}

Trains arrive at a station in random order from Berlin, Munich, Salzberg, Vienna, and Hamburg. In how many ways can the trains arrive so that the train from Berlin arrives immediately after the train from Salzberg?

Solution

This problem specifically mentions the order of the trains, so the order will matter. However, we are not asked in how many ways the trains can arrive in general, which would be \(P(5,5) = 5!\text{.}\)

Instead, we specify that the Berlin and Salzberg train must arrive one after the other. Symbolically, we want to arrange the following four trains in order: BS, M, V, H. BS is listed together because of the condition mentioned above. We can order these in \(P(4,4) = 4! = 24\) ways.

A deli sells 6 types of salads, 8 types of sandwiches, and 3 types of chips. Picnic baskets can be purchased which contain 4 different items from these 17. How many different picnic baskets can be made to contain at least two different sandwiches?

Solution

This is actually the most challenging problem in this section. The reason is that we have to use both the multiplication rule to split the process into steps, and the addition rule to split the process into cases. Here's how we do it:

  • Case 1.

    Pick two from 8 sandwiches and 2 from the remaining 9 items

    \begin{equation*} C(8,2)\times C(9,2) = \frac{8\times 7}{2\times 1}\times\frac{9\times 8}{2\times 1} = 1008\text{.} \end{equation*}
  • Case 2.

    Pick three sandwiches from 8 available and 1 item from remaining 9

    \begin{equation*} C(8,3)\times C(9,1) = \frac{8\times 7\times 6}{3\times 2\times 1} \times 9 = 504\text{.} \end{equation*}
  • Case 3.

    Pick four sandwiches from 8 available and none of the remaining 9 items

    \begin{equation*} C(8,4)\times C(9,0) = \frac{8\times 7\times 6\times 5}{4\times 3\times 2\times 1}\times 1 = 70\text{.} \end{equation*}

Note that these three cases are mutually exclusive based on the number of sandwiches chosen, and that a picnic basket with at least two sandwiches would fall into one of these cases. So using the addition rule, the total number of picnic baskets is:

\begin{equation*} 1008 + 504 + 70 = 1582\text{.} \end{equation*}
Figure 2.2.75. Mixed Counting Techniques I
Figure 2.2.76. Mixed Counting Techniques II

A restaurant offers a special weekday menu deal. This includes dinner for two with two entrees and one appetizer. The restaurant offers 14 different entrees and six appetizers.

Question: In how many ways can a couple select their meal if they agree to order different entrees and split them?

Answer

546

A congressional committee consists of 12 Democrats and 7 Republicans. They wish to select a subcommittee of 4 members.

Question: In how many ways can this be done if there must be at least one Republican and at least two Democrats on the subcommittee?

Answer

2926

You are in charge of a parade. There are five floats and four marching bands scheduled to participate in the parade. You decide that you want to alternate floats and marching bands, starting with a float.

Question: In how many different ways could you order the floats and marching bands in this parade?

Answer

2880