The inclusion-exclusion principle counts elements in the union of sets: |A union B| = |A| + |B| - |A intersect B|. For three sets: |A union B union C| = |A| + |B| + |C| - |A intersect B| - |A intersect C| - |B intersect C| + |A intersect B intersect C|. In PnC, this handles "at least one of several conditions." Example: arrangements of ABCDEF where A is not first AND B is not second AND C is not third — use inclusion-exclusion on violations. Also used for surjections: number of onto functions from an n-set to a k-set = sum over i from 0 to k of (-1)^i * C(k,i) * (k-i)^n. JEE rarely goes beyond three-set inclusion-exclusion.
Part of ALG-07 — Permutations & Combinations
Inclusion-Exclusion Principle
Want to generate AI summaries of your own documents? NoteTube turns PDFs, videos, and articles into study-ready summaries.
Sign up free to create your own