can inclusion/exclusion be done with set subtraction instead?

554 Views Asked by At

The inclusion/exclusion principle applied to the Venn diagram below (from Wikipedia) would give the value of $\left\lvert A\cup B \cup C\right\rvert$ as $\left\lvert A\right\rvert + \left\lvert B\right\rvert + \left\lvert C\right\rvert - \left\lvert A \cap B\right\rvert - \left\lvert A \cap C\right\rvert - \left\lvert B \cap C\right\rvert + \left\lvert A\cap B\cap C\right\rvert$. Venn diagram for inclusion/exclusion

When you add more sets, the number of calculations required goes up quickly, and in general the problem takes exponential time to solve. I see a much simpler formula by looking at the diagram: $\left\lvert A\right\rvert + \left\lvert B\setminus A\right\rvert + \left\lvert \left(C\setminus A\right)\setminus B\right\rvert$. Visually, instead of adding all of the circles together and then subtracting the sections that we added too many times, we just add the first circle, add the second circle with a bite out of it, and then add the third circle with two bites out of it, avoiding the double-adding of any sections.

Is this simpler formula correct? If so, why is the more complicated inclusion/exclusion principle used?

I happen to be working with cardinalities of powersets, and cardinalities of powerset differences seem simple enough to compute unless I am mistaken: $\left\lvert \wp \{a,b,c\}\setminus\wp \{a,c\}\right\rvert = \left\lvert \wp \{a,b,c\}\right\rvert - \left\lvert \wp\big(\{a,b,c\}\cap\{a,c\}\big)\right\rvert = 8 - 4 = 4$

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, your formula is also correct. I believe the reason the usual formula is preferred is because in combinatorics one is usually not so much concerned with the number of terms as with their complexity. In combinatorics, one typically doesn't have to consider an exponential number of such terms separately but can combine very many of them into one term, e.g. if the sets are given by conditions such as vertices of a graph having a certain colour, so that the intersections stand for two or more of these conditions being fulfilled simultaneously. In such cases, it's easier to work with all possible intersections (corresponding to all possible logical conjunctions of the conditions) than with counting the number of objects fulfilling more complicated conditions such as "vertex $C$ has the given colour but neither vertex $A$ nor vertex $B$ does".