Problem:
For any finite set , let denote the number of elements in . Find the number of ordered pairs such that and are (not necessarily distinct) subsets of that satisfy
Solution:
We are given that and are subsets of and asked to count the number of ordered pairs such that .
Using the principle of inclusion-exclusion, we know that . Letting , , and , the condition becomes . Expanding the right-hand side gives . Subtracting both sides yields , which factors as .
So the condition holds if and only if or , meaning or .
Now we count the number of ordered pairs such that or . For each element of the universal set , we have three possibilities:
(1) it is in both and ,
(2) it is in but not in ,
(3) it is in neither nor .
So there are such ordered pairs with . Similarly, there are ordered pairs with .
However, the pairs where are counted twice. There are such pairs, since each element is either in the subset or not.
By the principle of inclusion-exclusion, the total number of valid ordered pairs is .
The problems on this page are the property of the MAA's American Mathematics Competitions