GATE CS 2015 Set 2 Q.64 (CS Q.54): Probability and Statistics

Let $X$ and $Y$ denote the sets containing 2 and 20 distinct objects respectively and $F$ denote the set of all possible functions defined from $X$ to $Y$ . Let $f$ be randomly chosen from $F$ . The probability of $f$ being one-to-one is _____.

Your answer

Official answer and solution

Official answer: 0.95
From: Official GATE 2015 answer key

Solution

Calculate the ratio of injective (one-to-one) functions to total functions from $X$ to $Y$ .

We are given:

$|X| = 2$
$|Y| = 20$

Total number of functions from $X$ to $Y$ :

|F| = |Y|^{|X|} = 20^2 = 400.

Number of one-to-one (injective) functions:

The first element of $X$ can map to any of the 20 elements in $Y$ .
The second element of $X$ must map to any of the remaining 19 distinct elements in $Y$ .

\text{Injective functions} = 20 \times 19 = 380.

Probability:

P(\text{one-to-one}) = \frac{380}{400} = \frac{38}{40} = \frac{19}{20} = 0.95.

Final answer

0.95

Common trap

Dividing combinations $\binom{20}{2}$ by $20^2$ without accounting for domain permutations.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 2
Question: 64 of 65, printed as CS Q.54
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source