Find the number of single valued functions from set A to another set B, given that the cardinalities of the sets A and B are m and n respectively.

GATE 1989 · Discrete Mathematics · Functions · medium

Answer: The number of functions from A (|A| = m) to B (|B| = n) is n^m.

1. Count the choices per input: Defining a function means deciding f(a) for every a in A. For one fixed input there are n elements of B to choose from, and these decisions are independent across the m inputs (repeats allowed).
2. Multiply across all inputs: By the multiplication principle the total is n x n x ... x n (m factors) = n^m. Hence the number of single-valued functions from A to B is n^m.