--- 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-11-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 For finite sets, the union contains everyone in at least one set. Adding two set sizes counts shared members twice, so subtract the intersection once. If 24 people walk, 18 cycle and 7 do both, their union has 24 + 18 - 7 = 35 people. Each shared person contributes 1 + 1 - 1 = 1. **Example.** For three sets, add their sizes, subtract all three pair intersections, then add the triple intersection. Pair counts include triple members. Add the triple count to an 'A and B only' count to get the full A ∩ B count. For sizes 16, 14 and 11, pair counts 6, 5 and 4, and triple count 1, the union has 41 - 15 + 1 = 27 members. *(drawing: A member of all three sets appears in three single sets and three pair intersections. The triple term restores its contribution to 1.)* For four sets, S1 is the sum of four set sizes, S2 the sum of six pair intersections, S3 the sum of four triple intersections and S4 the intersection size for all four. The union size is S1 - S2 + S3 - S4. All intersections include members also in further sets. For any finite family, continue with a plus sign for odd-sized groups of sets and a minus sign for even-sized groups. An element in m >= 1 sets appears in intersections from nonempty selections of those sets. Odd sizes have + signs; even sizes have - signs. Choose one set T. Pair each nonempty selection omitting T with the selection formed by adding T. Sizes differ by 1, so signs cancel. Removing T pairs every selection containing T except {T}, whose partner would be empty. Only {T} remains, contributing +1. Elements outside all sets contribute 0. Thus the sum counts the union. A permutation orders labelled items. There are n! orders, where n! = n × (n-1) × ... × 1. Use 0! = 1 for the one empty arrangement. For 6 items, 6! = 720. A fixed point puts an item in its matching position. Let Fi contain orders fixing position i. Fixing k specified positions leaves (n-k)! orders of the remaining items. Other positions may also be fixed. **Example.** Write an order by listing the item in each position. For letters 1 and 2 in matching envelopes 1 and 2, order 12 puts both letters in matching envelopes; order 21 puts neither there. Compare each entry with its position number. Reject an order if any entry matches. Listing all orders gives a direct check for small problems. To count derangements of n labelled items, start with n! orders. For each k, choose every group of k positions once. Fixing those positions leaves (n-k)! orders, including further fixed points. Subtract the sum for k=1, add it for k=2, and keep alternating through k=n. These sums count intersections, not orders with exactly k fixed points. This subtracts the union of forbidden fixed-point sets from all orders. A surjection assigns each labelled task to one named person and gives every person a task. For r >= 1 tasks and n people, n^r counts all assignments: n choices per task. Let each forbidden set mean one person gets no task. Missing k specified people leaves (n-k)^r assignments. Subtract their union from the total using alternating signs. For 3 tasks and 2 people, 2^3 - 2 × 1^3 + 0^3 = 6 assignments give both a task. **Recap.** Add the parts, fix the overlaps with alternating signs, and check the fix on one element. *Lesson, questions and flashcards written for this dataset.* ## Practice 14 questions on this page, each with its working shown. ## Needs first - [Counting with the Product and Sum Rules](https://lightmysky.com/learn/mathematics/counting-with-the-product-and-sum-rules-mt_3NZC5F7RKP) ## Optional connections - [Sets & Venn Diagrams](https://lightmysky.com/learn/mathematics/sets-and-venn-diagrams-mt_1YwOCMMwD8) - [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)