inclusion_exclusion_principle

The Inclusion-Exclusion Principle The inclusion-exclusion principle is an important combinatorial way to compute the size of a set or the probability of complex events. It relates the sizes of individual sets with their union. Statement The verbal formula The inclusion-exclusion principle can be expressed as follows: To compute the size of a union of multiple sets, it is necessary to sum the sizes of these sets  separately , and then subtract the sizes of all  pairwise  intersections of the sets, then add back the size of the intersections of  triples  of the sets, subtract the size of  quadruples of the sets, and so on, up to the intersection of  all  sets. The formulation in terms of sets The above definition can be expressed mathematically as follows: ∣ ∣ ∣ ⋃ i = 1 n A i ∣ ∣ ∣ = ∑ i = 1 n | A i | − ∑ 1 ≤ i < j ≤ n | A i ∩ A j | + ∑ 1 ≤ i < j < k ≤ n | A i ∩ A j ∩ A k | − ⋯ + ( − 1 ) n − 1 | A 1 ∩ ⋯ ∩ A n | | ⋃ i = 1...