Demonstrate another way to implement the Inclusion–exclusion principle?

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.

Solution 1:

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)$}}} $$

Solution 2:

I'm not sure whether this is what you're getting at, but you can use an index set $S$ to represent which intersection is being taken. This is similar, but not identical to, your binary representation. Then the sign of a particular term is $(-1)^{\lvert S\rvert-1}$. If $[1,n]$ denotes the set $\{1,2,\ldots,n\}$, then the Principle of Inclusion-Exclusion can be written $$ \left\lvert\bigcup_{i\in[1,n]}A_i\right\rvert+{\sum_{S\subseteq[1,n]}}'(-1)^{\lvert S\rvert}\left\lvert\bigcap_{i\in S}A_i\right\rvert=0. $$ I use the prime after the summation symbol to indicate that the sum runs over all subsets of $[1,n]$ except for the empty set.

If we adopt the reasonable convention that the empty intersection equals the universal set, then we don't have to exclude the empty set from the sum, and we can write $$ \left\lvert\left(\bigcup_{i\in[1,n]}A_i\right)'\right\rvert=\sum_{S\subseteq[1,n]}(-1)^{\lvert S\rvert}\left\lvert\bigcap_{i\in S}A_i\right\rvert=0. $$

Solution 3:

By far the cleanest proof of the principle of inclusion and exclusion (with the extra bonus of a simple recipe and easy to remember formulas) is the one given by Wilf in "generatingfunctionology". It requires a bit of familiarity with generating functions/power series, but nothing outlandish. If you are OK with summations and the binomial formula, you are all set.

Let $\Omega$ be a universe, and $\mathcal{A}_i \subseteq \Omega$ be a collection of sets. We will identify the sets with properties, that is, $\mathcal{A} = \{\omega \in \Omega \colon p_\mathcal{A}(\omega)\}$. Call the set of all properties $\mathcal{P}$. We define:

• $e_k$: Number of objects in $\Omega$ with exactly $k$ properties
• $N_k$: Number of objects in $\Omega$ with at least $k$ properties
• $N(\supseteq \mathcal{S})$: The number of objects in $\Omega$ with at least the properties $S \subseteq \mathcal{P}$
• $P(\omega)$: The set of properties $\omega$ has (the sets to which it belongs)

Knowing the $N(\supseteq S)$ allows to compute the $N_r$: $$ \begin{align*} N_r &= \sum_{\lvert \mathcal{S} \rvert = r} N(\supseteq \mathcal{S}) \\ &= \sum_{\lvert \mathcal{S} \rvert = r} \sum_{\substack{\omega \in \Omega \\ \mathcal{S} \subseteq P(\omega)}} 1 \\ &= \sum_{\omega \in \Omega} \sum_{\substack{\lvert \mathcal{S} \rvert = r \\ \mathcal{S} \subseteq P(\omega)}} 1 \\ &= \sum_{\omega \in \Omega} \binom{\lvert P(\omega) \rvert}{r} \end{align*} $$ On the other hand, an object with $t$ properties will be counted $\binom{t}{r}$ times in $N_r$ (each $r$-subset of properties is considered once), so: $$ N_r = \sum_{t \ge 0} \binom{t}{r} e_t $$ Define: $$ \begin{align*} N(z) &= \sum_{k \ge 0} N_k z^k \\ E(z) &= \sum_{k \ge 0} e_k z^k \end{align*} $$ Substituting the expression for $N_r$ in terms of the $e_t$ in $N(z)$: $$ \begin{align*} N(z) &= \sum_{r \ge 0} \left( \sum_{t \ge 0} \binom{t}{r} e_t \right) z^r \\ &= \sum_{t \ge 0} e_t \left(\sum_{r \ge 0} \binom{t}{r} z^r \right) \\ &= \sum_{t \ge 0} e_t (1 + z)^t \\ &= E(1 + z) \end{align*} $$ So we get the remarkable formula: $$ E(z) = N (z - 1) $$ Most of the time one is interested in the objects with no properties, i.e., $e_0 = E(0) = N(-1)$.

As an example, consider derangements of $n$ elements. Our universe $\Omega$ is the set of all permutations, and we say that a permutation has property $i$ if $i$ is a fixed point. So, as only the elements that aren't in $\mathcal{S}$ can be rearranged: $$ N(\supseteq \mathcal{S}) = (n - \lvert \mathcal{S} \rvert)! $$ Thus: $$ N_r = \sum_{\lvert \mathcal{S} \rvert = r} N(\supseteq \mathcal{S}) = \binom{n}{r} (n - r)! = \frac{n!}{r!} $$ So: $$ N(z) = n! \sum_{0 \le r \le n} \frac{z^r}{r!} $$ We want $e_0 = E(0) = N(-1)$: $$ e_0 = n! \sum_{0 \le r \le n} \frac{(-1)^r}{r!} $$