The Inclusion–Exclusion Principle

Transcript

0:00Introduction

Hello everyone! Okay, one small puzzle before we start. Take six letters: two A's, two B's and two C's, arranged in a row. They can be arranged in ninety different ways. Now, we want no two identical letters side by side. So Riya counts the bad arrangements: thirty with the two A's together, thirty with the two B's together, and thirty with the two C's together. Thirty plus thirty plus thirty is ninety. Ninety bad, out of ninety. So, zero good arrangements? But look at this one: ABCABC, okay? No two identical letters are side by side! Something is wrong here, right? Today we learn the principle that catches this mistake: inclusion and exclusion. In JEE, it comes up often in counting questions. So, let's begin.

0:54Two properties: add, then subtract the overlap

So, say we have some objects, and two properties. Set A holds the objects with the first property, and set B holds the objects with the second. We want to count the objects with at least one of the two properties. With me? The natural first move is to add. These two vertical bars around A mean the number of elements in set A, right? So, the first line simply adds the number in A and the number in B together. But now look at the middle region, where the two circles overlap. How many times did we count the objects sitting there? Twice, exactly! Once inside A, and once again inside B: double counting! This middle region is A intersection B, in the second line. The symbol shaped like an upside down cup means intersection: the objects in both sets. Okay? So, we subtract the overlap once. The cup shaped symbol means union: the objects in A, or in B, or in both. The number in A union B equals the number in A, plus the number in B, minus the number in A intersection B, the overlap. Now every object is counted exactly once. Clear?

2:06Three properties: add, subtract, add back

Now, three properties: A, B and C, the three circles you see. Same first move: add the numbers in A, in B and in C, all three. Now look at the dark centre of the figure, A intersection B intersection C: the objects with all three properties. How many times have we counted them? Three times, yes! Once in each circle. And every double overlap, the region inside exactly two circles, is counted twice. Right? So, we subtract the three pairwise intersections: A intersection B, B intersection C, and C intersection A, all three of them. Now each double overlap is counted once, fixed. But the centre sits inside all three of those pairs. So, how many times is the centre counted now? Zero times! Added three times, taken off three times. We lost it completely. So, add it back once: plus the number in A intersection B intersection C, the centre. Now every region is counted exactly once. And forgetting this last term is a very common mistake. Got it? For short, we use the Greek capital letter sigma, which means sum. The number in A union B union C equals the sum over the single sets, minus the sum over the pairwise intersections, plus the triple intersection. Add, subtract, add back.

3:32Many properties, and the count of none

Okay? Now, what if there are four properties, or more? Same rhythm. Add the single sets, subtract the pairwise intersections, add the triple intersections, and so on. The three dots mean and so on, and the signs keep alternating. With me? Here is a topper's trick for writing it. Give each sum a name. S one, that is a capital S with a small one at its bottom right, is the sum over single properties. S two is the sum over pairs, and S three is the sum over triples. Clear? Now, a question that comes up often: none of the properties. Say there are capital N objects in total. How many of them have none of the properties? The total, minus those with at least one. Exactly! So, N minus the number in the union of all the sets. Right? And that union is S one, minus S two, plus S three, and so on. Subtract all of it from N, and every sign flips. So, none equals N, minus S one, plus S two, minus S three, and so on. Okay? So, when do you use this? Look for these words: at least one, none of, no two alike adjacent, and onto, which comes later in this chapter. The moment you see them, think inclusion and exclusion. Got it?

4:53Example 1: integers 1 to 100 divisible by 2 or 3

Let's start with an easy one. How many of the integers one, two, and so on up to one hundred are divisible by two or three? Pause the video, and try it first. Done? Okay, let's check. Let A be the multiples of two. Every second number is even, so one hundred over two: fifty. Right? Let B be the multiples of three. One hundred over three is thirty three point three, so there are thirty three whole multiples. Okay? So, fifty plus thirty three: eighty three numbers, right? No, no, careful! Look at the middle region. Numbers divisible by both two and three are the multiples of six, and they were counted twice. One hundred over six is sixteen point six six, so there are sixteen of them. With me? So, fifty plus thirty three, minus sixteen: sixty seven. Sixty seven numbers from one to one hundred are divisible by two or three. That's it!

5:50Example 2: AABBCC with no two identical letters adjacent

Now, remember our puzzle from the start? Let's finish it. In how many arrangements of AABBCC are no two identical letters adjacent? Pause and try. Hint: the two A's standing together is one bad event. Done? Okay, let's check. First, the total. Six letters in a row, but the two A's are identical, and so are the two B's and the two C's. So, six factorial, over two factorial, two factorial, two factorial; the exclamation mark means factorial. Seven hundred and twenty over eight: ninety. Yes, the ninety from our puzzle. Okay? Now the bad events. Bad event one: the two A's stand together. How do we count those arrangements? Glue them, yes! Treat A A as one block. Now we arrange five things: the block, two B's and two C's. Five factorial over two factorial, two factorial: one hundred and twenty over four, thirty. The same holds for B B and for C C, thirty each. So, S one is three times thirty: ninety. Clear? So, ninety in total, and ninety bad. The answer is ninety minus ninety, zero arrangements, right? No, no, wait! That is exactly Riya's mistake. An arrangement with A A together and B B together was thrown out twice. So, we add back the pairs. Glue both: the A A block, the B B block, and two C's. Four factorial over two factorial: twelve. There are three such choices of two blocks, so S two is thirty six. Got it? And all three glued: three blocks, arranged in three factorial ways, that is six. That is S three. With me? So, none adjacent is N minus S one, plus S two, minus S three. Ninety minus ninety, plus thirty six, minus six: thirty! Thirty good arrangements, and ABCABC is one of them. Mystery solved. Very good!

7:47Quick revision: two sets, more sets, none of the properties

So, quick revision. Two sets: add both, subtract the overlap once. More sets: add the singles, subtract the pairs, add the triples, and so on. And for none of the properties: N minus S one, plus S two, minus S three, and so on. Now go and try the practice problems on this page. You will find them easy, I promise. All the best!