7. Principle of Inclusion Exclusion (PIE)

7.10%

PIE Strategies

In this section you will be able to see why adding two overlapping groups counts some things twice, and how to fix it.

Your teacher asks: “Who has a cat?” 12 hands go up. “Who has a dog?” 9 hands go up. Are there 21 pet owners? Not if some kids raised their hand twice!

Sometimes the easy way to count is to count too much, then fix it. Kids with a cat and a dog got counted twice, so you subtract them once.

Look:the trouble is always in the overlap. The over-count meter shows exactly which region is counted too many times.

Exploreplay first, formulas later

Try this: Press + |Cat| and then + |Dog|. Which region turns a darker colour? How many times is it counted?
Try this: Now press − |Cat ∩ Dog|. Is every region counted exactly once? What is the total?
Try this: Turn on Numbers to words. Read each line aloud. Which kids are in the middle?
Try this: Change |Cat ∩ Dog| to 0. What happens to the over-count meter, and why?

Name it

Definition 7.1.1 · Overcounting

Overcounting is the process of counting more than what you need and then systematically subtracting the parts which do not belong.

Definition 7.1.2 · Principle of Inclusion and Exclusion

The principle of inclusion and exclusion (PIE) is a counting technique that uses overcounting to compute the number of elements that satisfy at least one of several properties while guaranteeing that elements satisfying more than one property are not counted twice.

Try it

Problem 7.5.3

Out of 200 students, there are 100 taking Geometry, 70 taking Algebra, and 30 taking both. How many students are taking neither?

Checkpoint for section 7.1

Get 2 of 3 right to master this section. One try each, no hints.

7.20%

PIE for 2 Events

In this section you will be able to count things in A or B with |A ∪ B| = |A| + |B| − |A ∩ B|.

How many numbers from 1 to 100 can be split into equal groups of 2 or equal groups of 7? Adding 50 and 14 gives 64. But wait: 14, 28 and 42 are on both lists!

The union $A \cup B$ is everything in $A$ or $B$ . The intersection $A \cap B$ is everything in both. Adding $|A|$ and $|B|$ counts the intersection twice, so subtract it once.

When the “good” cases are many and the “bad” cases are few, count the bad ones with PIE and subtract from the total.

Exploreplay first, formulas later

Try this: Build the sum one term at a time. After the first two terms, how many numbers are counted twice?
Try this: Turn on Show the formula. Which term fixes the overlap?
Try this: Make |×7| equal to |×2 ∩ ×7|. Now every multiple of 7 is even. What does the diagram look like?
Try this: Turn on Numbers to words. How many numbers from 1 to 100 are neither?

Name it

Definition 7.2.1 · Union Symbol

$|A \cup B|$ is the union of elements in both $A$ and $B$ (i.e. all elements that are in set $A$ or set $B$ , but duplicates are only written once).

Definition 7.2.2 · Intersection Symbol

$|A \cap B|$ is the intersection of elements in both $A$ and $B$ (i.e. only those elements which are in both sets).

Theorem 7.2.3 · Principle of Inclusion Exclusion for 2 Sets

Given two sets, $|A_1|$ and $|A_2|$ ,

|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|.

Basically, we count the number of possibilities in 2 "things" and subtract the duplicates.

Remark 7.2.4

When the number of cases that don't work is much less than the number of cases that do work, it can often be helpful to use complementary counting along with PIE.

Watch itpredict, then reveal

Example 7.1

Find how many numbers from 1 to 100 (inclusive) that are divisible by 2 or 7.

1
How many numbers from 1 to 100 are divisible by 2?

Predict first:
Your prediction

Example 7.2

Omega Learn

How many subsets of the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ have at most 4 even numbers and at most 2 elements that are multiples of 3?

1
How can you apply the Principle of Inclusion and Exclusion to this problem?

Example 7.3

Omega Learn

Mark and George are playing a guessing game. George randomly chooses 2 numbers between 1 and 25. Mark then asks George if exactly 1 of the 2 numbers is divisible by 7. George, truthfully, answers yes. Mark then proceeds to guess 1 multiple of 7 and 1 number that is not a multiple of 7. What is the probability that Mark guesses at least 1 number correctly?

1
How many multiples of 7 are there from 1 to 25? How many numbers are not multiples of 7?

Predict first:
Your prediction

open on YouTube

Example 7.4

Omega Learn

How many different ways are there to arrange the letters in the word LOLLIPOP if each of the L's must be next to an O?

1
LOLLIPOP has 3 L's but only 2 O's. Each O has just 2 sides. What must happen to one of the O's?

open on YouTube

Try it

Problem 7.5.1

How many positive numbers less than or equal to 100 are multiples of 2 or 3?

Problem 7.5.2

How many positive numbers less than or equal to 100 are NOT multiples of 2 or 3?

Problem 7.5.5

In a town of 351 adults, every adult owns a car, motorcycle, or both. If 331 adults own cars and 45 adults own motorcycles, how many of the car owners do not own a motorcycle?

Problem 7.5.7

How many positive numbers less than or equal to 200 are multiples of 2 and 3 but not a multiple of 5?

Contest cornerreal contest problems

Problem 7.5.4

AMC 8

Sets $A$ and $B$ , shown in the Venn diagram, have the same number of elements. Their union has 2007 elements and their intersection has 1001 elements. Find the number of elements in $A$ .

Problem 7.5.6

AMC 8

At Euler Middle School, 198 students voted on two issues in a school referendum with the following results: 149 voted in favor of the first issue and 119 voted in favor of the second issue. If there were exactly 29 students who voted against both issues, how many students voted in favor of both issues?

Checkpoint for section 7.2

Get 2 of 3 right to master this section. One try each, no hints.

7.30%

PIE for 3 Events

In this section you will be able to count things in A, B or C: add the singles, subtract the pairs, add back the triple.

Your school has art, band and chess clubs. Some students are in two clubs. A few are in all three! How do you count each student exactly once?

With three circles, the middle gets messy. A student in all three clubs is added 3 times, then subtracted 3 times. That leaves 0, so you add them back once.

Look:the signs take turns: plus the singles, minus the pairs, plus the triple.

Exploreplay first, formulas later

Build the sum →

Over-count meter: times each region is counted

Art onlynot counted yet
Band onlynot counted yet
Chess onlynot counted yet
Art and Band onlynot counted yet
Art and Chess onlynot counted yet
Band and Chess onlynot counted yet
all threenot counted yet

|Art|10

|Band|9

|Chess|8

|Art ∩ Band|4

|Art ∩ Chess|3

|Band ∩ Chess|3

|Art ∩ Band ∩ Chess|1

everything25

Try this: Add the three singles. Watch the centre of the meter. How many times is a student in all three clubs counted?
Try this: Subtract the three pairs. What happened to the centre? Is it counted at all now?
Try this: Press + for the last term. Is every region now counted exactly once?
Try this: Turn on Numbers to words. How many students are in no club at all? Check it with the box total.

Name it

Theorem 7.3.1 · Principle of Inclusion Exclusion for 3 Sets

Given three sets, $|A_1|, |A_2|, |A_3|$ ,

\begin{aligned}|A_1 \cup A_2 \cup A_3| = {} & |A_1| + |A_2| + |A_3| \\ & - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| \\ & + |A_1 \cap A_2 \cap A_3|.\end{aligned}

In this formula, we count the number of possibilities in 3 "things", subtract the possibilities that are duplicates in all 3 pairs of sets, and add back the number of duplicates that are in all 3 sets.

Watch itpredict, then reveal

Example 7.5

How many numbers less than or equal to 193 are multiples of 2, 3, or 5?

1
How many numbers up to 193 are divisible by 2? By 3? By 5?

Predict first:
Your prediction: by 2Your prediction: by 3Your prediction: by 5

Example 7.6

AMC 8

Five different awards are to be given to three students. Each student will receive at least one award. In how many different ways can the awards be distributed?

1
Forget the rule for a moment. Each award can go to any of the 3 students. How many ways?

Predict first:
Your prediction

open on YouTube

Contest cornerreal contest problems

Problem 7.5.8

AMC 8

Mrs. Sanders has three grandchildren, who call her regularly. One calls her every three days, one calls her every four days, and one calls her every five days. All three called her on December 31, 2016. On how many days during the next year did she not receive a phone call from any of her grandchildren?

Problem 7.5.9

AMC 10

Alice refuses to sit next to either Bob or Carla. Derek refuses to sit next to Eric. How many ways are there for the five of them to sit in a row of 5 chairs under these conditions?

Problem 7.5.11(additional)

AMC 10

There are 20 students participating in an after-school program offering classes in yoga, bridge, and painting. Each student must take at least one of these three classes, but may take two or all three. There are 10 students taking yoga, 13 taking bridge, and 9 taking painting. There are 9 students taking at least two classes. How many students are taking all three classes?

Problem 7.5.13(additional)

AMC 12

Call a number prime-looking if it is composite but not divisible by 2, 3, or 5. The three smallest prime-looking numbers are 49, 77, and 91. There are 168 prime numbers less than 1000. How many prime-looking numbers are there less than 1000?

Checkpoint for section 7.3

Get 2 of 3 right to master this section. One try each, no hints.

7.40%

PIE for any Number of Events (Optional)

In this section you will be able to see the pattern behind PIE for any number of sets (optional).

What if there are 4 overlapping groups? Or 10? You can’t draw that Venn diagram nicely. But the pattern keeps going!

Add every single set, subtract every pair, add every triple, subtract every quadruple, and so on. The signs take turns until you reach the term with all the sets.

The star in the widget is one element. However many sets it is in, the rounds always count it exactly once in the end.

Exploreplay first, formulas later

sets4

element is in3

PIE rounds for 4 sets
Round	Sign	Terms	★ in	★ count
singles	+	4	·	·
pairs	−	6	·	·
triples	+	4	·	·
quadruples	−	1	·	·

★ counted 0×

4 sets give 15 terms in all. Change “element is in”: after the last round the count is always exactly 1.

Try this: Press the big button round by round. How many times is the star counted after each round?
Try this: Change "element is in" to 1, 2, 3 and 4. Does the final count always come out to 1?
Try this: Set 5 sets. Is the last round added or subtracted? Why?

Name it

Concept 7.4.1 · PIE Generalization

The same principle applies when counting more than 3 events. For any $n$ events, to find the total number of ways such that any of the events occur:

Find the number of ways each individual event occurs in.
For every pair of 2 events, subtract the number of ways where both of them occur.
For every triplet of 3 events, add back the number of ways where all 3 of them occur.
For every quadruplet of 4 events, subtract the number of ways where all 4 occur …
For all $n$ events, add (if $n$ is odd) or subtract (if $n$ is even) the number of ways where all of them occur.

Alternate between adding the number of ways and subtracting the number of ways until you reach the case where all $n$ events occur. Whether you add or subtract the number of ways where all $n$ events occur depends on whether $n$ is odd, since we alternate between adding and subtracting.

Theorem 7.4.2 · Principle of Inclusion Exclusion Generalized Formula

Stated more formally, if $(A_i)_{1 \le i \le n}$ are finite sets, then:

\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{i=1}^{n} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n-1} |A_1 \cap \cdots \cap A_n|.

Contest cornerreal contest problems

Problem 7.5.12(additional)

BmMT

Students are being assigned to faculty mentors in the Berkeley Math Department. If there are 7 distinct students and 3 distinct mentors, and each student has exactly one mentor, in how many ways can students be assigned to mentors such that each mentor has at least one student?

Problem 7.5.14(additional)

MATHCOUNTS

How many different subsets of $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}$ contain at least one element in common with each of the sets $\{2, 4, 6, 8, 10, 12\}$ , $\{3, 6, 9, 12\}$ and $\{2, 3, 5, 7, 11\}$ ?

Checkpoint for section 7.4

Get 2 of 3 right to master this section. One try each, no hints.

7.5

Practice Problems

In this section you will be able to mix two-set and three-set PIE on contest problems.

Time for a tough one from the AIME! Look for the two events, find each chance, and subtract the overlap. Every problem has three hints if you get stuck.

Want every problem from this chapter on one page? Open the problem set.

Contest cornerreal contest problems

Problem 7.5.10

AIME

Many states use a sequence of three letters followed by a sequence of three digits as their standard license-plate pattern. Given that each three-letter three-digit arrangement is equally likely, the probability that such a license plate will contain at least one palindrome (a three-letter arrangement or a three-digit arrangement that reads the same left to right as it does right to left) is $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m+n$ .