How many onto (or surjective) functions are there from an n-element (n >= 2) set to a 2-element set? A. 2^n B. 2^n - 1 C. 2^n - 2 D. 2(2^n - 2)

GATE 2012 · Discrete Mathematics · Functions · medium

Answer: C. 2^n - 2

1. Count all functions: Each of the n domain elements independently picks one of 2 images, so the total number of functions is 2^n.
2. Subtract the non-onto functions: With m = n and k = 2: 2^n - C(2,1)*1^n + C(2,2)*0^n = 2^n - 2*1 + 0 = 2^n - 2. Equivalently, the only non-onto maps are the 2 constant functions, so 2^n - 2.
3. Select the option: The onto count 2^n - 2 matches option C.