Combinatorics · Chapter 4

Principle of Inclusion and Exclusion

Count everything in A or B (or C, or more) without counting anything twice: add the sets, subtract the overlaps, add back, and pair it with complementary counting.

What's this chapter about?

4.0 Inclusion and Exclusion
4.1 Practice Problems

You'll need

open on YouTube

4.00%

Inclusion and Exclusion

In this section you will be able to count what is in at least one of several sets: add the sets, subtract the overlaps, add back, and keep alternating.

How many numbers from 1 to 100 are divisible by 2 or 7? There are 50 even numbers and 14 multiples of 7. But 64 is too many: 14, 28 and 42 are on both lists!

Adding the sizes of two sets counts their overlap twice. So subtract the overlap once. That is the principle of inclusion and exclusion, or PIE for short.

With three sets, an element in all three is added 3 times and subtracted 3 times. That leaves 0, so add it back once. With more sets, the signs keep alternating.

Look:PIE pairs well with complementary counting. When the bad cases are few, count them with PIE and subtract from the total.

Exploreplay first, formulas later

Try this: Press + |×2| and + |×7|. That is 50 + 14 = 64. Which numbers did you count twice?
Try this: Now press − |×2 ∩ ×7|. Is every region counted exactly once? Turn on Numbers to words and check the 57.
Try this: Open the 3-set card below and build its sum. Watch the center go +3, −3, +1.
Try this: In Example 4.9, which pairs of 2×2 blocks overlap in 2 squares, and which in only 1?

Name it

Definition 4.0.1 · Principle of Inclusion and Exclusion

The principle of inclusion and exclusion (PIE) is a counting technique that computes the number of elements that satisfy at least one of several properties, while making sure that elements satisfying more than one property are not counted twice.

Definition 4.0.2 · Union Symbol

$|A \cup B|$ is the number of elements of the union of $A$ and $B$ : everything that is in $A$ or in $B$ (or both). Duplicates are only written once.

Definition 4.0.3 · Intersection Symbol

$|A \cap B|$ is the number of elements of the intersection of $A$ and $B$ : only the elements that are in both sets.

Theorem 4.0.4 · 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 possibilities in the 2 "things" and subtract the duplicates.

Remark 4.0.5

When the number of cases that don't work is much less than the number of cases that do work, it often helps to use complementary counting together with PIE: count the bad cases with PIE, then subtract them from the total.

Subsets of {1, …, 10}: the bad ones contain every even number or every multiple of 3.

Theorem 4.0.6 · 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}

Count the possibilities in the 3 "things", subtract the duplicates in all 3 pairs of sets, then add back the elements that are in all 3 sets.

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

Theorem 4.0.7 · Principle of Inclusion Exclusion Generalized

If $A_1, A_2, \ldots, A_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|.

Add the singles, subtract the pairs, add the triples, and keep alternating.

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.

Watch itpredict, then reveal

Example 4.1

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

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

Predict first:
Your prediction

Example 4.2

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 $\dfrac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m + n$ .

1
What is the probability that the three letters form a palindrome?

Predict first:
Your prediction

open on YouTube

Example 4.3

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 we apply PIE here? Should we count the good subsets or the bad ones?

Predict first:
Click a choice or type its letter (A–E).

Example 4.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
There are 3 L's but only 2 O's. Each O has at most 2 neighbors. What does that force?

open on YouTube

Example 4.5

AIME

Let $S$ be a set with six elements. Let $\mathcal{P}$ be the set of all subsets of $S$ . Subsets $A$ and $B$ of $S$ , not necessarily distinct, are chosen independently and at random from $\mathcal{P}$ . The probability that $B$ is contained in one of $A$ or $S - A$ is $\dfrac{m}{n^r}$ , where $m$ , $n$ , and $r$ are positive integers, $n$ is prime, and $m$ and $n$ are relatively prime. Find $m + n + r$ . (The set $S - A$ is the set of all elements of $S$ which are not in $A$ .)

1
How many ways are there to choose $A$ and $B$ so that $B$ is contained entirely in $A$ ?

Predict first:
Your prediction

Example 4.6

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?

Predict first:
Your prediction

Example 4.7

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
Ignore the rule. In how many ways can 5 different awards go to 3 students?

Predict first:
Your prediction

open on YouTube

Example 4.8

Modified AIME

Call a set $S$ product-free if there do not exist $a, b, c \in S$ (not necessarily distinct) such that $ab = c$ . For example, the empty set and the set $\{16, 20\}$ are product-free, whereas the sets $\{4, 16\}$ and $\{2, 8, 16\}$ are not product-free. Find the number of product-free subsets of the set $\{1, 2, 3, 4, \ldots, 7, 8, 9\}$ .

1
Can 1 be in a product-free set?

Predict first:
Click a choice or type its letter (A–E).

open on YouTube

Example 4.9

AIME

Each unit square of a 3-by-3 unit-square grid is to be colored either blue or red. For each square, either color is equally likely to be used. The probability of obtaining a grid that does not have a red $2 \times 2$ square is $\dfrac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m + n$ .

9 free squares → 2⁹ = 512

PIE rounds for 4 sets
Round	Ways	Colorings	Total
+ singles	4	·	·
− pairs	6	·	·
+ triples	4	·	·
− quadruples	1	·	·

1
Should we count grids without a red $2 \times 2$ square directly?

Predict first:
Click a choice or type its letter (A–E).

Contest cornerreal contest problems

Problem 4.1.1

AIME

This problem also appears in the book as 4.2.

Problem 4.1.2

AMC 10

Seven distinct pieces of candy are to be distributed among three bags. The red bag and the blue bag must each receive at least one piece of candy; the white bag may remain empty. How many arrangements are possible?

Problem 4.1.3

AMC 10

In how many ways can the sequence $1, 2, 3, 4, 5$ be rearranged so that no three consecutive terms are increasing and no three consecutive terms are decreasing?

Problem 4.1.4

AMC 10

Ang, Ben, and Jasmin each have 5 blocks, colored red, blue, yellow, white, and green; and there are 5 empty boxes. Each of the people randomly and independently of the other two people places one of their blocks into each box. The probability that at least one box receives 3 blocks all of the same color is $\dfrac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. What is $m + n$ ?

Checkpoint for section 4.0

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

4.1

Practice Problems

In this section you will be able to use PIE on contest problems, from AMC 10 warm-ups to AIME challenges.

Time for the harder ones. Each problem hides a union you need to count, or the complement of one. Find the sets first, then let PIE do the work.

The last three problems are AIME challenges. Each 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 4.1.5

AMC 10

This problem also appears in the book as 4.1.3.

In how many ways can the sequence $1, 2, 3, 4, 5$ be rearranged so that no three consecutive terms are increasing and no three consecutive terms are decreasing?

Problem 4.1.6(additional)

AIME

Find the number of positive integers that are divisors of at least one of $10^{10}$ , $15^7$ , $18^{11}$ .

Problem 4.1.7(additional)

AIME

In a five-team tournament, each team plays one game with every other team. Each team has a $50\%$ chance of winning any game it plays. (There are no ties.) Let $\dfrac{m}{n}$ be the probability that the tournament will produce neither an undefeated team nor a winless team, where $m$ and $n$ are relatively prime integers. Find $m + n$ .

Problem 4.1.8(additional)

AIMEChallenge

Problem 4.1.9(additional)

AIMEChallenge

Define a regular $n$ -pointed star to be the union of $n$ line segments $P_1P_2, P_2P_3, \ldots, P_nP_1$ such that

the points $P_1, P_2, \ldots, P_n$ are coplanar and no three of them are collinear,
each of the $n$ line segments intersects at least one of the other line segments at a point other than an endpoint, all of the angles at $P_1, P_2, \ldots, P_n$ are congruent,
all of the $n$ line segments $P_1P_2, P_2P_3, \ldots, P_nP_1$ are congruent, and the path $P_1P_2, P_2P_3, \ldots, P_nP_1$ turns counterclockwise at an angle of less than 180 degrees at each vertex.

There are no regular 3-pointed, 4-pointed, or 6-pointed stars. All regular 5-pointed stars are similar, but there are two non-similar regular 7-pointed stars. How many non-similar regular 1000-pointed stars are there?

Problem 4.1.10(additional)

AIMEChallenge

While watching a show, Ayako, Billy, Carlos, Dahlia, Ehuang, and Frank sat in that order in a row of six chairs. During the break, they went to the kitchen for a snack. When they came back, they sat on those six chairs in such a way that if two of them sat next to each other before the break, then they did not sit next to each other after the break. Find the number of possible seating orders they could have chosen after the break.