Inclusion-Exclusion Principle

## The counting problem A nightly deduplication job ingests several overlapping feeds and runs `k` **taint filters** over the merged stream - a filter marks a record as suspect for some reason (a blocked source, a malformed key, a stale timestamp). What the pipeline must report is the number of **clean** records: those that trip *none* of the filters. The only figures available from the reporting layer are match counts - how many records each filter caught, and how many were caught by a given combination of filters. The naive move is to add up the per-filter counts, subtract that from the total, and ship it. That is wrong whenever two filters can catch the same record, which is exactly the situation the job exists for. ## Why one subtraction over-corrects Write `N` for the total number of records and `A1 ... Ak` for the sets of records each filter catches. Follow a single record through the arithmetic: - a record caught by **no** filter is counted once in `N` and never touched again - correct; - a record caught by **one** filter is counted once, subtracted once - correct, it reaches zero; - a record caught by **two** filters is counted once and subtracted **twice** - it now contributes `-1`, so the count of clean records comes out too low; - a record caught by **three** filters is subtracted three times, contributing `-2`. So the first correction does not merely fail to be exact; it drives the answer in a direction that grows with how much the filters overlap. Adding every pairwise intersection back fixes the two-filter records, but a three-filter record sits in three different pairwise intersections and is now restored three times, landing back at `+1`. That is what forces the next subtraction, and the pattern does not stop until the intersections run out. ## The general statement The **inclusion-exclusion principle** states the clean count directly: `clean = N - sum |Ai| + sum |Ai and Aj| - sum |Ai and Aj and Ak| + ... + (-1)^k |A1 and ... and Ak|` A term built from an intersection of `j` filters carries the sign `(-1)^j`. There is one term for every subset of the `k` filters, including the empty subset whose intersection is the whole population and which supplies the leading `N`. That is `2^k` terms in total. The union form - the count of records caught by **at least one** filter - is the same identity rearranged, with `2^k - 1` non-empty terms and the signs starting negative. ## Why the alternation cancels exactly Take a record caught by exactly `m` filters and ask how many terms it appears in. It appears in every term built from a subset of *those* `m` filters, and there are `C(m,j)` such subsets of size `j`. Its net contribution is therefore the signed binomial row for `m`: | filters matched (m) | contributions by term size | net | |---|---|---| | 0 | +1 | 1 | | 1 | +1, -1 | 0 | | 2 | +1, -2, +1 | 0 | | 3 | +1, -3, +3, -1 | 0 | | m | sum of (-1)^j C(m,j) | (1-1)^m = 0 | The last row is the whole argument: the signed row sum is the binomial expansion of `(1 - 1)^m`, which is `0` for every `m >= 1` and `1` for `m = 0`. Every tainted record cancels itself out no matter how many filters caught it, and every clean record survives with weight one. Nothing about the filters is assumed - not independence, not disjointness, not similar sizes. It is an identity over finite sets, so it holds for whatever the data happens to look like. ## Stopping early on purpose Because the terms alternate, a **truncated** sum is not noise - it brackets the answer, and the direction depends on where you stopped. Summing the per-filter counts alone over-states the union (every multiply-caught record is counted more than once), so it gives an upper bound on the union and hence a lower bound on the clean count. Subtract the pairwise overlaps and you undershoot the union, which flips both bounds. Truncation is a legitimate engineering move when the deep intersections are expensive to measure, but it must be reported as a bound, never as the count. ## Where engineers get this wrong 1. **Stopping after the single subtraction**, which is only correct when no record can be caught twice - the case where the formula was not needed. 2. **Adding pairs back and stopping there**, which leaves triple-caught records mis-weighted and is the most common half-remembered version. 3. **Reaching for independence**, multiplying rates as if the filters were unrelated. Overlapping feeds correlate heavily, and the identity never needs that assumption anyway. 4. **Forgetting the empty term.** The leading `N` is a term of the sum, and dropping it turns the clean count into the negated union.