Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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=0}^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.

share|improve this question
1  
Take a look at Wilf's "generatingfunctionology" <math.upenn.edu/~wilf/DownldGF.html>;, it has a very nice proof (and a much more usable formula too). –  vonbrand Feb 9 '13 at 3:51
    
Here's a working link: math.upenn.edu/~wilf/DownldGF.html to a great book. –  Fred Kline Sep 11 '13 at 23:12
    
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. –  Michael Hardy Sep 11 '13 at 23:35

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
    
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. –  Incognito Jan 19 '12 at 15:39
    
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. –  Will Orrick Jan 19 '12 at 19:45

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} $$ 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 Vanermonde'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$ 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 the sum of the sizes of all intersections of $j$ of the $S(i)$; 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{5} $$

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 $(5)$ 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{6} $$ where $\binom{-1}{n}=(-1)^n$, we get the following

Corollary:

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

The Inclusion-Exclusion Principle

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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