Inclusion-exclusion for n sets continued
|A1 ? A2 ? … ? An| = s1 - s2 + s3 - s4 + s5 - s6 … + (-1)n+1sn.
In other words, |A1 ? A2 ? … ? An| is the sum of all the si, where
si has the “+” sign if i is odd, and the “-” sign if i is even.
We state this principle without a proof.
Example: |A1 ? A2 ? A3 ? A4| =
(|A1| + |A2| + |A3| + |An|) -
(|A1 ? A2| + |A1 ? A3| + |A1 ? A4| + |A2 ? A3| + |A2 ? A4| + |A3 ? A4|) +
(|A1 ? A2 ? A3| + |A1 ? A2 ? A4| + |A1 ? A3 ? A4| + |A2 ? A3 ? A4|) -