MathCount with Proofs AwesomeMath Summer Program 2024
HANDOUT #4: Inclusion/Exclusion Principle
1 Principle of Inclusion and Exclusion (PIE)
A lot of the time what we’re asked to count is or can be expressed as the union of multiple sets. Note,
however, that we cannot simply add together the sizes of our sets to obtain the size of their union. That’s
where the Principle of Inclusion-Exclusion (PIE) comes in. For example, if we have two sets A and B and
want to find the size of A ∪ B, when we add |A| and |B| we end up counting each element in A ∩ B twice!
To adjust for this, we subtract off the size of that intersection to yield
|A ∪ B| = |A| + |B| − |A ∩ B|.
h
Okay that wasn’t so bad. But what happens when we have three sets instead of two? Things get more
complicated. As an example, suppose there are three different exams a student could sit for for a particular
at
math contest. We would like to know how many students participated in the contest total (i.e. how many
students took at least one exam).
Exam 1
1
2
1
2
2
1
eM
Let A be the set of students who took Exam 1, B be the set of
students who took Exam 2, and C be the set of students who
took Exam 3. We might start by looking at |A| + |B| + |C|.
What gets overcounted when we compute this sum? We can
use a Venn Diagram to help us figure this out, with the number
in a particular region representing how many times that region
has been counted.
om
Exam 2 Exam 3
So there’s definitely some overcounting going on. Let’s try what we did with two sets and subtract off |A∩B|.
Then we’ll subtract off |A ∩ C|, then |B ∩ C|. These are the Venn Diagrams representing the result after
each of those steps:
Exam 1 Exam 1 Exam 1
es
1 1 1
1 2 1 1 1 1
Aw
2 1 0
1 1 1 1 1 1
2 2 1
Exam 2 Exam 3 Exam 2 Exam 3 Exam 2 Exam 3
We’re close! Now we just have to add back in the intersection of all three sets and everything will have been
counted exactly once. In summary, we’ve discovered that
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
Huzzah! But... what about even more sets? Unfortunately there’s going to be even more adding and
subtracting to correct for under and overcounting. Fortunately there’s a pattern to how PIE works. To get
the size of the union of several sets:
1
MathCount with Proofs AwesomeMath Summer Program 2024
• Add the sizes of each single set.
• Subtract the sizes of all sets that are intersections of two of the original sets.
• Add back the sizes of all sets that are intersections of three of the original sets.
• Subtract the sizes of all sets that are intersections of four of the original sets.
• Etc.
We always add all of the intersections of any odd number of the original sets, and we always subtract off all
of the intersections of any even number of the original sets. We continue until we reach the intersection of
all the original sets. More formally, if we have n sets A1 , A2 , . . . , An then
h
n
X X X
|A1 ∪ A2 ∪ · · · ∪ An | = |Ai | − |Ai ∩ Aj | + |Ai ∩ Aj ∩ Ak | − · · · + (−1)n−1 |A1 ∩ · · · ∩ An |
i=1 i<j i<j<k
at
Example 1.1
How many positive integers less than 200 are multiples of either 5 or 11?
ANSWER: Let A be the set of
|A| + |B| − |A ∩ B| = 199
Example 1.2
5 + 199
11
multiples
− 5·11 = 39 + 18 − 3 = 54.
How many four-digit positive integers have two 1’s in a row?
eM
199 of 5 and B be the set of multiples of 11. We seek |A ∪ B| =
om
ANSWER: Let A be the set of four-digit numbers that begin with two 1’s, B be the set of four-digit
numbers with the two middle digits being 1, and C be the set of four-digit numbers that end with two 1’s. We
need to count A ∪ B ∪ C. Note that |A| = 100, |B| = 90, |C| = 90, |A ∩ B| = 10, |A ∩ C| = 1, |B ∩ C| = 9, and
|A∩B∩C| = 1. The Inclusion/Exclusion Principle then says |A∪B∪C| = (100+90+90)−(10+1+9)+1 = 261.
es
2 Derangement
A derangement of 1, 2, 3, . . . , n is any permutation of 1, 2, 3, . . . , n where no number is in its original position
(1 is not first, 2 is not second, and so on). The Inclusion/Exclusion Principle shows that the number of
Aw
n+1 n
derangements of 1, 2, 3, . . . , n is Dn = n! − n! 1 − 1
2! + 1
3! − · · · (−1)
n! = n! 1
2! − 1
3! + · · · (−1)
n! .
Example 2.1
How many permutations of ABCDE have none of A, C, or E in their original location?
ANSWER: Let R, S, and T be the sets of permutations where A, C, or E are in their original positions,
respectively. We want the permutations not in R∪S ∪T . Thus, |R∪S ∪T | = (4!+4!+4!)−(3!+3!+3!)+2! =
72 − 18 + 2 = 56. The number we want is therefore 5! − 56 = 120 − 56 = 64.
2
MathCount with Proofs AwesomeMath Summer Program 2024
3 Problem Set #4
1. Of the integers from 1 through 1000
A. How many are multiples of either 4 or 7?
B. How many are multiples of either 2 or 5 or 13?
2. Five people sit around a table. They get up to take a break. When they return, how many ways can
they be seated so that none of them sits in the same place that they were sitting before?
3. (2021 Purple Comet) At one school, 85 percent of the students are taking mathematics courses, 55
percent of the students are taking history courses, and 7 percent of the students are taking neither
h
mathematics nor history courses. Find the percent of the students who are taking both mathematics
and history courses.
at
4. (2021 AMC 12 B) At a math contest, 57 students are wearing blue shirts, and another 75 students are
wearing yellow shirts. The 132 students are assigned into 66 pairs. In exactly 23 of these pairs, both
students are wearing blue shirts. In how many pairs are both students wearing yellow shirts?
5. (2017 AIME II) Find the number of subsets of {1, 2, 3, 4, 5, 6, 7, 8} that are subsets of neither {1, 2, 3, 4, 5}
nor {4, 5, 6, 7, 8}.
eM
6. (2017 AMC 12 A) At a gathering of 30 people, there are 20 people who all know each other and 10
people who know no one. People who know each other hug, and people who do not know each other
shake hands. How many handshakes occur?
7. (2007 Purple Comet) The four sets A, B, C, and D each have 400 elements. The intersection of any
two of the sets has 115 elements. The intersection of any three of the sets has 53 elements. The
om
intersection of all four sets has 28 elements. How many elements are there in the union of the four
sets?
8. (2017 AIME I) Call a set S product-free if there do not exist a, b, c ∈ 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, 5, 6, 7, 8, 9, 10}.
es
9. (2017 Purple Comet) Eight red boxes and eight blue boxes are randomly placed in four stacks of four
boxes each. The probability that exactly one of the stacks consists of two red boxes and two blue boxes
is m
n , where m and n are relatively prime positive integers. Find m + n.
10. (2017 Purple Comet) Find the number of three-element subsets of {1, 2, 3, . . . , 13} that contain at least
Aw
one element that is a multiple of 2, at least one element that is a multiple of 3, and at least one element
that is a multiple of 5 such as {2, 3, 5} or {6, 10, 13}.
11. (2018 Purple Comet) Five girls and five boys randomly sit in ten seats that are equally spaced around a
circle. The probability that there is at least one diameter of the circle with two girls sitting on opposite
ends of the diameter is mn , where m and n are relatively prime positive integers. Find m + n.
12. (2019 Purple Comet) Find the number of positive integers less than 2019 that are neither multiples of
3 nor have any digits that are multiples of 3.
13. Permutations of Numbers
A. How many permutations of 1, 2, 3, . . . , 8 are there in which no even number is in its original
position?
B. How many permutations of 1, 2, 3, . . . , 9 are there in which exactly 5 numbers are in their original
position?
3
MathCount with Proofs AwesomeMath Summer Program 2024
C. How many permutations of 1, 2, 3, . . . , 10 are there in which at least one even number is in its
original position?
14. How many permutations are there of the letters AAABBBCCC
A. with no restrictions?
B. if no more than two A’s can appear together?
C. if no more than two A’s can appear together and no more than two B’s can appear together?
D. if no A’s can be adjacent and no more than two B’s can appear together?
E. if every B must be next to at least one A?
15. (2019 Purple Comet) A derangement of the letters ABCDEF is a permutation of these letters so that
h
no letter ends up in the position it began such as BDECFA. An inversion in a permutation is a pair of
letters xy where x appears before y in the original order of the letters, but y appears before x in the
permutation. For example, the derangement BDECFA has seven inversions: AB, AC, AD, AE, AF,
at
CD, and CE. Find the total number of inversions that appear in all the derangements of ABCDEF.
16. (2020 Purple Comet) Find the number of permutations of the letters ABCDE where the letters A and
B are not adjacent and the letters C and D are not adjacent. For example, count the permutations
ACBDE and DEBCA but not ABCED or EDCBA.
eM
17. (2020 Purple Comet) Find the number of permutations of the letters AAAABBBCC where no letter
is next to another letter of the same type. For example, count ABCABCABA and ABABCABCA but
not ABCCBABAA.
om
es
Aw
4
MathCount with Proofs AwesomeMath Summer Program 2024
4 Homework #4
1. (2022 Purple Comet) At Ignus School there are 425 students. Of these students 351 study mathematics,
71 study Latin, and 203 study chemistry. There are 199 students who study more than one of these
subjects, and 8 students who do not study any of these subjects. Find the number of students who
study all three of these subjects.
2. Let S = {1, 2, 3, . . . , n}. Find the number of ordered triples {A, B, C} of sets, where A, B, and C are
all subsets of S such that A ∩ B ̸= ∅, A ∩ C ̸= ∅, B ∩ C ̸= ∅, and A ∩ B ∩ C = ∅.
3. Prove that the number of onto functions f : X → Y where |X| = n and |Y | = m is given by
h
m m m
mn − (m − 1)n + (m − 2)n − · · · + (−1)m−1 1n .
1 2 m−1
at
eM
om
es
Aw
5
MathCount with Proofs AwesomeMath Summer Program 2024
PROBLEM SET #4 ANSWERS:
1. Of the integers from 1 through 1000
A. How many are multiples of either 4 or 7?
ANSWER: 250 + 142 − 35 = 357
B. How many are multiples of either 2 or 5 or 13?
ANSWER: (500 + 200 + 76) − (100 + 38 + 15) + 7 = 630
2. Five people sit around a table. They get up to take a break. When they return, how many ways can
they be seated so that none of them sits in the same place that they were sitting before?
ANSWER: D5 = 44
h
3. (2021 Purple Comet) At one school, 85 percent of the students are taking mathematics courses, 55
percent of the students are taking history courses, and 7 percent of the students are taking neither
mathematics nor history courses. Find the percent of the students who are taking both mathematics
at
and history courses.
ANSWER: 47
4. (2021 AMC 12 B) At a math contest, 57 students are wearing blue shirts, and another 75 students are
wearing yellow shirts. The 132 students are assigned into 66 pairs. In exactly 23 of these pairs, both
students are wearing blue shirts. In how many pairs are both students wearing yellow shirts?
ANSWER: 32
nor {4, 5, 6, 7, 8}.
ANSWER: 196
eM
5. (2017 AIME II) Find the number of subsets of {1, 2, 3, 4, 5, 6, 7, 8} that are subsets of neither {1, 2, 3, 4, 5}
6. (2017 AMC 12 A) At a gathering of 30 people, there are 20 people who all know each other and 10
people who know no one. People who know each other hug, and people who do not know each other
om
shake hands. How many handshakes occur?
ANSWER: 245
7. (2007 Purple Comet) The four sets A, B, C, and D each have 400 elements. The intersection of any
two of the sets has 115 elements. The intersection of any three of the sets has 53 elements. The
intersection of all four sets has 28 elements. How many elements are there in the union of the four
sets?
es
ANSWER: 1094
8. (2017 AIME I) Call a set S product-free if there do not exist a, b, c ∈ 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
Aw
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
ANSWER: 252
9. (2017 Purple Comet) Eight red boxes and eight blue boxes are randomly placed in four stacks of four
boxes each. The probability that exactly one of the stacks consists of two red boxes and two blue boxes
is m
n , where m and n are relatively prime positive integers. Find m + n.
ANSWER: 847
10. (2017 Purple Comet) Find the number of three-element subsets of {1, 2, 3, . . . , 13} that contain at least
one element that is a multiple of 2, at least one element that is a multiple of 3, and at least one element
that is a multiple of 5 such as {2, 3, 5} or {6, 10, 13}.
ANSWER: 63
11. (2018 Purple Comet) Five girls and five boys randomly sit in ten seats that are equally spaced around a
circle. The probability that there is at least one diameter of the circle with two girls sitting on opposite
ends of the diameter is mn , where m and n are relatively prime positive integers. Find m + n.
ANSWER: 118
6
MathCount with Proofs AwesomeMath Summer Program 2024
12. (2019 Purple Comet) Find the number of positive integers less than 2019 that are neither multiples of
3 nor have any digits that are multiples of 3. ANSWER: 321
13. Permutations of Numbers
A. How many permutations of 1, 2, 3, . . . , 8 are there in which no even number is in its original
position?
ANSWER: 8! − (4 · 7! − 6 · 6! + 4 · 5! − 4!) = 24,024
B. How many permutations of 1, 2, 3, . . . , 9 are there in which exactly 5 numbers are in their original
position?
ANSWER: 95 D4 = 1134
C. How many permutations of 1, 2, 3, . . . , 10 are there in which at least one even number is in its
h
original position?
ANSWER: 5 · 9! − 10 · 8! + 10 · 7! − 5 · 6! + 5! = 1,458,120
at
14. How many permutations are there of the letters AAABBBCCC
A. with no restrictions?
9
ANSWER: 3,3,3 = 1680
B. if no more than two A’s can
6appear together?
ANSWER: 1680 − 6+1
ANSWER: 1680 − 4+3
1
ANSWER: 1680 − 7 · 20 + 7 · 20 − 2 3+2
D. if no A’s can be adjacent and
3
6no more
3 − 3
2
eM
3 = 1680 − 140 = 1540
C. if no more than two A’s can appear together
and no more than two B’s can appear together?
than
2+3 4
1
= 1420
two B’s can appear together?
= 1680 − 660 = 1020
E. if every B must be next to at least one A?
ANSWER: There are 80 + 200 + 88 = 368 such permutations.
om
15. (2019 Purple Comet) A derangement of the letters ABCDEF is a permutation of these letters so that
no letter ends up in the position it began such as BDECFA. An inversion in a permutation is a pair of
letters xy where x appears before y in the original order of the letters, but y appears before x in the
permutation. For example, the derangement BDECFA has seven inversions: AB, AC, AD, AE, AF,
CD, and CE. Find the total number of inversions that appear in all the derangements of ABCDEF.
ANSWER: 2275
es
16. (2020 Purple Comet) Find the number of permutations of the letters ABCDE where the letters A and
B are not adjacent and the letters C and D are not adjacent. For example, count the permutations
ACBDE and DEBCA but not ABCED or EDCBA.
ANSWER: 48
Aw
17. (2020 Purple Comet) Find the number of permutations of the letters AAAABBBCC where no letter
is next to another letter of the same type. For example, count ABCABCABA and ABABCABCA but
not ABCCBABAA. ANSWER: 79
18. (2022 Purple Comet) At Ignus School there are 425 students. Of these students 351 study mathematics,
71 study Latin, and 203 study chemistry. There are 199 students who study more than one of these
subjects, and 8 students who do not study any of these subjects. Find the number of students who
study all three of these subjects.
ANSWER: 9
