Introduction to Counting

Introduction

Counting the number of objects with certain properties will be an important part of our probability section later in the course. For example, we may want to count the number of allowed phone numbers in the United States. Or we may want to count the number of ways to arrange people at a restaurant. To be able to count these things and many other things, we will look at the product rule, sum rule, and subtraction rule.

Product Rule

Example 1

First consider this problem: Suppose two groups arrive at a restaurant at the same time. The restaurant has 4 tables. Assuming that all tables are large enough to fit each group, how many different ways can the two groups be seated?

Think about this problem on your own a bit and try to come up with an answer before looking at the explanation below!

To solve this, let's first imagine seating the first group at the first table. Then, we could seat the second group at either table 2, table 3, or table 4. Alternatively, we could place the first group at table 2. Then we could place the second group at table 1, table 3, or table 4.

This is depicted below, with green representing the first group and orange representing the second group.

Continuing this pattern we can see that there are 12 ways to seat the two groups. (If you don't see this, try drawing out the rest of the seating arrangements).

However, while drawing a picture is helpful for gaining some intuition, it is not always practical. Suppose the problem was as stated above but with 10 tables instead of just 4 tables. This would quickly get complicated and tedious to visualize in this way. Hence, we have the product rule.

There are 4 ways to seat the first group. Then, once the first group has been seated, there are 3 ways to seat the second group (the second group cannot be seated at the table the first group is seated at as that table is already occupied). This gives us a total of $4 \cdot 3 = 12$ ways of seating the two groups.

We can generalize this product rule: if there are $\textbf{a}$ ways of doing one thing, and $\textbf{b}$ ways of doing another thing, then there are $\textbf{a} \cdot \textbf{b}$ ways of doing both things.

Example 2

There are 10 digits in a phone number. Each digit is number between 0 and 9. How many different phone numbers are there?

There are 10 ways to choose the first digit in a phone number. Then there are 10 ways to choose the second digit, 10 ways to choose the third digit and so forth. Thus there are $10 \cdot 10 \cdot ... 10 = 10^{10}$ possible phone numbers in the United States.

Practice Problems

An area code is the first three digits of a phone number. For example, for a phone number 123-456-7890 the area code is 123.
a. How many different area codes are there?
b. How many phone numbers are there with a particular area code? (For concreteness, you can imagine this area code to be 123)

2. A parking lot has 8 parking spaces. How many ways are there to park 4 cars in the parking lot?

3. A menu lists 8 different sandwiches and 7 types of soups. A lunch special includes a soup and a sandwich. How many different ways are there to select a lunch special?

Sum Rule

Example

Suppose that I want to enroll in a class and I can only enroll in one class. I can choose a computer science class or a writing class. 7 computer science classes and 9 writing classes are offered. How many different classes are there that I could enroll in?

There are 7 computer science classes and 9 writing classes. All of these classes are distinct. In other words, none of the computer science classes are also a writing class. So there are $7 + 9 = 16$ classes I have to choose from to enroll in.

Here we implicitly used the sum rule, if there are $\textbf{a}$ ways of doing one thing, and $\textbf{b}$ ways of doing another thing, and $\textbf{a}$ and $\textbf{b}$ are distinct, then there are $\textbf{a} + \textbf{b}$ total ways to so something.

a and b must be distinct for the sum rule to hold!

Practice Problems

4. A student can choose to read a book off of 3 lists. Assuming no book appears on more than one list, how many books can the student choose from if there are 17 books on the first list, 32 books on the second list, and 8 books on the third list?

5. A string consists of lowercase letters and numbers. For example, "g7h5dee" is a string of length 7. How many strings of length 9 are there that either start with 2 numbers or start with the letters 'ab'?

Hint: You will need to use both the sum rule and the product rule.

Subtraction Rule

Example 1

You should have noticed that a and b being distinct was emphasized in the discussion of the sum rule. Suppose that a and b were not distinct:

How many bit strings of length 3 are there that start with a 1 or end with a 1? (Note: a bit string is a sequence of 1s and 0s, for example 101 is a bit string of length 3).

If we used the sum rule to solve this problem, we would first count the number of bit strings of length 3 that start with a 1. Using the product rule this gives us $2 \cdot 2 = 4$ bit strings.

Then we would count the number of bit strings of length 3 that end with a 1. Using the product rule, this should also give us 4 bit strings.

Finally, putting it all together with the sum rule we would say there are $4 + 4 = 8$ bit strings of length 3 that start with a 1 or end with a 1. However, this is incorrect.

Listed below are the possible bit strings of length 3. Highlighted are the bit strings that either start with a 1 or end with a 1.

We can see that there are only 6 bit strings of length 3 that either start with a 1 or end with a 1.

This is not because the sum rule does not work, but rather, because we have improperly used the sum rule. Recall that the sum rule states there are a + b ways to do something when a and b are distinct. In this case a is bit strings that start with a 1 and b is bit strings that end with a 1. a and b are not distinct because a bit string may fall into both categories. That is, a bit string may both start and end with a 1. Explicitly, the bit strings 101 and 111 both start and end with a 1.

To resolve this we need the subtraction rule, perhaps more commonly referred to as the principle of inclusion-exclusion.

We want to count the bit strings that start or end with 1. Visually, this is all the bit strings in the venn diagram below.

But when we try to add bit strings that start with a 1 and bit strings that end with a 1 using the sum rule, we will count the bit strings that both start and end with a 1 twice:

However, we have added the middle section in green , the bit strings that both start and end with 1, twice.

Therefore, we must subtract the number of elements that start and end with a 1 from our total as, we have added these into our total twice.

We are left with 6 bits of length 3 that start or end with a 1.

Generalized the subtraction rule states that if there are $\textbf{a}$ ways of doing one thing, and $\textbf{b}$ ways of doing another thing, and $\textbf{a}$ and $\textbf{b}$ are not distinct, then there are $\textbf{a} + \textbf{b}$ minus the number of ways common to a and b ways to do something.

Example 2

In a survey of 1000 people it was found that 206 people own dogs, 125 people own cats, 12 people own turtles, and 31 people own both a dog and a cat. How many people own a dog or a cat?

This question contains some extraneous information. We care about people in our sample who own dogs or cats. We are told that 206 people own dogs, 125 people own cats, and 31 people own both a dog and a cat.

Because dog and cat owners are not distinct (there are people who own both a dog and a cat), we use the subtraction rule.

The subtraction rule tells us to add the number of people who own a cat and the number of people who own a dog, and subtract the number of people who own both a cat and a dog to find the total number of people who own a cat or a dog. Since $205 + 125 - 31 = 300$ we conclude that $300$ people own a dog or a cat.

Practice Questions

6. Use the product rule to prove that the 8 bit strings of length 3 listed in example 1 are all the bit strings of length 3. In other words, prove that we haven't forgotten to list any bit strings of length 3.

7. How many strings of 9 English letters are there that start with a vowel or end with a vowel?

8. How many positive integers not exceeding 100 are divisible by 2 or 3?