The University of Hong Kong · FACULTY OF COMPUTER SCIENCE

COMP2121 Chap.6 Inclusion-Exclusion Counting

- one subject, every graph, every model, every mark
6 Chapters3-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 6 of 11 · COMP2121

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.

In this chapter

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

Q [6 marks]. This practice weighting was set for revision and is not an official University marking scheme. How many integers from 1 to 60 are divisible by 2, 3 or 5?
The integers from 1 to 60 sorted by divisibility by 2, 3 and 5.The integers from 1 to 60 sorted by divisibility by 2, 3 and 5. Each number in a region counts the integers lying in exactly those sets; the seven regions sum to 44, which is 30 + 20 + 12 − 10 − 6 − 4 + 2, and 16 integers lie outside all three.16848422multiples of 2multiples of 3multiples of 516 outside
The integers from 1 to 60 sorted by divisibility by 2, 3 and 5. Each number in a region counts the integers lying in exactly those sets; the seven regions sum to 44, which is 30 + 20 + 12 − 10 − 6 − 4 + 2, and 16 integers lie outside all three.
  • 2Count each single set by floor division.
  • 2Count the pairwise and triple intersections.
  • 2Combine with alternating signs.
The multiples of 2, 3 and 5 up to 60 number 30, 20 and 12. Multiples of 6, 10 and 15 number 10, 6 and 4, and multiples of 30 number 2. The union has 30 plus 20 plus 12 minus 10 minus 6 minus 4 plus 2, which is 44 integers, leaving 16 divisible by none of them.
Sia tip — An element in all three sets is added three times and subtracted three times, so add the triple overlap back.
Glossary

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.
FAQ

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.

Study strategy

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.

A+Everything unlocked
Unlocks this Bible + all 52 of your subjects at The University of Hong Kong, plus 1,000+ more Bibles across the AskSia library.
Sia - your COMP2121 tutor, unlimited, worked the way the exam marks it
The full 3-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works