Principle of Inclusion and Exclusion

96 Views Asked by At

Im trying to derive $N(A\cup B\cup C)$ with the help of Venn Diagram.

$$|A\cup B\cup C| = |A| + |B| + |C| - |A\cap B| - |B\cap C| - |A\cap C| + |A\cap B\cap C|$$

I have reached the step where $N(A)+N(B)+N(C)$ is computed.I Can see the terms are getting cancelled out during addition of $N(A)+N(B)+N(C)$ how does this happen.

EDIT:

I don't know how to Type Symbols so im attaching a picture

enter image description here enter image description here

What i want to know is how N(A)+N(B)+N(C) is obtained after cancellation

2

There are 2 best solutions below

1
On

Take a look at how many times each element is counted. For example, if you have $x$ which is an element of $A$ and is not an element of $B$ and $C$. Then $x$ is only counted in $|A|$, not in the other sumands.

Now look at what happends if $x$ is in $A$ and $B$ but not in $C$. Now $x$ is counted in $|A|$ and in $|B|$, yielding $+2$ to the sum, but because it is also counted in $|A\cap B|$, it also yields $-1$, so all together, it yields $2-1=1$.

0
On

Hint Start by seeing why $|A\cup B| = |A|+|B|-|A\cap B|$ and then substitute: $$\begin{align*} |A\cup B\cup C| & = |A\cup (B\cup C)| = |A|+|B \cup C| - |A\cap (B\cup C)| \\ & = |A|+(|B|+|C|-|B\cap C|) - |(A\cap B) \cup (A\cap C)| \\ & = |A|+|B|+|C|-|B\cap C| - (|A\cap B| + |A\cap C| - |(A\cap B)\cap (A\cap C)|) \\ & = |A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C| + |A\cap B\cap C| \end{align*}$$