[MUSIC] Now the topic that we're going to discuss today is the principle of inclusion and exclusion. Sometimes common elaborated as (PIE) We start with the following baby problem. Example. Suppose that in a class group, there are 24 students who are able to speak Spanish, and 25 who speak French. In a class group. 25 people speak Spanish. And 24 speak French. Suppose that there are eight people among them who are able to speak both languages. My question is how many people can speak at least one foreign language? How many students. Speak at least. One foreign language? Well probably you have seen pictures usually used for solving this problem. These are called Euler Venn diagrams. So you can draw the sets of people speaking Spanish and French as two circles overlapping, and the intersection corresponds to, to those who speak both languages. So there are 25 people here and 24 here in this circle. An the intersection consists of eight people. So you want to find the total number of people in the union of these two sets. And for this well of course you know how to do this, so if you want to find the union of these two sets if you want to count the elements in the union. You need to add the number of elements in S and F. And if you do that, you count every one but you count the intersection twice. Those who speak both Spanish and French are counted first among the Spanish speakers, and then among the French speakers, so if you want to find the total number of students in this unit you need to subtract the intersection, S intersected with F. So as you plug in the values here you get 25 + 24- 8. And this gives you 49- 8 that is 41. So this was very easy. Okay, let's consider another example with three foreign languages. So suppose this is example two. Suppose that in this class group there are people studying German. And the number of Spanish and French speakers is the same. And in addition, there are 15 people speaking German. And among these, there are people who speak both German and Spanish. And suppose that the number of such people is six. Six speak German and Spanish. And seven speak both German and French. And on these there are people speaking all three foreign languages, and suppose that the number of such people is equal to four. Speak all three languages. How to compute the number of people who speak at least one foreign language. The question is again the same. Okay, to do this we draw again, the diagram with circles. These are the Spanish speakers. These are French speakers, and these are students speaking German, and we'll put numbers 25, 24, and 15. And what about the intersections? So we have this set of students speaking both Spanish and French, and there are eight people. And in this intersection, Spanish and German there are six people, and here the row seven. And also there is the triple intersection. Which consists of four people knowing all three languages. Okay, so we'll want to compute the number of people speaking at least one foreign language. How we do that, so we compute the number of students in the union G ,union with S and union with F. Is again the sum of all three groups of people, speaking German, French, and Spanish. And then we need to subtract the intersections because we count those who speak two languages, we count them twice as in the previous example. So we get, we need to subtract those who speak both Spanish and French, The intersection we subtract those speaking Spanish and German. And we subtract those speaking German and French. Okay, and now we are left with the triple intersection. So the question is, how we counted these students who speak all the three languages or not. And if we did, how many times did we count that. So let's see. First, we counted the intersection three times when we were adding G, F and S. So these four people were counted three times. And then we have subtracted each of them also three times because they were counted among these who spoke Spanish and French, Spanish and German, and German, and French. So this means that we haven't counted them in the sum yet. But we want to count them once. So we need to add the intersection. S intersected with F, intersected with G. And again, as we take the numerical values we get that this is equal to 25 + 24 + 15- 8- 7- 6 + the triple intersection which is four and if I am not mistaken, I hope i am not. We'll get. 47 as the total number of students who are able to speak, at least one final language. But okay, this numbers are not that important as this formula. From this you can see it's structure, as you compare this formula with this one. To count the union of three sets you need to add up their cardinalities, and then subtract the double intersections, and then add the triple intersection. So the same thing holds here. First you add the two sets and then the cardinalities of these two sets, and then you subtract the intersection. So here you take these intersections interchangeably with plus and minus signs. So if the intersection has, as here. Two components, then you take it with a negative sign. And if It has one of three components you take it with a plus sign. And the generalization of this formula is called the inclusion exclusion formula. And we're going to write it in the general form right now. [MUSIC]
