Combinatorics – How to Implement the Inclusion-Exclusion Principle

combinatoricsinclusion-exclusion

I'm attempting to implement the Inclusion–exclusion principle, which is generally described as follows…

$$\begin{align}
\left| \bigcup\limits_{i=1}^n A_i \right| =
+ \left( \sum\limits_{i=1}^n | A_i | \right)
– \left( \sum\limits_{i,j:1 \le i<j \le n} \right. &| A_i \cap A_j |
+\cdots \\
& \cdots + (-1)^{n-1} | A_1 \cap A_2 \cap \ldots \cap A_{n-1} \cap A_n |\huge)
\end{align}$$

However, I wish to demonstrate that by "mapping" values to a binary representation (forgive/correct my language, math is not my core competency) we can find the same thing by keeping the sign as the same cardinality of the sets.

Lets assume we're working with three sets, A, B and C.

I could quickly generate a table based on a binary representation that shows each place value to be a set, and thus generate all my combinations:

 A | B | C  | Represents
-----------
 0 | 0 | 1  | C
 0 | 1 | 0  | B
 0 | 1 | 1  | C intersection B
 1 | 0 | 0  | A
 1 | 0 | 1  | A intersection C
 1 | 1 | 0  | A intersection B
 1 | 1 | 1  | A intersection B intersection C

Thus I now have my sets:

$$ \{ | C_i |, | B_i |, | C_i \cap B_i |, | A_i |, | A_i \cap C_i |, | A_i \cap B_i |, | A_i \cap B_i \cap C_i | \}$$

I wish to describe that the cardinality of the sets determines addition or subtraction. This is obvious with the general equation from above (negative multiplier in front of each term after the sums are calculated).

Thus, from the above set we know we can simply express this equation with addition/subtraction dependent on cardinality:

$$ \left|\bigcup\limits_{i=1}^3 A_i\right| = + | C_i | + | B_i | – | C_i \cap B_i | + | A_i | – | A_i \cap C_i | – | A_i \cap B_i | + | A_i \cap B_i \cap C_i | $$

I wish to express this as a general an equation, but am unsure of which concepts to use or how to implement them.

Best Answer

Let's derive a generalization of the Inclusion-Exclusion Principle based on some combinatoric identities.

Cancellation Lemma

Suppose $n$ and $k$ are non-negative integers. Then $$ \sum_{j=k}^n(-1)^{j-k}\binom{n}{j}\binom{j}{k} =\left\{\begin{array}{} 1&\text{if }n=k\\ 0&\text{otherwise} \end{array}\right.\tag{1} $$

Note that if $n\lt k$, then $\binom{n}{j}\binom{j}{k}=0$ for all $j$, so we can assume that $n\ge k$.

Proof 1: Using $\displaystyle\binom{n}{k}=\frac{n!}{k!\,(n-k)!}$, we get $$ \begin{align} \sum_{j=k}^n(-1)^{j-k}\binom{n}{j}\binom{j}{k} &=\sum_{j=k}^n(-1)^{j-k}\binom{n}{k}\binom{n-k}{j-k}\\ &=\binom{n}{k}(1-1)^{n-k}\tag{2} \end{align} $$ which is $1$ if $n=k$ and $0$ otherwise. $\quad\square$

Proof 2: Using Vandermonde's Identity, we get $$ \begin{align} \sum_{j=k}^n(-1)^{j-k}\binom{n}{j}\binom{j}{k} &=\sum_{j=k}^n(-1)^{j-k}\binom{n}{n-j}\binom{j}{j-k}\\ &=\sum_{j=k}^n\binom{n}{n-j}\binom{-k-1}{j-k}\\ &=\binom{n-k-1}{n-k}\tag{3} \end{align} $$ which is $1$ if $n=k$ and $0$ otherwise. $\quad\square$

Proof 3: Consider the generating function for $(1)$ as a function of $k$: $$ \begin{align} \sum_{k=0}^n\sum_{j=k}^n(-1)^{j-k}\binom{n}{j}\binom{j}{k}x^k &=\sum_{j=0}^n\sum_{k=0}^j(-1)^{j-k}\binom{n}{j}\binom{j}{k}x^k\\ &=\sum_{j=0}^n(-1)^j\binom{n}{j}(1-x)^j\\ &=(1-(1-x))^n\\[12pt] &=x^n\tag{4} \end{align} $$ Equating the coefficients of $x^k$ in $(4)$ proves the result. $\quad\square$

Theorem (Generalized Inclusion-Exclusion Principle)

Let $\{S(i)\}_{i=1}^m$ be a finite collection of sets from a finite universe.

Let $N(j)$ be the sum of the sizes of all intersections of $j$ of the $S(i)$: $$ N(j)=\sum_{|A|=j}\left|\,\bigcap_{i\in A} S(i)\,\right|\tag{5} $$ Thus, $N(0)$ is the size of the universe.

Then, the number of elements in exactly $k$ of the $S(i)$ is $$ \sum_{j=0}^m(-1)^{j-k}\binom{j}{k}N(j)\tag{6} $$

Proof:

An element that is in $n$ of the $S(i)$ is counted $\binom{n}{j}$ times in $N(j)$. That is, there are $\binom{n}{j}$ ways to choose the $j$ sets in the intersection from the $n$ sets that contain the element. The Cancellation Lemma says that this element is counted once in $(6)$ if $n = k$ and is cancelled out otherwise. $\quad\square$

Using the identity $$ \sum_{k=0}^n(-1)^k\binom{j}{k}=(-1)^n\binom{j-1}{n}\tag{7} $$ where $\binom{-1}{n}=$$(-1)^n\binom{n}{n}$$=(-1)^n$$[n\ge0]$, we get the following

Corollary 1:

The number of elements in at most $k$ of the $S(i)$ is $$ \sum_{j=0}^m(-1)^{j-k}\binom{j-1}{k}N(j)\tag{8} $$

Using the identity $$ \sum_{k=n}^j(-1)^k\binom{j}{k}=(-1)^n\binom{j-1}{j-n}\tag{9} $$ again where $\binom{-1}{n}=(-1)^n\binom{n}{n}=(-1)^n[n\ge0]$, we get the following

Corollary 2:

The number of elements in at least $k$ of the $S(i)$ is $$ \sum_{j=k}^m(-1)^{j-k}\binom{j-1}{j-k}N(j)\tag{10} $$

The Inclusion-Exclusion Principle

The usual Inclusion-Exclusion Principle is the case $k=1$ of Corollary 2.

However, the usual Inclusion-Exclusion Principle can also be derived by subtracting the number of objects that are in none of the $S(i)$ from the size of the universe. Using $(6)$ yields $$ \underbrace{\ \ \ N(0)\ \ \ \vphantom{\sum_j\binom{j}{0}}}_{\substack{\text{size of the}\\\text{universe}}}-\underbrace{\sum_{j=0}^m(-1)^{j}\binom{j}{0}N(j)}_{\substack{\text{number of elements}\\\text{in none of the $S(i)$}}}=\underbrace{\sum_{j=1}^m(-1)^{j-1}N(j)\vphantom{\binom{j}{0}}}_{\substack{\text{number of elements in}\\\text{at least one of the $S(i)$}}} $$

Related Question