The Fundamental Principles of Counting

Transcript

0:00Introduction

Hello everyone! Okay, one small puzzle before we start. Suppose a student has three shirts, four pairs of trousers, and two pairs of shoes. In how many ways can she dress? Many students answer at once: three plus four plus two, nine ways. Hmm, nine? Is that really right? Hold on to your answer; we will settle it in a few minutes. Look, this is the very first idea of permutations and combinations. Almost every counting argument is built from just two rules, and in JEE, counting questions come up often. Today you learn both rules. So, let's begin.

0:39Multiplication principle: one step, then the next

So, rule number one: the multiplication principle. Suppose a task has two successive steps, one and then the other. Step one can be done in m ways, and then, for each of those m ways, step two can be done in n ways, okay? Remember those two words, for each. They matter. So how many ways for the whole task? Look at the left half of the figure. Three blue roads from A to B, numbered one, two and three, and then two orange roads from B to C, named a and b. The arrow in the figure means going from one town to the next, okay? Take road one: you still have both roads, a and b. Road two: again both. Road three: again both. So the routes are one a, one b, and so on up to three b: three times two, six routes. The cross sign on screen means times. So for two steps, the total is m times n ways. Clear? And it does not stop at two steps. Three steps, four steps, any number: just keep multiplying, m times n times p, and so on. The three dots mean the pattern continues, right? And the right half of the figure, four boxes multiplied together? That is this same rule with four steps. We will come back to it in a minute. Now, back to our puzzle. She picks a shirt, and then a pair of trousers, and then a pair of shoes. Three successive choices. So tell me: add or multiply? Multiply, yes, exactly! For each of the three shirts, she has four pairs of trousers, and for each of those, two pairs of shoes. Three times four times two: twenty four ways, not nine! That was our trap. She does not wear a shirt or trousers or shoes; she wears all three together. So adding was wrong. Got it?

2:23Addition principle: either this way or that way

Now, rule number two: the addition principle. This time, the task is done in either of two ways. Either the first way, in m ways, or the second way, in n ways, okay? Can we just add them? Let me ask you this: before we add, what must be true about the two ways? Very good! They cannot happen together. If one single way of doing the task belonged to both lists, adding would count it twice, right? So this condition is not decoration. Always check it. And when it holds, the task can be done in m plus n ways. That's it! And just like before, it extends to any number of cases: m plus n plus p, and so on, as long as no two cases can happen together. With me?

3:09Topper's trick: key words, then the tightest place

Alright, now a trick that toppers use. First, read the words of the question. When it says one thing, and then another, multiply. The double arrow on screen means: so you do this, okay? And when it says this or that, with cases that cannot occur together, add. So, and then means multiply; or means add. Simple, right? Second part of the trick. When you fill places, like the digits of a number, fill the most restricted place first, the one with a condition on it. Why? Because if you leave it till the end, its number of choices depends on what you picked before, and then a single product does not work. Clear? Look at the right half of the figure: four digit numbers with all digits different. The thousands place cannot be zero, so fill it first: nine choices, one to nine. Hundreds: any other digit, and now zero is allowed, so again nine. Then tens, eight, and units, seven. Nine times nine times eight times seven: four thousand five hundred and thirty six. Okay? Now think. If the number must be even, which place gets a condition? The units place, exactly! Even means the last digit is zero, two, four, six or eight, so fill the units place first. Keep this in mind; our second example needs it.

4:30Example 1: routes from A to C, via B or directly

Now, example one. There are three roads from A to B, two from B to C, and two roads going directly from A to C, okay? In how many ways can one travel from A to C? Pause the video, and try it first. Done? Okay, let's check. Case one: go via B, that is, pass through town B on the way. From A to B in three ways, and then from B to C in two ways. And then means multiply: three times two, six routes, the same six we counted earlier. Right? Case two: go directly from A to C, two roads. Now, six routes and two routes. Add or multiply? Add, correct! One trip goes through B, or goes directly, never both. The cases cannot happen together. So six plus two: eight ways. Anyone who multiplied and got twelve? Careful! That would mean one trip uses a road through B and also a direct road. That makes no sense. Got it?

5:31Example 2: 3-digit even numbers, all digits different

Now a harder one, JEE style. How many three digit even numbers have all digits different? Pause the video and try it. Hint: use today's trick. Which place is restricted? Done? Okay, let's check. Even number, so the units place has the condition. Fill it first. It can be zero, two, four, six or eight: five choices, okay? Next, the hundreds place: not zero, and not the units digit, so eight choices. Then the tens place: eight left. So five times eight times eight, three hundred and twenty, right? No, no, careful! This is the trap. When the units digit is zero, zero is already used, so the hundreds place has nine choices, not eight. The count depends on the units digit, so we split into cases. Case one: units digit zero. Hundreds: any digit from one to nine, nine choices. Tens: eight left. Nine times eight: seventy two. Case two: units digit two, four, six or eight, four choices. Hundreds: not zero and not the units digit, eight choices. Tens: ten digits minus the two already used, eight choices, and here zero is allowed. Four times eight times eight: two hundred and fifty six. The two cases cannot happen together, so add. Seventy two plus two hundred and fifty six: three hundred and twenty eight. See? Multiply inside each case, add across the cases. Both rules in one question! With me?

7:11Quick revision: multiply steps, add cases, restricted first

So, quick revision. And then: multiply the number of ways. Or, with cases that cannot occur together: add. And when you fill places, fill the most restricted place first, and split into cases if you need to. Now go and try the practice problems on this page. You will do them easily, I promise. All the best!