0
$\begingroup$

I have a question that may be trivial but I just can't find an appropriate answer on the Internet. The inclusion-exclusion principle can be used to discern the cardinality of the union among sets $\bar{a} =\lvert \cup_{i=1}^n A_i \rvert$. Similarly, I can use it to count intersections, $\bar{b} =\lvert\cap_{i=1}^n A_i \rvert$, in which case $\bar b$ is the number of elements that belong to all sets. Now, I would like to count the number of elements that are part of any intersection between the sets $A_i$ taken by two, i.e., $ \bar c = \lvert \cup \left\{ A_i \cap A_j \right\} \rvert$. Does this have a particular name? I guess it is a less restrictive intersection operation, as $\bar c \geq \bar b$.

Thanks for your help.

$\endgroup$
3
  • 1
    $\begingroup$ It's not clear what the question is. Are you looking for a way to compute $\bar{c}$? In that case the inclusion-exclusion principle would seem to do the job, and you'll likely end up with a subexpression of the result of I-E applied to $|\bigcup_{i=1}^n A_i|$. $\endgroup$
    – Paul McKenney
    Feb 19, 2013 at 15:54
  • 1
    $\begingroup$ Also, it seems that the set-theory tag is a bit inappropriate; combinatorics is probably better. $\endgroup$
    – Paul McKenney
    Feb 19, 2013 at 15:55
  • $\begingroup$ Given sets $A_1, \dots, A_n$, I would like to find the set of elements that belong to any intersection of sets taken by two, i.e., $\bigcup_{i \neq j} A_i \cap A_j$. Is there a name for this? $\endgroup$
    – Alejandro Marcos Aragon
    Feb 19, 2013 at 16:35

1 Answer 1

Reset to default
0
$\begingroup$

Take a look at Wilf's "generatingfunctionology", he derives a marvelous formula that gives the answer to such questions very simply.

$\endgroup$
2
  • $\begingroup$ Hi vonbrand, thanks for your answer. Got the book, but I can't seem to find such magical equation. Could you please point out which one you're talking about? $\endgroup$
    – Alejandro Marcos Aragon
    Feb 19, 2013 at 23:24
  • $\begingroup$ Section 4.2 "A generatingfunctiological view of the sieve method" $\endgroup$
    – vonbrand
    Feb 19, 2013 at 23:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .