--- title: "Inclusion-Exclusion" description: "Count a union by adding the parts, subtracting the pairwise overlaps, adding the triples back, and prove the alternating pattern is right." canonical: https://lightmysky.com/learn/mathematics/inclusion-exclusion-mt_MgU-IMpVHA source: https://lightmysky.com/learn/mathematics/inclusion-exclusion-mt_MgU-IMpVHA.md retrieved: 2026-09-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # Inclusion-Exclusion Count a union by adding the parts, subtracting the pairwise overlaps, adding the triples back, and prove the alternating pattern is right. Subject: Mathematics · Area: Discrete Mathematics · Ages 19 to 20 Page: https://lightmysky.com/learn/mathematics/inclusion-exclusion-mt_MgU-IMpVHA ## Ready when they can - Apply the formula to three and to four overlapping sets - Prove the general formula by tracking how often one element is counted - Count derangements or surjections by applying the principle to a well-chosen family of sets ## Lesson: Count the union without double counting Adding two overlapping sets counts the overlap twice, so subtract it once. The union equals the sum of the sizes minus the size of the overlap. With 30 in chess, 25 in drama, and 10 in both, you get 30 plus 25 minus 10, which is 45. Each shared member ends up counted exactly once. **Example.** With three sets the overlaps overlap too, so one correction is not enough. Add the three singles, subtract the three pairwise overlaps, then add back the triple overlap. With 20 liking tea, 15 coffee, and 12 juice, pairwise overlaps of 8, 6, and 5, and a triple of 3, you get 47 minus 19 plus 3, which is 31. The triple was removed three times, so it must be added back. The signs keep alternating as sets are added: add singles, subtract pairs, add triples, subtract quadruples, and so on. You prove the pattern by tracking one element through the sum. An element in exactly two sets is counted twice in the singles and subtracted once in the pairs, giving 2 minus 1, which is 1. Every element lands at exactly 1. **Example.** Derangements show the sieve in action. Three letters into three envelopes avoid every correct envelope in only 2 orders, namely 231 and 312. Sieving four items over their four fixed-point sets gives 24 minus 24 plus 12 minus 4 plus 1, which is 9. Each term corrects the overcount of the one before. **Recap.** Add the parts, fix the overlaps with alternating signs, and check the fix on one element. ## Practice 14 questions on this page, each with its working shown. ## Needs first - [Sets & Venn Diagrams](https://lightmysky.com/learn/mathematics/sets-and-venn-diagrams-mt_1YwOCMMwD8) - [Counting with the Product and Sum Rules](https://lightmysky.com/learn/mathematics/counting-with-the-product-and-sum-rules-mt_3NZC5F7RKP) - [The Pigeonhole Principle](https://lightmysky.com/learn/mathematics/the-pigeonhole-principle-mt_wgfpmZqzd9) ## Opens up - [Recurrence Relations and Characteristic Roots](https://lightmysky.com/learn/mathematics/recurrence-relations-and-characteristic-roots-mt_q0b2bi0iAB)