22.1.5. Alternate Form of Inclusion-Exclusion

So, now what we will do is, we will look into an alternate form of inclusion-exclusion which is very powerful and it is this alternate form of inclusion-exclusion which we use in varieties of problems. So, what happens in this alternate form is that we will be facing scenarios where we want to count the number of elements from a set A which has n number of elements and we will be interested to count the number of elements in this set which has none of the properties say P1, P2, P3, ..., Pn.

The alternate form of inclusion-exclusion is useful for scenarios where we want to count elements that lack certain properties. Here, we start with a set, A, that contains 'n' elements. We identify certain properties (P1, P2, ... Pn) and focus on counting how many elements do not possess any of these properties. This is different from the standard inclusion-exclusion, which typically counts how many do have certain properties.

Imagine you have a basket of fruits and you want to know how many fruits are not apples, bananas, or oranges (the properties). In this case, you'd want to use the alternate form to first find all the fruits and then subtract the ones that are apples, bananas, or oranges.

P1, P2, P3 will be some abstract properties and we will be interested to find out the number of elements in the set A which neither have the property P1 nor the property P2, nor the property P3, and so on. So, for that what we will do is we will first identify the subset A_i consisting of elements which has property P_i.

To use the alternate form, we first define the subsets A_i, where each A_i consists of elements in set A that possess the property P_i. This means if you have properties such as being red or being round, A_1 could be all red fruits, A_2 could be all round fruits, etc. This allows us to focus our counting on those specific elements that we want to exclude.

Continuing with the fruit example, let’s say A_1 is the set of red fruits, A_2 is the set of round fruits, etc. By identifying these subsets, we can better understand which fruits to exclude when counting how many are neither red nor round.

And if I take the union of the subsets A1 to An, I get all the elements in the set A which has either the property P1 or the property P2 or the property P3 or so on. That means it will have at least one of the properties P1 to Pn; but that is not what we want.

The union of the subsets A1 to An represents all elements that have at least one of the specified properties (P1 to Pn). However, our goal is to count elements that do NOT have any of these properties. Thus, finding the union helps identify which elements to exclude from our total count.

If we think of it as a collection of fruits again, the union of A1 to An gives us all fruits that are red, round, etc. But what we want is to see all fruits that aren't any of those. It's like first gathering all the items we don't want and then figuring out how many are left in the original set.

Now the desired answer or the number of elements which do not have any of the properties P1 to Pn will be the difference of the cardinality of A which is n and the unique cardinality of the union of n sets.

To find how many elements do not have any of the properties, we take the total count of elements in set A (which is n) and subtract the count of elements that have at least one of the properties (the cardinality of the union of the A_i). This means performing the operation n - |A1 ∪ A2 ∪ ... ∪ An|, where |...| denotes the number of elements.

In our fruit example, if we start with 10 fruits in total and collect that there are 4 fruits that are either red, round, or any other property, we subtract: 10 - 4 = 6. This means there are 6 fruits that are neither red nor round.

Now we will apply the rule of inclusion-exclusion to find out the cardinality of the union of the n sets because we know how to find that.

The next step involves employing the inclusion-exclusion principle to compute |A1 ∪ A2 ∪ ... ∪ An|. This principle allows us to add and subtract the cardinalities of the various subsets to eliminate overlap accurately. The general idea is to start by adding the sizes of each individual subset, then deducting sizes of pairwise intersections, adding sizes of triple intersections, and so forth.

Imagine again with our fruit problem: if we counted the red fruits, round fruits, and then backtracked to exclude the overlaps, we could precisely calculate how many fruits fit at least one property without double counting any. It's like making a checklist for each color and shape while ensuring you don’t mark any fruit twice due to overlapping categories.

--