Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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|$. –  Paul McKenney Feb 19 '13 at 15:54
1  
Also, it seems that the set-theory tag is a bit inappropriate; combinatorics is probably better. –  Paul McKenney Feb 19 '13 at 15:55
    
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? –  Alejandro Marcos Aragon Feb 19 '13 at 16:35

1 Answer 1

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

share|improve this answer
    
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? –  Alejandro Marcos Aragon Feb 19 '13 at 23:24
    
Section 4.2 "A generatingfunctiological view of the sieve method" –  vonbrand Feb 19 '13 at 23:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.