Source: Extra Practice
Let n(A) = m and n(B) = n. The total number of non-empty relations that can be defined from A to B is:
Options
Option A
mn
Option B is correct
2^(mn) - 1
Option C
2^(mn)
Option D
m^n - 1
Explanation
The total number of relations from A to B is the total number of subsets of A × B, which is 2^(n(A×B)) = 2^(mn). A 'non-empty' relation means we must exclude the empty set (null relation). Thus, the count is 2^(mn) - 1. Option C includes the empty relation. Option A is just the count of ordered pairs. Option D is related to the count of functions.