## Fundamental Counting Principle

### Transcript

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. Fundamental counting principle, Is a general way to approach tasks that can be broken into stages.

Suppose we can divide a given task in two stages. Suppose the first stage can be done in n sub 1 ways, the second way and then sub 2 ways and so forth. The total number of ways to do the task was simply be the product of all these numbers. So the number of ways we could 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 formal dinner, guests have the choice of 1 of 4 salad, so, choice of 1 of 4, 1 of 5 appetizers, 1 of 12 entrees, and 1 of 4 desserts.

And so the whole idea is that at any particular dinner chosen, you'll get a salad and appetizer and entree and dessert. So of the meals like that, how many different possible meals are there? Well, the fundamental counting principles 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 times 5 times 12 times 4. Or 4 times 5, of course, is 20, then multiply by that other 4 that's 80. Well, 8 times 12 is 96, so 80 times 12 would have to be 960, that's the answer.

Suppose we have six different books that 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 going to put in the first slot? Stage number two would be what are we going to 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 that choice of the second slot, I have 5 choices left, there still 5 books available that I could put in that second slot.

And so forth 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 going to be in place, and I'm just gonna have that one last book.

So I really want no choice at that point. And so N will be 5 times 4 times 3 times 2 times 1. Now we can simplify this a little bit, the 3 times 2 is 6, the 5 times 4 is 20. 20 times 6 is 120, 6 times 12 is 72, so 6 times 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, the total number of orders 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 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 it sounds like three different jobs for three different people. How many different possible steering committee could be chosen? So it sound like if Harry is chosen for the facilitator and Sally is chosen for the union rep, that would be different is 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've picked that person there are 24 people left I could pick to be the union rep.

Once I've picked that person also, there are 23 people left for secretary. So now we have to figure out 25 times 24 times 23. But that's not too hard, 25 times 24, for this we use doubling and halving principle. Half of 24 is 12, double of 25 is 50, use the half and doubling principle again, half of 12 is 6, so we get 6 times 100, that's 600.

So now, we just have to do 600 times 23. Well, let's think about 6 times 23. 6 times 23, that's not too bad, because I know 6 times 120 is 120, and 6 times 3 is 18. Well, 120 + 18, that's 138. Now just tack on the last two zeros, 13800.

So there are 13800 different possible steering committees that could 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 at the first stage can be done in one ways a second we've done in two ways, then the complete tasks can be done it 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 formalise that with a special notation in a couple lessons.

Read full transcriptSuppose we can divide a given task in two stages. Suppose the first stage can be done in n sub 1 ways, the second way and then sub 2 ways and so forth. The total number of ways to do the task was simply be the product of all these numbers. So the number of ways we could 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 formal dinner, guests have the choice of 1 of 4 salad, so, choice of 1 of 4, 1 of 5 appetizers, 1 of 12 entrees, and 1 of 4 desserts.

And so the whole idea is that at any particular dinner chosen, you'll get a salad and appetizer and entree and dessert. So of the meals like that, how many different possible meals are there? Well, the fundamental counting principles 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 times 5 times 12 times 4. Or 4 times 5, of course, is 20, then multiply by that other 4 that's 80. Well, 8 times 12 is 96, so 80 times 12 would have to be 960, that's the answer.

Suppose we have six different books that 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 going to put in the first slot? Stage number two would be what are we going to 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 that choice of the second slot, I have 5 choices left, there still 5 books available that I could put in that second slot.

And so forth 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 going to be in place, and I'm just gonna have that one last book.

So I really want no choice at that point. And so N will be 5 times 4 times 3 times 2 times 1. Now we can simplify this a little bit, the 3 times 2 is 6, the 5 times 4 is 20. 20 times 6 is 120, 6 times 12 is 72, so 6 times 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, the total number of orders 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 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 it sounds like three different jobs for three different people. How many different possible steering committee could be chosen? So it sound like if Harry is chosen for the facilitator and Sally is chosen for the union rep, that would be different is 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've picked that person there are 24 people left I could pick to be the union rep.

Once I've picked that person also, there are 23 people left for secretary. So now we have to figure out 25 times 24 times 23. But that's not too hard, 25 times 24, for this we use doubling and halving principle. Half of 24 is 12, double of 25 is 50, use the half and doubling principle again, half of 12 is 6, so we get 6 times 100, that's 600.

So now, we just have to do 600 times 23. Well, let's think about 6 times 23. 6 times 23, that's not too bad, because I know 6 times 120 is 120, and 6 times 3 is 18. Well, 120 + 18, that's 138. Now just tack on the last two zeros, 13800.

So there are 13800 different possible steering committees that could 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 at the first stage can be done in one ways a second we've done in two ways, then the complete tasks can be done it 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 formalise that with a special notation in a couple lessons.