Special case in inclusion exclusion principle

Question

In the book Introductory combinatrics by Richard Brualdi it include a special case in inclusion exclusion principle as follows:

Assume that the size of set $$A_{i_1}\bigcap A_{i_2}\bigcap A_{i_3}... A_{i_k}$$ that occurs in inclusion exclusion principle depends only on $$k$$ and not on which k sets are used in intersections. Thus there are constants $$\alpha_0,\alpha_1,\alpha_2 ... \alpha_n$$ such that $$\alpha_0 = \vert S\vert$$ $$\alpha_1 =\vert A_1 \vert = \vert A_2 \vert = ... \vert A_m\vert$$ $$\alpha_2 = \vert A_1 \bigcap A_2 \vert = ... \vert A_{m-1} \bigcap A_m \vert$$ $$...$$ $$\alpha_m = \vert A_1 \bigcap A_2 \bigcap A_3 ... A_m\vert$$

in this case inclusion exclusion principle simplifies to $$\vert \bar A_1 \bigcap \bar A_2 \bigcap ... \bar A_m \vert=\alpha_0-\binom{m}{1}\alpha_1 + \binom{m}{2}\alpha_2 -\binom{m}{3}\alpha_3 + ... + \left(-1\right)^k\binom{m}{k}\alpha_k + ... + \left(-1\right)^m\alpha_m.$$

I am not getting this theorm clearly and the way it is derived . I need a lucid explanation .

Answer 1

This "special case" is the case in which the intersection of $k$ different sets always has the same size, namely $\alpha_k$.

So $$|S|-\sum_\text{1 set}|A_i|+\sum_\text{2 sets}|A_i\cap A_j|-\sum_\text{3 sets}|A_i\cap A_j\cap A_k|+...$$

becomes $$\begin{align*}&|S|-\sum_\text{1 set}\alpha_1+\sum_\text{2 sets}\alpha_2-\sum_\text{3 sets}\alpha_3+...\\=\quad&|S|-c_1\alpha_1+c_2\alpha_2-c_3\alpha_3+...\end{align*}$$

where $c_k$ is the number of ways to pick $k$ sets at a time, out of $m$. But that's obviously $m\choose k$.

Answer 2

It is easy to understand the intuition behind [the general case of] the inclusion-exclusion principle from a venn diagram, at least in the cases $m=2$ or $m=3$; see the wikipedia page for example.

The "special case" that is described in the post is when all the similar-looking shapes in the venn diagram actually have the same number of elements. For example, when $m=3$, it states that the three circles each have $\alpha_1$ elements, and the three [American] football-shaped pieces (intersection of two circles) each have $\alpha_2$ elements.