Fundamental Counting Principle
The fundamental counting principle. This is, as the name suggests, the single most important principle in this entire module, and it really is based on the very simple idea that the word and means multiply. The fundamental counter principle is a general way to approach tasks that can be broken into stages.
Suppose we can divide a given task into stages. Suppose the first stage can be done in n sub 1 ways, the second way in n sub 2 ways and so forth. The total number of ways to do the task will simply be the product of all these numbers. So the number of ways we can do it in the first stage times the number of choices we can make in the second stage times the number of choices we make in the third stage etc.
We just find the product, very simple. This is the fundamental counting principle. So I realized this is very abstract, now I'm gonna show a few examples. So, for a formal dinner, guests have the choice of one of 4 salads, so a choice of one of 4, one of 5 appetizers, one of 12 entrees, and one of 4 desserts.
And so the whole idea is that at any particular dinner chosen you'll get a salad, an appetizer, an entree, and dessert. So, all of the meals like that, how many different possible meals are there? Well, the fundamental counting principle is perfect here because we're in stages, we can treat each course separately and there's no restrictions here. In other words, any salad can go with any appetizer, they can go with any entree.
So there's no restriction at all. So we can just simply multiply the numbers. That's what the fundamental counting principle tells us. So the number of ways to do this would be 4 x 5 x 12 x 4. Well, 4 x 5 of course is 20. Then multiply by that other 4, that's 80.
Well, 8 x 12 is 96, so 80 x 12 would have to be 960, that's the answer. Suppose we have, six different books that we will place on a shelf. In how many different orders can we place these books? Well, think about it this way. The various places are stages.
Stage number one is, what are we gonna put in the first slot? Stage number two would be, what are we gonna put in the second slot, that sort of thing. Well in the first slot, I have six choices. So when I start out, I have six books. I can pick up any one and put it in that first slot.
Now here's the tricky part, for the second slot I already picked a book. And so that first book is already sitting in the first slot. So when I go to make the choice of the second slot, I have five choices left. There's still five books available that I could put in that second slot, and so forth on each choice. On each stage, there are fewer choices that I'll have because books have already been put in the slot.
So the third book, I'll have four choices. The second book, I'll have three choices. The fifth book, I'll have two choices. And by the time I get to the last book, I'm only gonna have one choice because five books are already gonna be in place and I'm just gonna have that one last book.
So I really will have no choice at that point. And so N will be 5 x 4 x 3 x 2 x 1. Now, we can simplify this a little bit, the 3 x 2 is 6, the 5 x 4 is 20. 20 x 6 is 120, 6 x 12 is 72, so 6 x 120 is 720. And that's the number of different orders in which we can put these books.
Notice that in arranging any six different items in order or the total number of orders is the product of six and every positive integer less than it. So that would be 720 orders for any 6 distinct different items and no restrictions. And in general, if we have to arrange n different items in order, the total number of orders is the product of n times every positive integer less than n.
We will formalize this in a couple lessons when we discuss factorials, so just keep this in the back of your mind right now. We'll talk about this more formally, and we'll have a special notation for it in a couple lessons. Here's a practice problem, pause the video and then we'll talk about this. Okay, a small division of a company with 25 employees will choose a three-person steering committee consisting of a facilitator, a union rep, and a secretary.
So sounds like three different jobs for three different people, how many different possible steering committees could be chosen? So it sounds like if Harry is chosen for the facilitator and Sally is chosen for the union rep, that would be different than if Sally is chosen as the facilitator and Harry is chosen as the union rep. So I'll just point out here that the order does matter, if we swap around the people into the different roles then we have a different steering committee.
Well, clearly, if we're picking them at random, for the first choice for the facilitator, I have 25 choices. Once I pick that person, there are 24 people left I could pick to be the union rep, once I pick that person also, there are 23 people left for secretary. So now we have to figure out 25 x 24 x 23. Well, that's not too hard, 25 x 24, for this we'll use the doubling and halving principle.
Half of 24 is 12, double of 25 is 50. Use the having and doubling principle again. Half of 12 is 6, so we get 6 x 100, that's 600. So now we just have to do 600 x 23. Well, let's think about 6 x 23, 6 x 23, that's not too bad because I know 6 x 20 is 120, and 6 x 3 is 18, 120 + 18, that's 138.
Now just tacked on the last two zeros 13,800. So there are 13,800 different possible steering committees that can be chosen. So notice that as we're seeing, we're kinda seeing a pattern here with counting problems. We only have a company with 25 employees, but as soon as we start looking at different orders of doing things, we get very, very large numbers.
Some of the largest numbers in mathematics come from combinatorics. In summary, the fundamental counting principle says that if the first stage can be done in one ways, the second be done in two ways then the complete task can be done. It's just the product of the number of ways, the number of choices we have in each stage.
That's the fundamental counting principle. If we have to arrange a set of n different items in order than number of possible orders, it's a product of n times all the positive integers less than n. And again, we'll formalize that with a special notation in a couple of lessons.
Read full transcriptSuppose we can divide a given task into stages. Suppose the first stage can be done in n sub 1 ways, the second way in n sub 2 ways and so forth. The total number of ways to do the task will simply be the product of all these numbers. So the number of ways we can do it in the first stage times the number of choices we can make in the second stage times the number of choices we make in the third stage etc.
We just find the product, very simple. This is the fundamental counting principle. So I realized this is very abstract, now I'm gonna show a few examples. So, for a formal dinner, guests have the choice of one of 4 salads, so a choice of one of 4, one of 5 appetizers, one of 12 entrees, and one of 4 desserts.
And so the whole idea is that at any particular dinner chosen you'll get a salad, an appetizer, an entree, and dessert. So, all of the meals like that, how many different possible meals are there? Well, the fundamental counting principle is perfect here because we're in stages, we can treat each course separately and there's no restrictions here. In other words, any salad can go with any appetizer, they can go with any entree.
So there's no restriction at all. So we can just simply multiply the numbers. That's what the fundamental counting principle tells us. So the number of ways to do this would be 4 x 5 x 12 x 4. Well, 4 x 5 of course is 20. Then multiply by that other 4, that's 80.
Well, 8 x 12 is 96, so 80 x 12 would have to be 960, that's the answer. Suppose we have, six different books that we will place on a shelf. In how many different orders can we place these books? Well, think about it this way. The various places are stages.
Stage number one is, what are we gonna put in the first slot? Stage number two would be, what are we gonna put in the second slot, that sort of thing. Well in the first slot, I have six choices. So when I start out, I have six books. I can pick up any one and put it in that first slot.
Now here's the tricky part, for the second slot I already picked a book. And so that first book is already sitting in the first slot. So when I go to make the choice of the second slot, I have five choices left. There's still five books available that I could put in that second slot, and so forth on each choice. On each stage, there are fewer choices that I'll have because books have already been put in the slot.
So the third book, I'll have four choices. The second book, I'll have three choices. The fifth book, I'll have two choices. And by the time I get to the last book, I'm only gonna have one choice because five books are already gonna be in place and I'm just gonna have that one last book.
So I really will have no choice at that point. And so N will be 5 x 4 x 3 x 2 x 1. Now, we can simplify this a little bit, the 3 x 2 is 6, the 5 x 4 is 20. 20 x 6 is 120, 6 x 12 is 72, so 6 x 120 is 720. And that's the number of different orders in which we can put these books.
Notice that in arranging any six different items in order or the total number of orders is the product of six and every positive integer less than it. So that would be 720 orders for any 6 distinct different items and no restrictions. And in general, if we have to arrange n different items in order, the total number of orders is the product of n times every positive integer less than n.
We will formalize this in a couple lessons when we discuss factorials, so just keep this in the back of your mind right now. We'll talk about this more formally, and we'll have a special notation for it in a couple lessons. Here's a practice problem, pause the video and then we'll talk about this. Okay, a small division of a company with 25 employees will choose a three-person steering committee consisting of a facilitator, a union rep, and a secretary.
So sounds like three different jobs for three different people, how many different possible steering committees could be chosen? So it sounds like if Harry is chosen for the facilitator and Sally is chosen for the union rep, that would be different than if Sally is chosen as the facilitator and Harry is chosen as the union rep. So I'll just point out here that the order does matter, if we swap around the people into the different roles then we have a different steering committee.
Well, clearly, if we're picking them at random, for the first choice for the facilitator, I have 25 choices. Once I pick that person, there are 24 people left I could pick to be the union rep, once I pick that person also, there are 23 people left for secretary. So now we have to figure out 25 x 24 x 23. Well, that's not too hard, 25 x 24, for this we'll use the doubling and halving principle.
Half of 24 is 12, double of 25 is 50. Use the having and doubling principle again. Half of 12 is 6, so we get 6 x 100, that's 600. So now we just have to do 600 x 23. Well, let's think about 6 x 23, 6 x 23, that's not too bad because I know 6 x 20 is 120, and 6 x 3 is 18, 120 + 18, that's 138.
Now just tacked on the last two zeros 13,800. So there are 13,800 different possible steering committees that can be chosen. So notice that as we're seeing, we're kinda seeing a pattern here with counting problems. We only have a company with 25 employees, but as soon as we start looking at different orders of doing things, we get very, very large numbers.
Some of the largest numbers in mathematics come from combinatorics. In summary, the fundamental counting principle says that if the first stage can be done in one ways, the second be done in two ways then the complete task can be done. It's just the product of the number of ways, the number of choices we have in each stage.
That's the fundamental counting principle. If we have to arrange a set of n different items in order than number of possible orders, it's a product of n times all the positive integers less than n. And again, we'll formalize that with a special notation in a couple of lessons.
Related Blog Posts
