3
$\begingroup$

IF $A$,$B$,$C$ are finite sets then,

Number of elements in exactly one of sets $A$,$B$,$C$:$$n(A)+n(B)+n(C)-2 \times n(A \cap B)-2 \times n(A \cap C)-2 \times n(C \cap B) + 3 \times n(A \cap B \cap C)$$

Number of elements in exactly two of the sets $A$,$B$,$C$: $$n(A \cap B)+(A \cap C)+n(C \cap B) - 3 \times n(A \cap B \cap C)$$

Could somebody explain how can we prove them? I think it's something with inclusion and exclusion but am not getting how to get those results.Also I think we can have a generalized results for these kinds ?!

  • 1
    It is exactly PIE (inclusion-exclusion). This is trivial though with a Venn diagram.2010-12-21
  • 1
    This could be helpful: http://www.cut-the-knot.org/arithmetic/combinatorics/InclusionExclusion.shtml and http://www.math.lsa.umich.edu/~baik/Teaching/inclusion-exclusion.pdf2010-12-21
  • 2
    Please change the title to something more descriptive.2010-12-21
  • 1
    @Moron:Please check.2010-12-22
  • 0
    Deb: Seems ok...2010-12-22
  • 0
    @InterestedGuest That first link is what you need. See point (2).2012-10-12

1 Answers 1

2

You're right about inclusion and exclusion.

For the number of elements in exactly one of the sets, you first count all $n(A) + n(B) + n(C)$ elements. You disregard the $n(A \cap B)$ elements twice, as you need to disregard them from your count for both $A$ and $B$. The logic is similar for $A \cap C$ and $B \cap C$. Finally, you've disregarded the $n(A \cap B \cap C)$ elements in all three sets twice, so you have to correct the count by adding this quantity back in.

I bet you can figure out the second one once you've carefully understood the first.

  • 0
    Thanks, I understood,it was really trivial on analyzing with a venn diagram.2010-12-22