1
$\begingroup$

Let $A_{1},\ A_{2}$, , $A_{n}$ be $n$ sets. Then $|A_{1}\cup A_{2}\cup ... \cup A_{n}|= \sum_{i}|A_{i}|-\sum_{i<j}|A_{i}\cap A_{j}|+ \cdots + (-1)^{n-1}|A_{1}\cap A_{2}\cap\ \cap A_{n}|. $

Proof. Suppose that $x\in \bigcup_{1 \le h \le n} A_h $ is in exactly $m$ of the sets $A_{1}, A_{2}$, . . . $, A_{n}$. How many of the sets of the form $A_{i_{1}}\cap A_{i_{2}}\cap\cdots\cap A_{i_{k}}$ with $i_1 < i_2 < \cdots < i_k$ is $x$ in? The answer is $\left(\begin{array}{l} m\\ k \end{array}\right)$ because it is just the number of ways of choosing $k$ of the sets which contain $x$.

$\color{red}{\blacklozenge}$ This means that on the right hand side of the formula, $x$ will be counted $ \left(\begin{array}{l} m\\ 1 \end{array}\right)\ -\ \left(\begin{array}{l} m\\ 2 \end{array}\right)\ +\cdots +(-1)^{m-1}\ \left(\begin{array}{l} m\\ m \end{array}\right) $ times.

I espy why the IEP and the last line (after the red lozenge) are true for $m \le 3$ sets, thanks to pictures like this one on page 2 of 7. Yet I don't perceive it when $m \ge 4$ (which I don't think can be visualised) ? Whence does this expression originate?

$\endgroup$
3
+50
$\begingroup$

You are right saying that no similar picture can be made with discs. However a set can be given any shape. Here's an example with four sets. Intersections of four sets

  • $A$ green
  • $B$ blue
  • $C$ yellow
  • $D$ red
  • $A\cap B$ pink
  • $A\cap C$ cyan
  • $A\cap D$ dark brown
  • $B\cap C$ light green
  • $B\cap D$ violet
  • $C\cap D$ orange
  • $A\cap B\cap C$ red brown in the middle
  • $A\cap B\cap D$ bright green
  • $A\cap C\cap D$ light brown
  • $B\cap C\cap D$ pale blue
  • $A\cap B\cap C\cap D$ black
| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

I'd like to answer this question from three different point of views. Here's a quick overview: We start with focus at

1.) The essence of IEP: Transformation of at least information to exact information

2.) Analyse the red lozenge expression

3.) Eye-birds view: The essence of IEP is just a shift by one

4.) No more answers, but further questions

Now to the details:

1.) The essence of IEP: Transformation of at least information to exact information:

If counting objects having at least a number of properties is simple, but counting objects having exactly a number of properties is difficult, than the IEP comes into play.

In our example the objects are the elements contained in $A_1,\dots,A_n$ and the properties of an element $x$ are the sets $A_j,1\leq j\leq n$, which contain $x$.

If we have this essence of IEP in mind and we look at the expression:

\begin{align*} \left|\bigcup_{j=1}^{n}A_j\right|=\sum_{j=1}^{n}\left|A_j\right| -\sum_{1\leq i \leq j \leq n}\left|A_i\cap A_j\right|\pm\cdots+(-1)^{n-1}\left|\bigcap_{j=1}^{n}A_j\right|\tag{1} \end{align*}

we observe, that the right hand side (RHS) consists of summands with at least information. Because e.g.

$$\left|A_i\cap A_j\right|\quad \text{in}\quad\sum_{1\leq i \leq j \leq n}\left|A_i\cap A_j\right|$$

counts not only the number of elements which are in $A_i$ and $A_j$ it counts more precisely the number of elements which are at least in $A_i$ and $A_j$, since elements $x$ in $A_i\cap A_j$ may also be contained in other sets of $A_1,\dots,A_n$.

Now, the LHS $$\left|\bigcup_{j=1}^{n}A_j\right|$$ shows the number of elements which are exactly in $\bigcup_{j=1}^{n}A_j$.

2.) Analyse the red lozenge expression

Keeping 1.) in mind we analyse the expression: \begin{align*} 1 = \binom{m}{1}-\binom{m}{2}\pm\cdots+(-1)^{m-1}\binom{m}{m}\tag{2} \end{align*} which results from looking at a specific element $x$ which is contained in exactly $m$ sets of $A_1,\dots,A_n$.

We start by looking at the RHS of $(2)$:

In $\binom{m}{1}$ the element $x$ is counted once for each of the $m$ sets which contain $x$.

Since these sets $A_j$ are not disjoint (they contain $x$), some elements are counted more than once. Those are the elements that belong to at least two of the sets $A_j$, or the intersection $A_i \cap A_j$. This is valid especially for the element $x$. We wish to consider every such intersection, so we subtract $\binom{m}{2}$.

When we subtract the sum of the number of elements in such pairwise intersections, some elements may have been subtracted more than once. Those are the elements that belong to at least three of the sets $A_j$ and one of them is $x$ (assuming $m\geq3$). So, we add the sum of the elements of intersections of the sets taken three at a time, resulting in subtracting $\binom{m}{3}$.

This process goes on with sums being alternately added or subtracted until we come to the last term - the intersection of all sets $A_j$.

These arguments are for better insight only. To see that the RHS identity $(2)$ is clearly valid, we observe

\begin{align*} \binom{m}{1}&-\binom{m}{2}\pm\cdots+(-1)^{m-1}\binom{m}{m}\\ =&\binom{m}{0}-\left(\binom{m}{0}-\binom{m}{1}+\binom{m}{2}\mp\cdots+(-1)^{m}\binom{m}{m}\right)\\ =&1-(1-1)^m\\ =&1 \end{align*}

Some more and alternative insight into the relationship between exact and at least information is provided in the next section.

3.) Eye-birds view: The essence of IEP is just a shift by one

It's remarkable, that from a higher point of view, namely when using generating functions this information is condensed and encoded by a simple shift by one in the arguments.

Note: This shift by one provides a kind of bird's-eye view to the alternating sum of the IEP.

Let

  • $\binom{m}{k}$ ... number of intersections of $k$ sets, each containing elements which are contained in exactly $m$ sets

  • $e_m$ ... number of elements, which are in exactly $m$ sets

  • $l_m$ ... number of elements, which are in at least $m$ sets

Using this notation, the IEP (1) can now be written as: \begin{align*} e_1+e_2+\cdots+e_n=l_1-l_2\pm\cdots+(-1)^{n-1}l_n \end{align*}

Observe, that \begin{align*} l_k=\sum_{m=k}^{n}\binom{m}{k}e_m\qquad\qquad0\leq k\leq n\tag{3} \end{align*}

We now introduce the generating functions $L(z)$ and $E(z)$ having $l_k$ and $e_k$ as coefficients: \begin{align*} L(z) = \sum_{k=0}^{n}l_kz^k\qquad\qquad E(z)=\sum_{k=0}^{n}e_kz^k \end{align*}

According to $(3)$ we get: \begin{align*} L(z)&=\sum_{k=0}^{n}l_kz^k\\ &=\sum_{k=0}^{n}\sum_{m=k}^{n}\binom{m}{k}e_mz^k\\ &=\sum_{m=0}^{n}e_m\sum_{k=0}^{m}\binom{m}{k}z^k\\ &=\sum_{m=0}^{n}e_m(z+1)^m\\ &=E(z+1) \end{align*}

From this we conclude that

$$E(z)=L(z-1)$$ Note: This is remarkable, since the wanted $e_m$ which are the coefficients of $z^m$ of $E(z)$ can be simply calculated by changing $z$ to $z-1$ in the equation $L(z)=E(z+1)$ of the corresponding generating functions.

The coefficients $e_m=[z^m]E(z)$ giving the number of elements which are in exactly $m$ sets can now be calculated from $L(z-1)$.

\begin{align*} e_m&=[z^m]E(z)\\ &=[z^m]L(z-1)\\ &=[z^m]\sum_{k=0}^{n}l_k(z-1)^k\\ &=[z^m]\sum_{k=0}^{n}l_k\sum_{j=0}^{k}\binom{k}{j}z^j(-1)^{k-j}\\ &=\sum_{k=0}^{n}l_k\binom{k}{m}(-1)^{k-m}\\ &=\sum_{k=m}^{n}(-1)^{k-m}\binom{k}{m}l_k \end{align*}

We summarise: \begin{align*} L(z)=E(z+1)&\qquad\qquad\qquad l_k=\sum_{m=k}^{n}\binom{m}{k}e_m\\ &\tag{4}\\ E(z)=L(z-1)&\qquad\qquad\qquad e_k=\sum_{m=k}^{n}(-1)^{m-k}\binom{m}{k}l_m\\ \end{align*}

Note: $l_k$ and $e_k$ form a so called inverse relation pair. So, the IEP can also be expressed in terms of this specific combinatorial identity. Many different inverse relation pairs can be found e.g. in Combinatorial Identities from John Riordan. The above pair is stated in section 2.2: The simplest inverse relations.

Summary: From this generating functionological view and adapting H.S.Wilf (see section 4.2 from Generatingfunctionology): This is the Sieve Method (IEP): The act of replacing the variable $z$ by $z-1$ in the generating function $L(z)$ replaces the unfiltered data $\{l_m\}$ by the sieved quantities $\{e_m\}$.

This interesting question from LePressentiment gives rise to ask if there are further interesting principles based upon other binomial inverse pairs which could be applied to boolean algebras.

4.) No more answers, but further questions:

Question: Are there further inverse relation pairs which can be interpreted in the context of boolean algebras and which provide an interesting transformation of information similar to the IEP's at least to exact transformation?

Please, find here the corresponding MSE question.

| cite | improve this answer | |
$\endgroup$
2
+50
$\begingroup$

No pictures are really needed, the left brain hemisphere can do this all by itself.

Let us see what the right hand side of your formula, $$ \sum_i|A_{i}|-\sum_{i<j}|A_{i}\cap A_{j}|+\cdots +(-1)^{n-1}|A_{1}\cap A_{2}\cap\ldots \cap A_{n}|, \tag1 $$ counts exactly. Since the formula has signs, it will be a weighted enumeration with weights$~\pm1$. Each term in one of the summations is associated to a collection of summations variables $i_1<i_2<\cdots<i_k$ which is completely determined by the set $I=\{i_1,i_2,\ldots,i_k\}$; thus summand is $|A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_k}|$, and it has sign $(-1)^{k-1}$. So the formula counts pairs $(I,x)$, where $I$ is any non-empty subset of $\{1,\ldots,n\}$ and $x\in\bigcap_{i\in I} A_i$, with weight $(-1)^{|I|-1}$. Now rather than fixing $I$ first and then letting $x$ vary, one can fix $x$ first and then let $I$ vary (a standard double counting trick). Since we require $x\in A_i$ for all $i\in I$, once $x$ is fixed one might as well only consider those $A_i$ for which $x\in A_i$, so one can put $J_x=\{\, i\mid x\in A_i\,\}$, and the sets $I$ that one can take for the given$~x$ are precisely all the non-empty subsets of$~J_x$, and each such $I$ is counted with weight $(-1)^{|I|-1}$. Now if $m=|J_x|$, then the are $\binom m1$ singleton sets that can be chosen for$~I$, $\binom m2$ sets of size$~2$, and in general $\binom mk$ subsets of size$~k$. All in all the contribution to the counting for any fixed $x$ is $$ \binom m1-\binom m2+\binom m3-\cdots +(-1)^{m-1}\binom mm \tag2 $$ where $m=|J_x|$, as the cited text claims.

It is now of course easy to see that $(2)$ gives $1$ whenever $m>0$, while it gives $0$ when $m=0$, so summing over all $x$ gives $|A_1\cup A_2\cup\cdots\cup A_n|$, the left hand side of the original formula.

| cite | improve this answer | |
$\endgroup$

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.