A problem on Principle of inclusion and exclusion.

67 Views Asked by At

enter image description here

I am having a little bit of trouble understanding this part in my book. I know the normal PIE that is n(A+B) = n(A) + n(B) - n(AB) and then so on for more sets but I am not able to understand this form. What do they mean by numerical value associated is constant, what is meant by N(i) common value?

So could someone please explain this to me.

Thank you!

1

There are 1 best solutions below

5
On BEST ANSWER

They are inventing notation to simplify things... in the case that $n(a_1a_2)=n(a_1a_3)=n(a_1a_4)=\dots=n(a_2a_3)=\dots=n(a_ia_j)$ for all $i<j$ then rather than writing $n(a_1a_2)$ they write $N(2)$. Similarly, in the case that $n(a_1a_2a_3)=n(a_1a_2a_4)=\dots=n(a_ia_ja_k)$ for all $i<j<k$ then instead of writing $n(a_1a_2a_3)$ they just write $N(3)$ and so on for larger tuples.

Reworded, they are saying that in the event that all pairs have the same size as each other, all triples have the same size as each other, etc... then:

$|a_1\cup a_2\cup \dots \cup a_n|=n\cdot |a_1|-\binom{n}{2}\cdot |a_1\cap a_2| + \binom{n}{3}\cdot |a_1\cap a_2\cap a_3|-\dots + (-1)^{k+1} \binom{n}{k}|a_1\cap a_2\cap \cdots \cap a_k|+\dots$

They just wanted to shorten the notation, rather than saying "The size of the intersection of the $k$ sets $|a_1\cap a_2\cap \dots \cap a_k|$" they instead just say "The size of the intersection of $k$ sets $N(k)$."