Let A and B be sets with cardinalities m and n respectively. The number of one-one mappings (injections) from A to B, when m <= n, is A. m^n B. P(n, m) C. C(m, n) D. C(n, m) E. n^m

GATE 1993 · Discrete Mathematics · Functions · easy

Answer: The number of one-one mappings from A to B with m <= n is P(n, m) = n!/(n-m)! (option B).

1. Count distinct-image choices in order: The first element of A has n possible images; the second must differ, leaving n-1; the third n-2; continuing, the m-th element has n-m+1 choices. By the multiplication principle the count is n(n-1)...(n-m+1).
2. Recognise the product as P(n, m): The product n(n-1)...(n-m+1) is precisely the permutation P(n, m) = n!/(n-m)!. Hence the number of one-one mappings is P(n, m), matching option B.