9
$\begingroup$

I'm attempting to solving 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.

$\endgroup$
  • $\begingroup$ I'm not sure what you mean by "solve", but it's the wrong word. One might prove the inclusion-exclusion principle, or one might use the inclusion-exclusion principle to solve a problem. $\endgroup$ – Michael Hardy Sep 11 '13 at 23:35
4
$\begingroup$

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. $$

$\endgroup$
  • $\begingroup$ Re: "I'm not sure whether this is what you're getting a". I suppose what I want to express is that we can generate all of the sets in that binary-pattern way, and that the bit-population being even or odd determines if we add or subtract the term. $\endgroup$ – Incognito Jan 19 '12 at 15:39
  • 2
    $\begingroup$ The binary pattern can be identified with the indicator function, $\mathbf{1}_S$ of the set $S$. If you scroll down to the section Basic properties in the Wikipedia article linked to above, you will see a form of the Principle of Inclusion-Exclusion expressed using indicator functions. $\endgroup$ – Will Orrick Jan 19 '12 at 19:45
18
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think it may be misleading to say that $N_r$ is the number of objects with at least $r$ properties. By your formula $N_1 = \sum_{\omega \in \Omega} P(\omega)$ is not the number of objects with at least $1$ property, but instead the number of pairs $(\omega, p)$, with $\omega \in \Omega$ and $p \in \mathcal{P}$ such that $\omega$ has property $p$. Of course this interpretation is clear from your proof. For example, the number of permutations of $\{1,2,3\}$ with at least one fixed point is $4$ (the identity and three swaps), but $N_1 = 3!/1! = 6$ since the identity is counted three times. $\endgroup$ – Mark Wildon Apr 14 '18 at 11:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.