Let X, Y, Z be sets of sizes x, y and z respectively. Let W = X x Y and E be the set of all subsets of W. The number of functions from Z to E is A. z^(2^(xy)) B. z * 2^(xy) C. z^(2^(x+y)) D. 2^(xyz)

GATE 2006 · Discrete Mathematics · Functions · medium

Answer: The number of functions from Z to E is 2^(xyz), so the answer is Option D.

1. Size of W and of its power set E: W = X x Y has |X| * |Y| = x*y ordered pairs. E is the set of all subsets of W, so by the subset-count rule |E| = 2^(xy).
2. Count functions from Z to E: The number of functions from a z-element set to an |E|-element set is |E|^z = (2^(xy))^z. By the power-of-a-power rule, (2^(xy))^z = 2^(xy*z) = 2^(xyz).