Let X = 1, 2, 3, 4. The number of ordered pairs (A, B) of subsets of X such that A is a proper subset of B is
Answer: 65 Status: Verified (T3). Checked by code and independent solves on 2026-11-20.
Solution
- For A subset of B, each element is in neither, in B only or in both A and B: 3 choices.
- So pairs with A a subset of B number 3⁴ = 81.
- Remove the pairs with A = B, which number 2⁴ = 16, to get 81 - 16 = 65.
Fast method
3ⁿ - 2ⁿ = 81 - 16 = 65.
Expected time: about 120 seconds. Difficulty: hard.
Topic page: Sets, power set and algebra of sets