[MUSIC] The following formula, known as the principle of inclusion and exclusion, generalizes the previous example. Theorem, Let A1....An be finite subsets, Over a certain set X. And suppose we know the number of elements in each of them and in each of their intersections. Then the inclusion-exclusion principle allows us to find the number of elements in their union. Then the number of elements in the union of these sets, Is equal to the number of, The sum of numbers of elements in each of these sets. Minus, The sum of the number of n's in each double intersection. So I need to take all pairs of i and j where i < j. And take the number of elements in each Ai cap Aj. And then I need to sum it up with the total number of elements in all triple intersections. I'll take all triples i < j < k. Ai cap Aj, Ak. Minus all intersections of four, etc etc, until we get the intersection of all of them. And this intersection is taken with the sign -1 to the power n- 1. So the sign in front of each intersection depends on the parity of, Of the number of sets. A1 intersected with, An. So for n equal to 2 or 3, we get the formulas from our two previous examples. This formula has several proofs and as an exercise, I propose you to prove by induction. This is not very hard. By induction on the number of sets, of course. And I'm going to show you another proof which is more combinatorial, which is more in the spirit of our course. And, It is as follows. Let us take an element from this set. Let, from the union of Ai's. And let's see how many ways, well, how many times do we count it in the right hand side? How many times, How many times does it, Appear, In the right hand side? Well, to also their generality, we can suppose that X belongs to the first p sets and does not belong to the sets A p + 1 etc An. Suppose that X belongs to A1 etc Ap, so it belongs to their intersection as well. And X does not belong to Ap+1, Ap+2...An. Okay, then this means that, this element contributes into the right hand side of the sum, the following number of times. X contributes, To the right hand side, With multiplicity. Well, let's find this multiplicity. So, X is counted among the first p summands here. So it is counted p times in the first group of summands with multiplicity p. Then it also occurs in the double intersections and it occurs in p, choose two of them. And for each intersection, it just counter with a negative sign. So, if X belongs to p sets, it is counted p choose two times in the double intersections. p- p choose 2. Then if p is greater than or equal to 3, it appears in the triple intersections. And in the triple intersections, it is counted p choose 3 times. Then, In the intersections of 4, it is counted p choose 4 times, etc. Until we get -1 to the power of p-1, p choose p. And what is this sum? Well, this is very similar to the sum of binomial coefficients taken with alternating signs. And this is in fact, 1 +, we add and subtract 1 from the sum,- 1 + p- p choose 2. + p choose 3- etc + -1 to the power of p-1 p choose p. And we know that the sum being the alternating sum of my normal coefficients in one row over the Pascal triangle, counted with a negative sign is equal to 0. So, this is equal to 1, so that means that each element of the union A1....An is counted in the right hand side of this formula with multiplicity equal exactly to 1. So, the principle of inclusion and exclusion holds. So we have tend the principle of inclusion and exclusion. And now we will apply it to a combinatorial problem of counting the arrangements. [MUSIC]
