Combinatorics Principles: Inclusion-Exclusion

Combinatorics Principles: Inclusion-Exclusion

Author: c o

To introduce the principle of inclusion-exclusion
To provide examples of its application

In this packet, we are introduced to the combinatorial principle of inclusion-exclusion.

See More

Try Our College Algebra Course. For FREE.

Sophia’s self-paced online courses are a great way to save time and money as you earn credits eligible for transfer to over 2,000 colleges and universities.*

Begin Free Trial
No credit card required

28 Sophia partners guarantee credit transfer.

253 Institutions have accepted or given pre-approval for credit transfer.

* The American Council on Education's College Credit Recommendation Service (ACE Credit®) has evaluated and recommended college credit for 21 of Sophia’s online courses. More than 2,000 colleges and universities consider ACE CREDIT recommendations in determining the applicability to their course and degree programs.


Introduction And Background

Before beginning with this lesson, you should be familiar with the basics of set theory.


Lets say that you're at a party at which 9 people are attending, and you're wondering where people are going for spring break.  You know 4 people are going to Mexico and that 3 people are going home.  How many people, you wonder, aren't going anywhere?  

Your first intuition might be to say that 2 people must be remaining in their dorms for the week, since 4(to Mexico) + 3(going home) = 7 (people leaving) and 9 - 7 = 2.  

But then you remember that 1 person at the party is a Mexican student, and that she is going home.  Therefore, she is both going home and going to Mexico, that is, you accidentally counted her twice.  To correct this, you subtract her from the total count. So 4(to Mexico) + 3(going home) - 1(going home to Mexico) = 6, which makes 9-6 = 3 people at the party who wont be leaving for spring break.

The above example is an application of the principle of inclusion-exclusion:

If we have two sets A, B and we want to find the number of elements in the union of A and B, we must also know how many elements, if any, are in the intersection.

More generally: If we have a collection of sets, and we want to know how many elements are in the union of all of them, then we must know everything about how those sets intersect with one another.

See below for some examples.

Inclusion-Exclusion Principle

We see some examples of The Principle of Inclusion-Exclusion in the abstract, and we apply it to an example about voter satisfaction.