To prove that every element is counted exactly once, consider an arbitrary element x that belongs to exactly r sets. To start the algorithm, add all the elements in all the sets, disregarding overlap. Thus x is counted r times. Next, x appears in (r:2) (r choose 2) pairs of sets, so subtract (r:2) from r. Next, x appears in (r:3) (r choose 3) set triples, So add (r:3) to the total. Continue alternating until (r:r) is reached. Of course r choose r, the last term, is 1. Our element x is only counted once at step r, since there is precisely one collection of r sets that contains x. The element cannot be a member of more than r sets by definition.
Add -1 to the beginning of this series, -1+r-(r:2)+(r:3)-(r:4)+…, and apply the binomial theorem in reverse to get -(1-1)r. This is zero, so the original series added up to 1, and x was counted exactly once.
| Inclusion exclusion also works for non-discrete applications, such as determining the area consumed by many intersecting regions. Partition the regions into squares of size ε, and envoke the theorem. then take the limit as ε approaches 0. In this illustration, the numbers indicate the overlap count. |
|