The Inclusion-Exclusion Principle | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 8.13 Free with a free account

The Inclusion-Exclusion Principle

Discrete Mathematics · Chapter 8: Binomial Probability, Recurrence Relations, and Generating FunctionsSection 8.13 · lesson 58 of 878 min · free with a free account

← Introduction to Generating FunctionsNext lesson: Graphs: Vertices, Edges, and Basic Definitions →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Counting a union of overlapping conditions without double-counting.

  • State and prove inclusion-exclusion for 2 sets
  • Extend it to 3 or more sets
  • Apply it to filtering and divisibility problems
  • Contrast it with the addition rule of 5.2

Transcript

Everything said in the video, section by section (1,202 words). Read along, or search it.

Binomial Probability, Recurrence Relations, and Generating Functions

The Inclusion-Exclusion Principle

This section closes chapter eight with the inclusion-exclusion principle, a way to count the elements of a union when the sets overlap. We'll prove it for two sets and three, and extend it to any number. Then we'll apply it to real filtering and divisibility problems, and contrast it with the addition rule from section five point two.

The Opening Problem

Accounts With at Least 1 Method

A university I T department is auditing four thousand active student accounts, to plan a rollout of multi-factor authentication. One thousand eight hundred fifty accounts have the mobile app. One thousand two hundred have a registered hardware key. And four hundred thirty have both. A naive count of accounts with at least one method just adds, giving three thousand fifty. But that overstates the truth by exactly the accounts counted twice, the four hundred thirty with both. The correct count is three thousand fifty, minus four hundred thirty. That's two thousand six hundred twenty. That adjustment isn't a special trick. It's one instance of a general law, used by fraud systems flagging several risk criteria, database queries that union overlapping results, and search engines merging keyword matches.

Theorem 8.13.1

Inclusion-Exclusion for 2 Sets

Here's the law for two sets. The size of A union B is the size of A, plus the size of B, minus the size of A intersect B. Why the correction? Imagine listing every element of A, then every element of B. Anything in both gets written down twice. So the raw sum counts each element of the intersection twice instead of once. Subtracting the intersection removes exactly one extra count for each of them. Section five point two's addition rule is the special case where the sets are disjoint. Then the intersection is empty, and the correction is zero.

Worked Example 8.13.1

A Proof by Partition

Here's a proof. Partition A union B into three pieces that don't overlap. Elements only in A, elements only in B, and elements in both. Because the pieces are disjoint, the addition rule applies. The union's size is the sum of the three pieces. Now, A itself splits into A only, and the intersection. So the size of A only is the size of A, minus the intersection. The same goes for B. Substitute those in. The intersection is subtracted twice and added once, which leaves the size of A, plus the size of B, minus the intersection.

Theorem 8.13.2

3 Sets: Add Back the Triple Overlap

With three sets, there's a new wrinkle. Adding the three set sizes, then subtracting the three pairwise intersections, handles elements in one or two sets. But an element in all three gets subtracted one time too many. So a third correction adds back the triple intersection. The same alternating pattern extends to any number of sets. Add all the single sets, subtract all the pairwise intersections, and add all the triple ones. Then subtract the quadruple ones, and so on, alternating signs, down to the one intersection of every set.

Worked Example 8.13.2

Every Element Counted Exactly Once

Here's the proof for three sets. Fix any element x, and let k be the number of the three sets containing it. If k is zero, x is in nothing, so every term counts it zero times. Correct, since it's outside the union. If k is one, only one single-set term counts it. Total, one. If k is two, two single-set terms count it, and one pairwise term subtracts it. Two minus one is one. And if k is three, three single-set terms count it, all three pairwise terms subtract it, and the triple term adds it back. Three minus three plus one is one. Every element outside the union counts zero, and every element inside counts exactly once. So the formula gives the size of the union. The same tracking argument extends to more sets.

Figures 8.13.1 and 8.13.2

Reading the Regions

Venn diagrams make the counting visible, region by region. On the left is the account audit. One thousand four hundred twenty have only the app, four hundred thirty have both, and seven hundred seventy have only a key. That's two thousand six hundred twenty. And one thousand three hundred eighty have neither. On the right, three overlapping sets split into seven regions inside the union. These numbers come from the fraud example on the next slide. Their total is one thousand one hundred twenty-five.

Worked Example 8.13.3

Transactions Flagged for Review

A fraud pipeline flags a transaction for manual review if it meets any of three risk criteria, in a batch of ten thousand. Six hundred twenty are flagged for an unusual amount, four hundred ten for an unrecognized device, and two hundred seventy-five for a mismatched billing region. The logs also report ninety-five in the first two, sixty in the first and third, forty in the last two, and fifteen in all three. The question is how many satisfy at least one criterion. That's the union. By inclusion-exclusion, it's one thousand three hundred five, minus one hundred ninety-five, plus fifteen. One thousand one hundred twenty-five. So eight thousand eight hundred seventy-five passed all three checks. A single database query using OR counts the union directly. But separately counting each condition and adding them would overstate the total, by exactly the overlap terms.

Worked Example 8.13.4

Divisible by 2, 3 or 5

Now a divisibility problem. How many integers from one to three hundred are divisible by two, three, or five? The multiples of m in that range number three hundred over m, rounded down. So there are one hundred fifty multiples of two, one hundred of three, and sixty of five. An integer divisible by both two and three is divisible by their least common multiple, six. There are fifty of those. Likewise thirty multiples of ten, and twenty of fifteen. And divisible by all three means divisible by thirty. There are ten. So the union has three hundred ten, minus one hundred, plus ten. That's two hundred twenty. A one-line brute-force count confirms it. Checking a formula on a small case like this is a good habit, before trusting it on inputs too large to enumerate.

Table 8.13.1

Addition Rule or Inclusion-Exclusion?

The addition rule and inclusion-exclusion answer the same question, the size of a union. They're often confused. The addition rule requires disjoint sets. That's a necessary assumption, not an optional one. Inclusion-exclusion works for any finite sets. If the addition rule is misapplied to overlapping sets, it silently overstates the union by the size of the overlap, with no warning. Applying the inclusion-exclusion correction to disjoint sets is harmless. It just subtracts zero. So before adding two counts, ask whether the overlap is actually guaranteed to be empty, not merely plausible. Nothing stops a student from registering both an app and a key. Skipping the correction would overstate the count by exactly four hundred thirty.

Takeaways

Add, Subtract, Add Back

To summarize. For two sets, the union is A plus B minus the intersection. The subtraction removes exactly the double count. For three or more sets, the pattern becomes an alternating sum over every level of intersection. The addition rule is the special case for disjoint sets. And for divisibility, intersections become least common multiples. Here's something to think about. A student writes the three set sizes, subtracts the three pairwise intersections, and stops. They reason that every overlap has already been subtracted. Using the counting argument, explain precisely what's wrong. Which elements of the union end up miscounted if the final triple term is left out, and by how much is each one off?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About The Inclusion-Exclusion Principle

What is the inclusion-exclusion principle for two sets?
For two sets, |A \cup B| = |A| + |B| - |A \cap B|. Adding |A| and |B| counts every element of the intersection twice, so subtracting |A \cap B| removes exactly one extra count for each. Example: 1,850 app users plus 1,200 key users, minus 430 with both, gives 2,620 accounts with at least one method.
How do you extend inclusion-exclusion to three sets?
For three sets, add the single sets, subtract the pairwise intersections, then add back the triple intersection: |A\cup B\cup C| = |A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|. Signs keep alternating for more sets. The final term is needed because an element in all three sets would otherwise be counted 3-3=0 times.
How do you use inclusion-exclusion to count integers divisible by 2, 3, or 5?
Count multiples of each number, then use least common multiples for overlaps. From 1 to 300, there are 150, 100, and 60 multiples of 2, 3, and 5. Pairs use 6, 10, and 15, giving 50, 30, and 20. All three use 30, giving 10. So 310 - 100 + 10 = 220 integers are divisible by at least one.
What is the difference between the addition rule and inclusion-exclusion?
The addition rule only works for disjoint sets, while inclusion-exclusion works for any finite sets. If the sets overlap, simply adding their sizes overstates the union by the size of the overlap. Inclusion-exclusion corrects this, and when the sets are disjoint the intersection is empty, so the correction subtracts zero and the formula reduces to the addition rule.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →