Inclusion-exclusion for n sets
Assume we have n sets: A1,A2,…,An. |A1 ? A2 ? … ? An| = ?
s1 be the sum of the cardinalities of all of these sets, i.e.
s1 = |A1| + |A2| + … + |An|
s2 be the sum of the cardinalities of the intersections of all possible
pairs of these sets, i.e.
s2 = |A1 ? A2| + |A1 ? A3| … + |A1 ? An| +
+ |A2 ? A3| + |A2 ? A4| … + |A2 ? An| +
s3 be the sum of the cardinalities of the intersections of all possible
triples of these sets, i.e.
s3 = |A1 ? A2 ? A3 | + |A1 ? A2 ? A4 | + … + |A1 ? A2 ? An | +
+ |A1 ? A3 ? A4 | + |A1 ? A3 ? A5 | + … + |A1 ? A3 ? An | +
+ … + |An-2 ? An-1 ? An |
and so on. Note that sn= |A1 ? A2 ? … ? An |