SME
Discrete Mathematics
Sets and functions
Use this for “40 students take art, 35 band and 30 drama; 15 take art and band, 10 art and drama, 12 band and drama, 5 all three. How many take at least one?”
Diagram
|A ∪ B ∪ C|
|A ∪ B ∪ C| = 40 + 35 + 30 − 15 − 10 − 12 + 5
|A ∪ B ∪ C| = 73
The 7 regions: 20 + 13 + 13 + 10 + 5 + 7 + 5 = 73.
This is an example. Type your own values to start a new problem.
|A ∪ B ∪ C|
=
|A|
+
|B|
+
|C|
−
|A ∩ B|
−
|A ∩ C|
−
|B ∩ C|
+
|A ∩ B ∩ C|
Formulas
|A ∪ B ∪ C| = |A| + |B| + |C| − (|A ∩ B|) − (|A ∩ C|) − (|B ∩ C|) + |A ∩ B ∩ C|
73 = 40 + 35 + 30 − 15 − 10 − 12 + 5
Assumptions
•
Adding the three sets counts each pairwise overlap twice, so each is taken away once.
•
That takes the triple overlap away once too often, so it is added back.
•
Every region of the diagram is 0 or more: an overlap is no larger than what it lies in.
Step-by-step
WE KNOW
|A| = 40, |B| = 35, |C| = 30, |A ∩ B| = 15, |A ∩ C| = 10, |B ∩ C| = 12, |A ∩ B ∩ C| = 5
FIND
at least one (|A ∪ B ∪ C|)
Step 1 · Find at least one (|A ∪ B ∪ C|)
Use |A ∪ B ∪ C| = |A| + |B| + |C| − (|A ∩ B|) − (|A ∩ C|) − (|B ∩ C|) + |A ∩ B ∩ C|
Inclusion–exclusion: add the three sets, take away the three pairs, then add back the triple.
|A ∪ B ∪ C| = 40 + 35 + 30 − 15 − 10 − 12 + 5
|A ∪ B ∪ C| = 73
Check
Put the numbers back in. Both sides should match.
73 = 40 + 35 + 30 − 15 − 10 − 12 + 5 ✓
← Previous lesson
The steps of a proof by induction
Next lesson →
Power set and Cartesian product sizes
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
More problem types
Power set and Cartesian product sizes
Use this for “A has 3 elements and B has 4. How many subsets does A have, and how many ordered pairs are in A × B?”
Counting functions
Use this for “How many functions are there from a 3-element set to a 4-element set, and how many of them are one-to-one?”
One-to-one, onto or both
Use this for “Is f(n) = 2n from ℤ to ℤ one-to-one, onto, both or neither?”