In this lesson, we are going to talk about counting. With this, we are starting a new section; and at first, it might seem that counting is a simple thing, but it actually turns out that it is extremely important in math. The formal study of counting is called combinatorics, and this course will barely scratch the surface of combinatorics. First, we are going to define the idea of an event; an event is simply something happening. In this lesson, we will learn some principles, like the addition principle and the multiplication principle, which is also known as the fundamental counting principle.
An event is something happening that can occur some number of different ways. If we want, we can denote an event with a symbol (such as E) and similarly for the number of ways (such as n). [Some teachers and textbooks will not use the word `event'
and might use another word or nothing at all to describe this idea. That's fine. The important part is just to be aware of certain things having multiple possible outcomes or choices. All the coming ideas will work fine in any case; `event' is just a
way to describe this formally.]
We can visualize an event (or series of events, as we'll soon see) with a branching line diagram. At each event in the diagram, it splits into its various possible outcomes.
Addition Principle: Let there be two events E1 and E2, where E1 can occur in m ways and E2 can occur in n. If precisely one of the events will occur (not both), the total possible ways for something
to occur is
Multiplication Principle [AKA Fundamental Counting Principle]: Let there be two events E1 and E2, where E1 can occur in m ways and E2 can occur in n. If both events will occur (and they have no effect
on each other), the total possible ways for something to occur is
Pigeonhole Principle: Let there be some event E that can occur in n ways. If the event E happens n+1 times, then at least one of the ways E can occur must happen twice (or more). Equivalently, given n boxes and n+1 objects, if all the objects are
put into the boxes, then at least one box must have (at least) two objects.
When working on counting problems, it can help immensely to draw pictures and diagrams. Being able to visually follow the events and choices will make it much easier to solve problems.
You are camping in a national park. The camp is in the south part of the park. You are going to go on a hike and there are trailheads in the east, north, and west parts of the park. In the east portion, there are five trailheads. In the north portion, there are seven trailheads. In the west portion, there are four trailheads.
How many different hikes are there available to you?
The most difficult part of this problem is probably just the English. If a word is unfamiliar to you but it seems important to what's going on, look it up! The first step to doing any problem is making sense of it, and that includes understanding the vocabulary.
The word `trailhead' is somewhat uncommon, but if we look it up, we discover that it just means "the starting place for a trail". Since the problem is asking about hikes, and a hike takes place on a trail, each trailhead represents a possible hike.
From there, the problem is quite simple. We start off with three initial choices-east, north, or west. Depending on which direction we choose, it determines how many choices we have for a hiking trail.
Since choosing one direction precludes going on hikes from the other directions, we use the addition principle: just add up the number of choices for each direction.
Each direction has the following number of trail choices:
East: 5, North: 7, West: 4
Since you can only choose one category (east or north or west), we add them together to find the total number of choices:
5 + 7 + 4 = 16
Thus there are 16 possible trails to choose, so 16 different hikes.
You are about to buy a new bike. At the store, they sell four different bicycle models. Each model can come in any of the following colors: black, white, red, blue, green, or yellow.
How many different bikes could you buy at the store?
For purchasing the bike, you have two choices to make: the model of the bicycle and the color of the bicycle. Notice that choosing a different choice for either of these qualities will result in a different bike.
Still, the first choice of model has no effect on the second choice for color. Any color can be picked for any of the bike models. Thus, because both choices must occur and neither has any effect on the other, we can use the multiplication principle.
The number of ways the model can be chosen is 4. Count up the colors to find that there are a total of 6 ways to choose a color. Thus, since the two choices do not affect each other, we multiply them:
4 ·6 = 24
You are at a restaurant and about to have dinner. The dinner comes as three courses, and you will order exactly one of each course. The menu has eight different appetizers, twelve different main courses, and five desserts.
How many different ways are there for you to have dinner?
For choosing your dinner, you have three choices to make: which appetizer, which main course, and which dessert. Notice that choosing something different in any of these categories will result in a different dinner.
Still, each choice has no effect on the other choices. You can pick any appetizer and still go on to pick any main course and any dessert, and similarly for the other two. Thus, because each choice must occur and none of them have any effect on the others, we can use the multiplication principle.
The number of choices for the appetizer is 8, the number of choices for the main course is 12, and the number of choices for the dessert is 5. Since each choice does not affect the others, we multiply them:
8 ·12 ·5 = 480
A family is planning a vacation to Anza-Borrego Desert State Park in California. While there, they have two options: they could stay at a campground in a tent, or they could stay at a hotel. There are a total of three different campgrounds and eight different hotels. At each hotel, they have the option of staying in a normal room or a suite.
How many different ways are there for the family to stay at the park?
The family has to begin by making a choice between staying at a campground or a hotel. Choosing a campground means they won't choose a hotel, and choosing a hotel means they won't choose a campground. This means we can separate the two into two different categories and count them separately.
If they stay at a hotel, they also have to choose what type of room they stay in. Since each room type is available at all the hotels, the hotel choice does not affect the room choice, and vice-versa. Thus, we use the multiplication principle to find the total number of ways to stay in a hotel:
Waystostayinahotel: 8 ·2 = 16
Since choosing campground or hotel means the other event will not occur, we use the addition principle: count the number of ways to camp then add it to the number of ways to stay in a hotel:
[#campgroundways] + [#hotelways] = 3 + 16 = 19
Jack Burton needs to take a class on trucking to get his Class A license. There are two different trucking schools he can attend: "Three Storms Trucking School" and "Buckaroo Trucking Institute". If he attends "Three Storms", there are three different teachers he can choose from, each of which has four different timeslots for their classes. If he attends "Buckaroo", there are six different teachers he can choose from, each of which has three different timeslots for their classes.
How many different ways can Jack take a class to earn his trucking license?
Jack needs to take a class from some teacher during some timeslot. To begin with, he has a choice of which school he attends: "Three Storms" or "Buckaroo". Thus we can count how many ways he can take a class at each school, then add the two together to get the total number of ways:
Let's figure out how many ways he can take a class at "Three Storms" first. At that school, there are three teachers he can choose from, and each has four timeslots. Since the choice of teacher does not affect how many timeslots he has access to, we multiply them together to find the total number of ways:
#waysat "Storms" = 3 ·4 = 12
We do the same thing for the other school. At "Buckaroo" there are six teachers he can choose from, and each has three timeslots. Since the choice of teacher does not affect the number of timeslots, we multiply:
#waysat "Buckaroo" = 6 ·3 = 18
Now that we know how many choices he has at each school, we can add them together to find the total number of choices.
Total#ofways = 12 + 18 = 30
How many ways can you answer a true/false test with ten questions? (Assume that you respond to every question.)
Since you respond to every question and it is a true/false test, there are precisely two possible choices for each question on the test.
The choice of answer on each question has no effect on the other questions. For example, if you answer `true' on one question, you can still choose to answer either `true' or `false' on all the other questions. Therefore, since you will answer each question on the test and each of the questions has no effect on the others, we can calculate the total number of ways with the multiplication principle.
For each question, take the number of ways it can be answered, then multiply that by all the others. Since each question can be answered in two ways, we have
2 ·2 ·2 ·2 ·2 ·2 ·2 ·2 ·2 ·2 = 210 = 1024
A safe has a combination lock which has the numbers from 1 to 60 (inclusive) on the dial. The safe will open when the correct choice of four numbers (in order) are selected on the dial. How many different possible combinations can the safe have? What if it was five numbers instead of four-how many combinations would then be possible?
Each number choice in the combination has no effect on the other number choices. For example, if the first number is `47', the next number can be anything at all, including `47' again. Thus there are 60 possible choices for each of the four numbers in the combination.
Since the choice of each number has no effect on the others and all four choices must occur, we can calculate the total number of ways with the multiplication principle. For each choice, take the number of ways it can be picked, then multiply it by all the others. Since each choice can be picked in one of 60 ways, we have
60 ·60 ·60 ·60 = 604 = 12 960 000
We follow the exact same logic for figuring out the total possible ways when the combination is five numbers long:
60 ·60 ·60 ·60 ·60 = 605 = 777 600 000
Four number combination: 12 960 000, Five number combination: 777 600 000
In California, automobile license plates (excluding trucks) are issued in the format 1ABC234, where each of the numbers can be any number from 0-9 and each of the letters can be any letter from A-Z, with the exception of I, O, and Q (which are excluded to avoid confusion with 1 and 0).
With these rules in mind, how many distinct license plates can be made in this format?
Begin by noticing that the choice for each character has no effect on the choice of any of the others. For example, if a `7' is chosen for the first number slot, we can still choose any letter (other than the excluded ones) for the subsequent letters and any number for the subsequent numbers. Since every choice must be made and none of them affect the other choices, we use the multiplication principle.
For each number in the license, there are 10 possible choices (since it comes from the numbers 0-9). For each letter in the license, there are 23 possible choices (since the alphabet has 26 letters, but we were told I, O, and Q are excluded).
Since the choice of each character has no effect on the others, take the number of ways each can be picked, then multiply it by all the others:
Eight people are running a race together. How many different ways can first, second, and third place be won?
Unlike the previous problems we've worked on, the choice for who wins each place in the race does affect the other choices. Winning first place means that person cannot also win second or third. We can not just say there are eight possibilities for each of three choices and get 8·8 ·8: each choice affects the others, so we can't naively apply the multiplication prinicple without taking that into account.
However, if we think about it carefully, we can still use the multiplication principle. Start off by thinking about the different places in order. Think about first, then second, then third.
If we look at first place before the others, it's easy to see how many options there are: there are eight competitors, so eight people could potentially take first place. Thus we have 8 options for the first choice.
With that in mind, let's now consider second place. Since we already assigned a winner to first place, notice that there are only seven competitors remaining. This will be true no matter who won first place, because winning will take that person out of the running. Thus we don't have to care about the specific winner of first, we just need to acknowledge that there are now only seven possibilities for second. Thus we have 7 options for the second choice.
Following the same logic, we will only have six competitors remaining for third place. Thus we have 6 options for the third choice.
To find the total number of possibilities, we multiply the number of options for each choice with the others:
8 ·7 ·6 = 336
Sally has a variety of socks in a drawer. They come in the following colors: black, white, tan, red, orange, and blue. How many socks must she pull out from the drawer to guarantee that she has a pair of socks with matching colors?
Notice that if Sally pulls two socks from the drawer, she won't necessarily have a pair of socks that match in color. For example, she could pull out one orange and one blue. Similarly, if she pulls out three socks, they still won't necessarily match: orange, blue, and tan. We are looking for how many socks she must pull out to be absolutely sure she will have a matching pair in what she has pulled out.
If you think it's simple to find the answer to this, you're right! We know that the socks can come in a total of six different colors (black, white, tan, red, orange, and blue): therefore the most socks she can have without pulling a matching pair is six-one of each color. As soon as she pulls the seventh sock, it absolutely must match with one of the previous socks.
Thus Sally must pull out 7 socks to guarantee a match. [Notice that she might achieve a match before pulling out seven socks, it's just that she can only guarantee a match by pulling out seven.]
[If you're curious to see a slightly more formal explanation/proof, check out the next step. The above does a great job of relying on intuition, but sometimes you need to prove it more carefully.]
To formally prove this, we can use the pigeonhole principle. Consider each of the colors as a category "box". We have a total of 6 boxes, one for each color. Each sock that is pulled is put into the matching color box. As soon as we pull 6+1 = 7 socks, we know there must be at least one box with (at least) two objects in it: our matching pair. This fact comes from the pigeonhole principle, which guarantees if something can occur in n ways and the event happens n+1 times, it must repeat at least one of the ways.
*These practice questions are only helpful when you work on them offline on a piece of paper and then use the solution steps function to check your answer.
Lecture Slides are screen-captured images of important points in the lecture. Students can download and print out these lecture slide images to do practice problems as well as take notes while watching the lecture.