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
Introduction to Psychology

Analyze this:
Our Intro to Psych Course is only $329.

Sophia college courses cost up to 80% less than traditional courses*. Start a free trial now.


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.