Source: Extra Practice
If n(A) = p and n(B) = q, then the total number of non-empty relations that can be defined from A to B is:
Options
Option A
2^(pq)
Option B
pq
Option C is correct
2^(pq) - 1
Option D
2^(p+q)
Explanation
A relation from A to B is any subset of A × B. The number of elements in A × B is pq. The total number of subsets (relations) is 2^(pq). Since the question asks for 'non-empty' relations, we subtract the empty set (void relation). Therefore, the answer is 2^(pq) - 1. Option 1 includes the empty relation, while options 2 and 4 are incorrect formulas for the number of relations.