Overcounting (PIE)

MathDash
Last updated 2025-07-01

1 Introduction: Venn Diagrams

s h
Let’s start with a simple problem that illustrates why we need a systematic way to count

y
l
overlapping groups:

Example 1.1

D a n
There are 30 people in a class. 10 like biking, 15 like swimming, and 6 like both biking

h O
and swimming. How many people like neither biking nor swimming?

a t e
Let’s visualize this with a Venn diagram. A Venn diagram uses circles to show how dif-

s
ferent groups overlap:

M U
Biking Swimming

y
B rna l b m s
Total students = 30
Biking = 10
Swimming = 15

e
Both = 6

t
In x (neither biking
nor swimming)

Let’s understand what each part of this diagram means:

• The blue circle contains everyone who likes biking (10 people total)

• The red circle contains everyone who likes swimming (15 people total)

• Where the circles overlap (purple region marked ’m’) shows people who like both
activities (6 people)

• The region marked ’b’ shows people who only like biking

1
MathDash (Last updated 2025-07-01) Overcounting (PIE)

• The region marked ’s’ shows people who only like swimming

• The region marked ’x’ (the outside of the diagram!) shows people who like neither
activity

Again, think of it like sorting students into rooms:

• If you like both activities, you go to the middle room (’m’)

• If you only like biking, you go to the left room (’b’)

• If you only like swimming, you go to the right room (’s’)

• If you like neither, you wait outside (’x’)

Now let’s fill this in step by step:

h
1. We know 6 people like both activities:

s
Biking Swimming

a ly
D n
Total students = 30

h O
Biking = 10

t
s Swimming = 15
b 6

a e
Both = 6

M U s
y
B rna l x (neither biking
nor swimming)

e
2. We know 10 people like biking in total, so:

t
𝑏 + 6 = 10 =⇒ 𝑏 = 4 people like only biking

In
3. Similarly, 15 people like swimming in total:

𝑠 + 6 = 15 =⇒ 𝑠 = 9 people like only swimming

2
MathDash (Last updated 2025-07-01) Overcounting (PIE)

Biking Swimming

Total students = 30
Biking = 10
Swimming = 15
4 6 9
Both = 6

h
x (neither biking

s
nor swimming)

a ly
4. Finally, for those who like neither:

D n
𝑥 + 𝑏 + 𝑠 + 𝑚 = 30 =⇒ 𝑥 = 30 − 4 − 9 − 6 = 11

t h O
Here’s our completed diagram:

a e
Biking Swimming

M U s Total students = 30

y l
Biking = 10

B rna
Swimming = 15
4 6 9
Both = 6

te
In
11 (neither biking
nor swimming)

2 Three Overlapping Sets

Let’s try a more complex example:

Example 2.1
In a school of 200 students:

• 80 play basketball

• 120 play soccer

3
MathDash (Last updated 2025-07-01) Overcounting (PIE)

• 60 play tennis

• 40 play basketball and soccer

• 25 play basketball and tennis

• 30 play soccer and tennis

• 15 play all three sports

How many students play no sports at all?

This needs a three-circle Venn diagram.

Basketball Soccer

s h y
m

a l
b s Basketball = 80
Soccer = 120

D n
c Tennis = 60

h O
p q B & S = 40

t
B & T = 25

a e
S & T = 30

s
r All three = 15
x = plays

M U
no sports

y
B rna l Tennis
Let’s understand what each part of this diagram means:

e
• The blue circle contains everyone who plays basketball (80 students total)

t
• The red circle contains everyone who plays soccer (120 students total)

In
• The green circle contains everyone who plays tennis (60 students total)

• The region marked ’c’ shows students who play all three sports

• The region marked ’m’ shows students who play only basketball and soccer

• The region marked ’p’ shows students who play only basketball and tennis

• The region marked ’q’ shows students who play only soccer and tennis

• The region marked ’b’ shows students who play only basketball

• The region marked ’s’ shows students who play only soccer

• The region marked ’r’ shows students who play only tennis

• The region marked ’x’ (outside the circles) shows students who play no sports

Think of it like sorting students into rooms:

4
MathDash (Last updated 2025-07-01) Overcounting (PIE)

• If you play all three sports, you go to the center room (’c’)

• If you play exactly two sports, you go to one of the overlap rooms (’m’, ’p’, or ’q’)

• If you play exactly one sport, you go to one of the outer rooms (’b’, ’s’, or ’r’)

• If you play no sports, you wait outside (’x’)

Now let’s fill this in step by step:

1. We know 15 students play all three sports, so we fill in region ’c’ with 15:

Basketball Soccer

h
m

s
b s Basketball = 80

y
Soccer = 120

a l
15 Tennis = 60

D n
p q B & S = 40
B & T = 25

t h O
S & T = 30
r All three = 15

a e
x = plays

s
no sports

y M l U Tennis

B rna
2. Now let’s fill in the two-sport overlaps:

• For basketball and soccer (m): 40 total - 15 in center = 25 play just these two

• For basketball and tennis (p): 25 total - 15 in center = 10 play just these two

te
• For soccer and tennis (q): 30 total - 15 in center = 15 play just these two

In

5
MathDash (Last updated 2025-07-01) Overcounting (PIE)

Basketball Soccer

25
b s Basketball = 80
Soccer = 120
15 Tennis = 60

10 15 B & S = 40
B & T = 25
S & T = 30
r All three = 15
x = plays

h
no sports

a s ly Tennis

D n
3. Now we can find students who play only one sport:

h O
t
• Basketball only (b): 80 total - 25 (with soccer) - 10 (with tennis) - 15 (all three) = 30

a e
• Soccer only (s): 120 total - 25 (with basketball) - 15 (with tennis) - 15 (all three) = 65

s
• Tennis only (r): 60 total - 10 (with basketball) - 15 (with soccer) - 15 (all three) = 20

M U
Basketball Soccer

y
B rna l 30
25
65 Basketball = 80

e
Soccer = 120

t
15 Tennis = 60

In
10 15 B & S = 40
B & T = 25
S & T = 30
20 All three = 15
x = plays
no sports

Tennis
4. Finally, let’s count those who play no sports:

• Total students playing at least one sport = 30 (b) + 65 (s) + 20 (r) + 25 (m) + 10 (p) +
15 (q) + 15 (c) = 180

• Therefore, 240 - 180 = 60 students play no sports

6
MathDash (Last updated 2025-07-01) Overcounting (PIE)

Basketball Soccer

25
30 65 Basketball = 80
Soccer = 120
15 Tennis = 60

10 15 B & S = 40
B & T = 25
S & T = 30
20 All three = 15
60 = plays

h
no sports

a s ly Tennis

hD O n
t
3 The Principle of Inclusion-Exclusion (PIE)

a s e
Let’s formalize what we just did with the Venn diagrams. We’ll use some standard set
notation:

y M l U
• |𝐴| means ”number of elements in set A”

• 𝐴 ∪ 𝐵 means ”elements in A OR B (or both)”

B rna
• 𝐴 ∩ 𝐵 means ”elements in A AND B”

Theorem 3.1 (Two-Set PIE)

e
For any two finite sets A and B:

t
|𝐴 ∪ 𝐵| = |𝐴| + |𝐵| − |𝐴 ∩ 𝐵|

In
In words: The size of the union of two sets equals the sum of their individual sizes,
minus the size of their intersection.

In simpler words: To count how many items are in either group A or group B (or
both), add up the number of items in A and the number in B, then subtract the num-
ber that appear in both groups (to avoid counting them twice).

This makes sense from our Venn diagram! If we just add |𝐴| and |𝐵| , we count the overlap
twice, so we need to subtract it once:

7
MathDash (Last updated 2025-07-01) Overcounting (PIE)

|𝐴| |𝐵|

|𝐴 ∩ 𝐵|

Theorem 3.2 (Three-Set PIE)

h
For any three finite sets A, B, and C:

a s ly
|𝐴 ∪ 𝐵 ∪ 𝐶| = |𝐴| + |𝐵| + |𝐶| − |𝐴 ∩ 𝐵| − |𝐵 ∩ 𝐶| − |𝐴 ∩ 𝐶| + |𝐴 ∩ 𝐵 ∩ 𝐶|

D n
In words: The size of the union of three sets equals:

h O
• The sum of the sizes of each individual set

t e
• Minus the sizes of each pair of overlapping sets

a s
• Plus the size of the region where all three sets overlap

M U
In simpler words: To count how many items are in any of groups A, B, or C:

l
• Add up the number of items in each group

y
B rna
• Subtract the number of items that appear in each pair of groups (to avoid
counting them twice)

• Add back the number of items that appear in all three groups (because we
subtracted them too many times)

te
Again, this matches our three-circle Venn diagram! We:

In
• Add each individual set

• Subtract each pair of overlaps (which we counted twice)

• Add back the triple overlap (which we subtracted too many times)

This pattern continues. For four sets:

Theorem 3.3 (Four-Set PIE)

For finite sets A, B, C, and D:

|𝐴 ∪ 𝐵 ∪ 𝐶 ∪ 𝐷| =|𝐴| + |𝐵| + |𝐶| + |𝐷|

− |𝐴 ∩ 𝐵| − |𝐴 ∩ 𝐶| − |𝐴 ∩ 𝐷| − |𝐵 ∩ 𝐶| − |𝐵 ∩ 𝐷| − |𝐶 ∩ 𝐷|
+ |𝐴 ∩ 𝐵 ∩ 𝐶| + |𝐴 ∩ 𝐵 ∩ 𝐷| + |𝐴 ∩ 𝐶 ∩ 𝐷| + |𝐵 ∩ 𝐶 ∩ 𝐷|
− |𝐴 ∩ 𝐵 ∩ 𝐶 ∩ 𝐷|

8
MathDash (Last updated 2025-07-01) Overcounting (PIE)

Theorem 3.4 (General PIE)

To find the total number of things that appear in at least one group:

• Add up the sizes of each individual set

• Subtract the sizes of each pair of overlapping sets

• Add the sizes of each triple overlap

• Subtract the sizes of each quadruple overlap

• Keep alternating between adding and subtracting until you’ve considered all
possible overlaps

Or in everyday terms:

h
• Add up the number of things in each group

s
• Subtract things counted twice (in two groups)

a ly
• Add back things counted three times (in three groups)

D n
• Subtract things counted four times (in four groups)

h O
• Keep going until you’ve considered all possible combinations

t
Or in mathematical notation, for n finite sets 𝐴1 , 𝐴2 , ..., 𝐴𝑛 :

a s e
𝑛
Ø 𝑛
∑︁ ∑︁
𝐴𝑖 = (−1) 𝑘+1 |𝐴𝑖1 ∩ ... ∩ 𝐴𝑖𝑘 |

M U
𝑖=1 𝑘=1 1 ≤𝑖1 <...<𝑖𝑘 ≤𝑛

y l
The proof of this general formula involves drawing Venn diagrams in higher dimensions

B rna
and using mathematical induction. The key insight is that each element gets counted
exactly once after all the additions and subtractions.

e
4 Derangements: A Classic PIE Application

t
In
Here’s a fascinating application of PIE that might seem unrelated at first:

Example 4.1
A teacher has 6 tests to return to 6 students. If each test is randomly given back,
what’s the probability that no student receives their own test? (Such a permutation
where no element is in its original position is called a derangement.)

Let’s solve this step by step:

1) First, let’s understand what we’re counting:

• Total possible ways to return tests: 6! = 720 (any permutation)

• We want permutations where no test goes to its owner

• This is tricky to count directly, so let’s use PIE!

2) Let’s use complementary counting:

9
MathDash (Last updated 2025-07-01) Overcounting (PIE)

• Instead of counting arrangements where no test is correct...

• We’ll count arrangements where at least one test is correct

• Then subtract from total arrangements (6!)

3) Let’s define our events carefully:

• Let 𝐴1 = ”Student 1 gets their own test”

• Let 𝐴2 = ”Student 2 gets their own test”

• And so on through 𝐴6

4) Now let’s count each type of overlap:

Single events ( |𝐴𝑖 | ):

h
• If Student 1 gets their correct test, that position is fixed

s y
• The other 5 tests can be arranged in 5! ways

a l
• So |𝐴1 | = |𝐴2 | = ... = |𝐴6 | = 5!

D n
6

• There are 1
= 6 such events

h O
Pairs of events ( |𝐴𝑖 ∩ 𝐴 𝑗 | ):

t e
• If Students 1 and 2 both get correct tests, two positions are fixed

a s
• The other 4 tests can be arranged in 4! ways

M U
• So |𝐴1 ∩ 𝐴2 | = |𝐴1 ∩ 𝐴3 | = ... = 4! = 24

l
6

• There are = 15 such pairs

y
2

B rna
Triples ( |𝐴𝑖 ∩ 𝐴 𝑗 ∩ 𝐴𝑘 | ):

• Three students get correct tests, three positions fixed

• The other 3 tests can be arranged in 3! ways

e
6

• There are = 20 such triples

t
3

Quadruples ( |𝐴𝑖 ∩ 𝐴 𝑗 ∩ 𝐴𝑘 ∩ 𝐴𝑙 | ):

In
• Four students get correct tests, four positions fixed

• The other 2 tests can be arranged in 2! ways

6

• There are 4
= 15 such quadruples
Quintuples ( |𝐴𝑖 ∩ 𝐴 𝑗 ∩ 𝐴𝑘 ∩ 𝐴𝑙 ∩ 𝐴𝑚 | ):

• Five students get correct tests, five positions fixed

• The last test can be arranged in 1! way

6

• There are 5
= 6 such quintuples
All six ( |𝐴1 ∩ 𝐴2 ∩ 𝐴3 ∩ 𝐴4 ∩ 𝐴5 ∩ 𝐴6 | ):

• All six students get correct tests, all positions fixed

• No tests left to arrange: 0! = 1 way

10
MathDash (Last updated 2025-07-01) Overcounting (PIE)

6

• There is 6
= 1 such arrangement
5) Let’s apply PIE using our everyday explanation:

• First, add up arrangements where each test is correct individually:

6
 
6 tests × 5! ways = 5!
1

• Subtract arrangements where tests were counted twice (two correct tests):

6
 
15 pairs of tests × 4! ways = 4!
2

h
• Add back arrangements counted three times (three correct tests):

s y
6
 
20 triples of tests × 3! ways = 3!

a l
3

D n
• Subtract arrangements counted four times (four correct tests):

t h O
6
 
15 quadruples of tests × 2! ways = 2!

e
4

a s
• Add back arrangements counted five times (five correct tests):

M U
6
 

l
6 quintuples of tests × 1! ways = 1!

y
5

B rna
• Subtract arrangements counted six times (all tests correct):

6
 
1 way to pick all tests × 0! ways = 0!

e
6

t
This gives us our formula:

In
6 6 6 6 6 6
           
5! − 4! + 3! − 2! + 1! − 0!
1 2 3 4 5 6

6) Therefore:

• Arrangements with at least one correct = 720 - 360 + 120 - 30 + 6 - 1 = 455

• Arrangements with no correct tests = 720 - 455 = 265

265
• Probability = 720
≈ 0.368
This means about 37% of random returns will result in no student getting their own test!

Visual Aid: Think of it like this:

• First we counted all ways (6!)

• Then we removed arrangements where Student 1 got their test

11
MathDash (Last updated 2025-07-01) Overcounting (PIE)

• And where Student 2 got their test

• But wait! We removed arrangements where both 1 AND 2 got their tests twice, so
add those back

• Then we removed arrangements where 1 AND 2 AND 3 all got their tests three
times, so subtract those

• And so on, following the PIE pattern we learned

5 Practice Problems
Problem 1. A class has 40 students. 20 play basketball, 25 play soccer, and 15 play tennis.
12 play basketball and soccer, 8 play basketball and tennis, 10 play soccer and tennis,

h
and 5 play all three sports. How many students play no sports at all?

a s ly
Problem 2. In a club of 50 members, 25 play chess and 30 play cards. If 8 members play
neither game, how many members play both chess and cards?

hD n
Problem 3. In a school of 300 students, 100 take French, 150 take Spanish, and 80 take

O
t
German. 40 take French and Spanish, 30 take French and German, 45 take Spanish and
German, and 20 take all three languages. How many students take no language classes?

a s e
Problem 4. A professor has 5 tests to return to 5 students. If each test is randomly given

M U
back, what’s the probability that no student receives their own test?

y
B rna l
te
In

12
MathDash (Last updated 2025-07-01) Overcounting (PIE)

6 Solutions to Practice Problems

Problem 1. A class has 40 students. 20 play basketball, 25 play soccer, and 15 play tennis.
12 play basketball and soccer, 8 play basketball and tennis, 10 play soccer and tennis,
and 5 play all three sports. How many students play no sports at all?

Solution: Let’s solve this step by step using PIE:

1) First, let’s count students who play at least one sport:

• Add individual sports: 20 + 25 + 15 = 60

• Subtract double-counted pairs: -12 - 8 - 10 = -30

• Add back triple-counted overlaps: +5

h
• Total: 60 - 30 + 5 = 35 students play at least one sport

s y
2) Therefore:

a l
40 − 35 = 5 students play no sports

D n
Problem 2. In a club of 50 members, 25 play chess and 30 play cards. If 8 members play

h O
neither game, how many members play both chess and cards?

t e
Solution: Let’s solve this step by step using PIE:

a s
1) Let’s define what we know:

M U
• Total members: 50

l
• Chess players: 25

y
B rna
• Card players: 30

• Play neither: 8

• Let x = number who play both

e
2) Using PIE:

t
• Members who play at least one game = Total - Neither

In
• 50 - 8 = 42 play at least one game

• By PIE: | Chess ∪ Cards | = | Chess | + | Cards | - | Chess ∩ Cards |

• 42 = 25 + 30 - x

• 42 = 55 - x

• x = 13

Therefore, 13 members play both chess and cards.

To verify:

• Chess only: 25 - 13 = 12 members

• Cards only: 30 - 13 = 17 members

• Both: 13 members

13
MathDash (Last updated 2025-07-01) Overcounting (PIE)

• Neither: 8 members

• Total: 12 + 17 + 13 + 8 = 50 members

Problem 3. In a school of 300 students, 100 take French, 150 take Spanish, and 80 take
German. 40 take French and Spanish, 30 take French and German, 45 take Spanish and
German, and 20 take all three languages. How many students take no language classes?

Solution: Let’s solve this step by step using PIE:

1) First, let’s count students who take at least one language:

• Add individual languages: 100 + 150 + 80 = 330

• Subtract double-counted pairs: -40 - 30 - 45 = -115

h
• Add back triple-counted overlaps: +20

s y
• Total: 330 - 115 + 20 = 235 students take at least one language

a l
2) Therefore:

D n
300 − 235 = 65 students take no language classes

h O
Problem 4. A professor has 5 tests to return to 5 students. If each test is randomly given

t
back, what’s the probability that no student receives their own test?

a s e
Solution: Let’s solve using PIE:

M U
1) Total possible arrangements: 5! = 120

y l
2) Count arrangements with at least one correct test:

B rna
5

• Single correct: 1
4! = 5 × 24 = 120
5

• Pairs correct: 2
3! = 10 × 6 = 60
5

• Triples correct: 2!
= 10 × 2 = 20

e
3

t
• Quadruples correct: 54 1! = 5 × 1 = 5

In
• All correct: 55 0! = 1 × 1 = 1

3) Apply PIE:
120 − 60 + 20 − 5 + 1 = 76

4) Therefore:

• Derangements = 120 - 76 = 44
44
• Probability = 120
≈ 0.367

14