The number of equivalence relations on the set 1, 2, 3, 4 is
Answer: (D) 15 Status: Verified (T1). Checked by code and independent solves on 2026-11-20.
- 14
- 16
- 24
- 15
Solution
- Equivalence relations on a set correspond one-to-one to partitions of the set.
- Partitions of 4 elements by block sizes: 4 (1), 3+1 (4), 2+2 (3), 2+1+1 (6), 1+1+1+1 (1).
- Total = 1 + 4 + 3 + 6 + 1 = 15.
Fast method
Bell number B(4) = 15 (1, 2, 5, 15, 52, ...).
Expected time: about 120 seconds. Difficulty: medium.
Topic page: Relations and equivalence relations