## 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 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 into stages. Suppose the first stage can be done in n sub 1 one 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 could do it in the first stage, times the number of choices we can make in the second stage, times the number of choice we make in the third stage, etc.

We just find the product, very simple. This is the fundamental counting principle. So I realize 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, 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*5*12*4. Well, 4*5 of course is 20. Then multiply by that other 4, that's 80. Well, 8 times 12 is 96.

So 80*12 would have to be 960. That's the answer. Suppose we have six different books that we'll 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 could pick up any one and put it in that first slot.

Now here's the tricky part. For this 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 for the second slot, I have five choices left. There's still five books available that I can put in that second slot, and so forth. On each choice there are, in each state 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*4*3*2*1. Now we can simplify this a little bit. The 3*2 is 6. The 5*4 is 20. 20*6 is 120.

6*12 is 72. So 6*20 is 720. And that's now many different orders, that's the number of different orders in which we can put these books. Notice that in arranging any 6 different items in order, the total number of order's the product of 6 and every positive integer less than it.

So that would be 720 orders for any 6 distinct different items with 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 will talk about this more formally, and we will 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. 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 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've picked 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*24*23. Well that's not too hard. 25*24, for this we use the doubling and halving principle. Half of 24 is 12. Double of 25 is 50.

Use the halving and doubling principle again. Half of 12 is 6, so we get 6*100. That's 600. So now we just have to do 600*23. Well, let's think about 6 times 23. 6*23, that's not too bad because I know 6*20 is 120.

And 6*3 is 18. 120 + 18, that's 138. Now just tack on the last two zeros, 13,800. So there are 13,800 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 if the first stage can be done in n1 ways, the second can be done in n2 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, the number of possible orders is the product of n times all the positive integers less than n. And again, we'll formalize that with a special notation in a couple lessons.