The Unapologetic Mathematician

Mathematics for the interested outsider

Inclusion-Exclusion Again

Now that we know a little more about characteristic functions, let’s see how they can be used to understand the inclusion-exclusion principle. Our first pass was through a very categorified lens, which was a neat tie-in to Euler characteristics. But we want something a little more down-to-Earth.

So, let’s take a finite collection \left\{S_i\right\}_{i=1}^n of subsets of a set X. To each one we have a corresponding idempotent function \chi_{S_i}, which is {1} for points in S_i and {0} elsewhere. We can take the complement of a subset in the language of idempotents as usual: 1-\chi_{S_i}=\chi_{{S_i}^c}. This function is {1} for points not in S_i, and {0} in S_i.

Now let’s take and multiply all these complementary functions together to get

\displaystyle\prod\limits_{i=1}^n\left(1-\chi_{S_i}\right)=\prod\limits_{i=1}^n\chi_{{S_i}^c}=\chi_{{S_1}^c\cap\dots\cap{S_n}^c}

By DeMorgan’s Laws, the intersection of all these complements is the complement of the union of all the S_i. Thus

\displaystyle\prod\limits_{i=1}^n\left(1-\chi_{S_i}\right)=\chi_{(S_1\cup\dots\cup S_n)^c}=1-\chi_{S_1\cup\dots\cup S_n}

Now let’s expand out the product, just like we expand out the product of any sequence of binomials. In each factor, we choose which of the {1} or the \chi_{S_i} to contribute. First we get the term where we always choose {1}, then the terms where we choose exactly one of the \chi_{S_i}, then the terms where we choose exactly two of them, and so on until we choose all n of them. The sign of a term is negative when we choose an odd number of the \chi_{S_i}, and positive when we choose an even number. That is

\displaystyle\begin{aligned}\prod\limits_{i=1}^n\left(1-\chi_{S_i}\right)&=1-\sum\limits_{1\leq i\leq n}\chi_{S_i}+\sum\limits_{1\leq i<j\leq n}\chi_{S_i}\chi_{S_j}-\sum\limits_{1\leq i<j<k\leq n}\chi_{S_i}\chi_{S_j}\chi_{S_k}+\dots+(-1)^n\chi_{S_1}\dots\chi_{S_n}\\&=1-\sum\limits_{1\leq i\leq n}\chi_{S_i}+\sum\limits_{1\leq i<j\leq n}\chi_{S_i\cap S_j}-\sum\limits_{1\leq i<j<k\leq n}\chi_{S_i\cap S_j\cap S_k}+\dots+(-1)^n\chi_{S_1\cap\dots\cap S_n}\end{aligned}

Putting this together with the earlier expression, we find

\displaystyle\chi_{S_1\cup\dots\cup S_n}=\sum\limits_{1\leq i\leq n}\chi_{S_i}-\sum\limits_{1\leq i<j\leq n}\chi_{S_i\cap S_j}+\sum\limits_{1\leq i<j<k\leq n}\chi_{S_i\cap S_j\cap S_k}-\dots+(-1)^n\chi_{S_1\cap\dots\cap S_n}

For n=2 this gives us back our formula for the characteristic function of the intersection of two sets. For larger n it gives us the inclusion-exclusion principle in terms of characteristic functions.

December 28, 2009 Posted by | Fundamentals | 1 Comment

   

Follow

Get every new post delivered to your Inbox.

Join 389 other followers