Consider the Complement
Lesson · Intermediate
Combinatorics
For example, this applies to:
• a subset and its complement
• a graph and its complement
• selected and unselected objects
• an event and its complementary event
What is the maximum number of subsets of
that can be selected such that no two selected subsets are disjoint?
There are
subsets in total.
Pair every subset A with its complement A^c. This gives
pairs.
Since
we cannot select both subsets from any complementary pair.
So at most 32 subsets can be selected.
32 is attainable. Consider all subsets that include 1.
A fair die is rolled 3 times. What is the probability that at least one roll is a 6?
It is easier to consider the complementary event: no roll is a 6.
The probability of not rolling a 6 on one roll is 5/6, so
Therefore,
Let
How many subsets of S have a sum greater than 52?
The sum of all elements of S is
Pair every subset A with its complement A^c. Their sums add to 105.
There are
subsets, so there are
complementary pairs.
Thus the number of subsets with sum greater than 52 is
How many simple graphs with 5 unlabeled vertices and 8 edges are there?
A graph on 5 vertices has at most
edges.
Therefore, the complement of a graph with 8 edges has
edges.
So instead of classifying graphs with 8 edges, classify graphs with only 2 edges.
There are only two possibilities:
1. The two edges share a common vertex.
2. The two edges are disjoint.
These give two nonisomorphic graphs.
Therefore, the number of graphs is