Inclusion-Exclusion Principle

Math for CS · Axiom Academy

The Inclusion-Exclusion Principle Counting with overlapping sets -- add, subtract, add back, repeat When sets overlap, simply adding their sizes overcounts elements in the intersection. We need to subtract the overlap. With three sets, the pattern continues: add individual sizes, subtract pairwise intersections, add back the triple intersection. |A_2| = 500 , |A_3| = 333 , |A_5| = 200 Total: 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734 With n sets, the formula has 2^n - 1 terms (one for each non-empty subset of sets). This can be expensive, but many problems have structure that simplifies the computation. A derangement is a permutation where no element stays in its original position. How many derangements of \ 1, 2, , n\ exist? |A_i| = (n-1)! (fix one element, permute the rest) |A_i A_j| = (n-2)! (fix two elements) In general: any k elements fixed gives (n-k)! permutations There are k ways to choose which k elements are fixed

This is the written version of the interactive lesson above. See the full Math for CS course.