COMP2121 Chap.6 Inclusion-Exclusion Counting
Inclusion-Exclusion Counting
Correcting an overcount
Adding the sizes of overlapping sets counts shared elements more than once. Inclusion-exclusion subtracts pairwise overlaps, adds back triple overlaps and continues with alternating signs.
For divisibility questions each intersection becomes a single floor division.
Counting by removing failures
When every requirement must hold, count the arrangements in which each requirement fails and subtract their union from the total.
This gives onto assignments, integer solutions with upper bounds and derangements, where nobody receives their own item.
A procedure for requirement problems
Start by naming the universal set and its size. Then write one bad set for each requirement, describe it in words, and compute the size of every intersection, usually by a symmetry that makes all intersections of the same size equal.
Combine with alternating signs and subtract from the total. The onto count, three to the five minus three times two to the five plus three, follows exactly this pattern for five items assigned to three boxes, giving 150.
Derangements and the limiting ratio
For n objects, the bad set for object i is the set of permutations that fix it, and an intersection of k such sets has n minus k factorial members.
The resulting alternating sum gives 1, 2, 9 and 44 derangements for two, three, four and five objects. Divided by n factorial, the proportion approaches one over e, about 0.368, so roughly a third of random permutations leave nothing in place.
What this chapter covers
- 01
Union of two sets
- 02
Union of three sets
- 03
General inclusion-exclusion
- 04
Onto assignments
- 05
Bounded integer solutions
- 06
Derangements
Worked example · free
Read a three-set Venn diagram by region
- 2Count each single set by floor division.
- 2Count the pairwise and triple intersections.
- 2Combine with alternating signs.
Key terms
- Inclusion-exclusion
- A counting rule that corrects overlaps in a union with alternating signs.
- Derangement
- A permutation in which no object stays in its original position.
Inclusion-Exclusion Counting FAQ
Why is the triple intersection added back?
An element in all three sets is counted three times by the single sets and removed three times by the pairwise overlaps, leaving it uncounted. Adding the triple intersection once restores it.
How do upper bounds fit into this chapter?
Treat each violated upper bound as a bad set. Shift the variable so its new lower bound is one more than the old upper bound, count with stars and bars, and combine the bad sets by inclusion-exclusion.
What is the derangement formula?
The number of arrangements of n objects with none in its own place is n factorial times the alternating sum of one over k factorial for k from 0 to n. For four objects it gives nine.
How do I check an inclusion-exclusion answer?
Fill a Venn diagram from the innermost region outward and confirm the regions add to the union, or list the elements for a smaller version of the problem. For derangements, the small values 1, 2 and 9 are easy to confirm by listing.
How many terms does the general formula have?
For n sets there is one term for every non-empty collection of the sets, so two to the n minus one terms in all. Symmetry usually collapses them: when every intersection of k sets has the same size, the k-fold terms combine into n choose k times that size.
Exam move
Draw the Venn diagram and fill region counts from the innermost region outwards, then check the formula agrees. For requirement problems, define one bad set per requirement in words before writing any number. Verify small cases by listing, such as the nine derangements of four objects. Practise one upper-bound problem per session and write each shifted variable explicitly before applying stars and bars.
Compare the inclusion-exclusion answer with a direct count whenever the numbers are small enough to list completely.
Working through Inclusion-Exclusion Counting in COMP2121? Sia is AskSia’s AI Computer Science tutor — ask any COMP2121 Inclusion-Exclusion Counting question and get a clear, step-by-step explanation grounded in how COMP2121 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.