Inclusion-Exclusion
Count a union by adding the parts, subtracting the pairwise overlaps, adding the triples back, and prove the alternating pattern is right.
What a learner can do afterwards
- 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
1 · Read
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.
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.
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.
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.
Add the parts, fix the overlaps with alternating signs, and check the fix on one element.
Lesson, questions and flashcards written for this dataset.
Readings and extra questions written for this dataset. Linked videos credited to Khan Academy: Two-way frequency tables and Venn diagrams, and Probability with Venn diagrams. Video licensing terms are unverified.
More to read
What each intersection includes
Let L = {1,3,6,8}, M = {2,3,6} and N = {3,5,8}. Their sizes add to 10. The pair intersections are L ∩ M = {3,6}, L ∩ N = {3,8} and M ∩ N = {3}. Their sizes add to 5. The triple intersection is {3}, so inclusion-exclusion gives 10 - 5 + 1 = 6. The union is {1,2,3,5,6,8}, which confirms the result.
Follow the number 3 through that calculation. It appears in three single sets and three pair intersections. Those contributions cancel. The triple term then contributes one copy.
An intersection includes every element satisfying its named memberships. L ∩ M includes 3 even though 3 also belongs to N. By contrast, 'L and M only' excludes N. Before using a pair-only count in the formula, add the count belonging to all three.
A cancellation proof for any finite family
Choose an element x in the union. Suppose it belongs to m sets. Each nonempty selection from these m sets produces an intersection containing x. Inclusion-exclusion adds its contribution for odd-sized selections and subtracts it for even-sized selections.
Choose one of the m sets, called T. Take any nonempty selection that omits T and pair it with the selection obtained by adding T. Both intersections contain x. The selection sizes differ by one, so one contribution is positive and the other negative. They cancel.
Every selection containing T and at least one other set has a partner obtained by removing T. The only unpaired selection is {T}. It contributes +1. Thus x contributes exactly one overall.
An element outside the union belongs to none of the intersections, so its contribution is zero. Adding these results over all elements proves that the alternating sum equals the union size. The argument covers every membership count, rather than checking only one example.
Counting outcomes that avoid every forbidden condition
Begin with a finite collection of possible outcomes. For each forbidden condition, form the set of outcomes satisfying that condition. Inclusion-exclusion counts their union: the outcomes breaking at least one requirement. Subtract that union from the full collection to count outcomes avoiding every forbidden condition.
For derangements of n distinct items, use one forbidden set for each matching position. Fixing k specified positions leaves (n-k)! permutations of the remaining items. Further positions may also be fixed. These intersection sizes are not counts with exactly k fixed points. Starting from n! and alternating subtraction and addition of the intersection sums removes every permutation with a fixed point.
For assignments of r >= 1 labelled tasks to n named people, use a forbidden set for each person receiving no task. There are n^r unrestricted assignments. If k specified people receive no task, each task has n-k possible recipients, giving (n-k)^r assignments. Removing the union of these forbidden sets leaves surjections, where every person receives at least one task.
The same union formula serves both problems, but the forbidden sets and their intersection counts differ.
Explore more
2 · Watch
به انگلیسیTake it off screen
Where it sits
Learn first
Optional connections
This opens up
14 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.