اصل شمارش اساسی

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 into stages. Suppose the first stage can be done in, 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 choice we could make in the third stage, et cetera. 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 choices 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 will get a salad, an 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 are 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. Well 4 times 5 of course is 20. Then multiple 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 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 1 is what are we gonna put in the first slot. Stage number 2 would be what are we gonna put in the second slot. That sort of thing.

Well in the first slot. I have 6 choices. So when I start out, I have 6 books, I could pick up any one and put it in that first slot. Now here’s the tricky part. For the second slot, I’ve 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 5 choices left. There are still five books available that I could put in that second slot, and so forth on each choice there are, in each stage there are fewer choices that I’ll have because books have already been put in the slot. So, the third book 4 choices, the second book 3 choices, the fifth book I’ll have 2 choices,.

And by the time I get to the last book, I’m only gonna have 1 choice because 5 books are already gonna be in place and I’m just gonna have that 1 last book so I really will have 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 how 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 orders is 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’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 committees could be chosen?

So it sounds like if Harry is chosen for the facilitator, 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 times 24 times 23.

Well that’s not too hard. 25 times 24. For this we’ll use the doubling and halving principle. Half of 24 is 12, double of 25 is 50, use the, the halving and doubling principle again, half of 12 is 6. So we get 6 times a 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 20 is 120 and 6 times 3 is 18. Well 20 plus 18, that’s 138. Now just tack on the last 2 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 kind of 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 combinatorials.

In summary, the fundamental counting principle says that if the fist stage can be done in n1 ways than the second can 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 that 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 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 lessons