GATE 2012 CS (CS1) – Question 47

Engineering Mathematics · Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) · 2 marks · Multiple choice

How many surjections exist from an n-element set (n≥2) to a two-element set?

$2^n$
$2^n-1$
$2^n-2$
$2(2^n-2)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $2^n-2$

Explanation

Each of n domain elements independently chooses one of two images, giving 2ⁿ functions. Exactly two fail to hit both targets: the constant function to the first and the constant function to the second. Subtracting gives 2ⁿ−2, C.

More Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) questions

GATE 2010 CS (CS1) Q37 – A divisor of 1099 is chosen uniformly at random. What is the probability that it is a…
GATE 2015 CS (CS2) Q14 – How many positive divisors does 2100 have?
GATE 2015 CS (CS2) Q58 – How many onto functions map X=1,2,3,4 to Y=a,b,c?
GATE 2015 CS (CS3) Q25 – How many four-digit numbers using only 1,2,3 have digits in nondecreasing order from left…
GATE 2021 CS (CS2) Q60 – S has ten elements. How many ordered tuples (A,B) of subsets of S satisfy A⊆B?
GATE 2026 CS (CS1) Q57 – Let G be an undirected graph, which is a path on 8 vertices. The number of matchings in G…

All Discrete Mathematics: Combinatorics (Counting, Recurrence Relations, Generating Functions) questions →