Let F be the set of one-to-one functions from the set {1, 2, ..., n} to the set {1, 2, ..., m} where m >= n >= 1. a. How many functions are members of F? b. How many functions f in F satisfy the property f(i) = 1 for some i, 1 <= i <= n? c. How many functions f in F satisfy the property f(i) > f(j) for all i, j with 1 <= i < j <= n?

GATE 1997 · Discrete Mathematics · Functions · medium

Answer: a. P(m,n) = m!/(m-n)!; b. n*(m-1)!/(m-n)!; c. C(m,n) = m!/(n!(m-n)!)

1. Count all injective functions (part a): |F| = P(m, n) = m!/(m-n)!. Each of the n domain positions is assigned a distinct codomain value sequentially.
2. Count injections with f(i) = 1 for some i (part b): Choose which domain element i maps to 1: n choices. The remaining n-1 domain elements must map injectively to the m-1 non-1 codomain values: P(m-1, n-1) ways. Total = n * (m-1)!/(m-n)!.
3. Count strictly decreasing injections (part c): A strictly decreasing injection f with f(1) > f(2) > ... > f(n) is completely determined by which n values appear in its range; the values must be arranged in decreasing order. So the count equals C(m, n).