Welcome back to Discrete Math. We’re going to look at the inclusion-exclusion principle. Some of you may have this in your first course, other people they’ll wait till the second course, but this is probably more generalized than something you would have dealt with in your introductory Discrete Math course.

So where is the motivation? Well, if you recall, the cardinality of A or B is equal to the cardinality of A plus the cardinality of B minus the cardinality of A intersection B. And if we take the union of three objects, we can extend this a little bit further, and we get a law that looks like the following.

So we want a system that generalizes even further, and doesn’t necessarily deal explicitly with sets. So what we have is the principle of inclusion-exclusion more general.

So I need to define some stuff because we’re not dealing with sets anymore. Instead, we’re dealing with conditions. So C1, C2, all the way up to Cn will be conditions, and we have this n here. n basically means the number of elements.

So if we have n of C1, we have the number of elements that satisfy C1. If we have two conditions, n of C1, C2, then these are the number of elements that satisfy both C1 and C2. We can also have complement laws, which are very important for inclusion-exclusion, and that is if you have n of C1 bar, that is the number of elements that don’t satisfy C1.

Now what’s more interesting is when we have n, C1, C2, and a bar over each of these. What’s important to know here, this is the number of elements that are not C1 and not C2. This is different from the following. If we have n of C1, C2 bar, where it’s over both of them, this is the same thing as the number that are not C1 or C2. So this is a little bit different. So we’re not going to deal with that. Instead, we’re going to be dealing with this situation here.

So what is this similar to? Well when we take a look at n of not C1, it’s the same thing as the total number of elements. Sometimes we say s for our universe here, or u, and then we subtract all the conditions that fulfill C1. So this is very similar to set theory, where we have C1 as the first set, and not C1 as the outer set. I know this might not seem necessary to explain, but it’s good to get an idea of what exactly is going on here. So if you have a bar, this is equal to the universe, this is equal to the universe minus A. This is just an exact analog to what we’re doing. All right, so when we have a situation where we want the number of elements that are C1 bar, C2 bar, well it’s going to be the universe minus C1, C2 plus C1, C2. So this might be a little bit confusing at first, but what we’re looking at, we want to find all the elements that do not satisfy C1, and they don’t satisfy C2. So we want to find this area right here on the outside. So what do we have to do to do this? Well if we have n, we want to count everything once. So this whole thing is counted. Now because the whole thing is counted, let’s say we have this element here, so this element in the middle is counted. Well we have to subtract C1, so now it’s counted zero times, and then we have to subtract it from C2 because we don’t want