Inclusion exclusion formula with given property.

47 Views Asked by At

Suppose that we have given finite sets $A_{1},A_{2},...,A_{m}$ Then it is known that there is a formula: $$|A_{1}\cup A_{2}\cup\ldots\cup A_{m}|=\sum_{i=1}^{m}(-1)^{i-1}p_{i}$$

Where $$p_{i}=\sum_{J\subset \{1,2,...,m\},|J|=i}|\bigcap_{j\in J}A_{j}|$$

However if these sets are pairwise disjoint then the formula gets simpler: $$|A_{1}\cup A_{2}\cup\ldots\cup A_{m}|=\sum_{i=1}^{m}|A_{i}|=p_{1}$$

What could be said about the formula when for each $i,j\in \{1,\ldots,m\}$ so that $i\neq j$ we have $|A_{i}\cap A_{j}|\le 1$

To be more specific let $x_{i}=|\{j\in\{1,2,\ldots,m\}: |A_{i}\cap A_{j}|=0\}|$ and $y_{i}=|\{j\in\{1,2,\ldots,m\}: |A_{i}\cap A_{j}|=1\}|$

How to use that numbers?

1

There are 1 best solutions below

0
On

Not all that much can be said. It depends on the intersections of more than two sets. This yields a lower bound, though. Each partial sum of the inclusion–exclusion sum is a bound (alternatingly upper and lower), so the second partial sum yields

\begin{eqnarray} |A_{1}\cup A_{2}\cup\ldots\cup A_{m}| &\ge& \sum_{i=1}^m|A_i|-\sum_{i\ne j}|A_i\cap A_j| \\ &=& \sum_{i=1}^m|A_i|-\frac12\sum_{i=1}^my_i\;. \end{eqnarray}