How many binary relations are there on a set A with n elements?
GATE 1987 · Discrete Mathematics · Relations · medium
Answer: The number of binary relations on a set with n elements is 2^(n^2).
Compute |A x A|: The Cartesian product A x A contains all ordered pairs (a,b) with a,b in A. Since each component has n choices, there are n * n = n^2 ordered pairs.
Count subsets of A x A: A binary relation on A is any subset of A x A. The number of subsets of an m-element set is 2^m. Here m = n^2, so the number of binary relations is 2^(n^2).