0
$\begingroup$

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 .

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ What wiki page is saying that it will depends total number of sets not the cardinality of those sets . am I right ? and Wikipage is also referring the same book as I am . $\endgroup$ – optional Jun 19 '17 at 5:27

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.