TIFR CSE 2022 | Part A | Question: 5

Question

Let $\mathcal{F}$ be the set of all functions mapping $\{1, \ldots, n\}$ to $\{1, \ldots, m\}$. Let $f$ be a function that is chosen uniformly at random from $\mathcal{F}$. Let $x, y$ be distinct elements from the set $\{1, \ldots, n\}$. Let $p$ denote the probability that $f(x)=f(y)$. Then,

• A. $p=0$
• B. $p=\frac{1}{n^m}$
• C. $0<p \leq \frac{1}{m^n}$
• D. $p=\frac{1}{m}$
• E. $p=\frac{1}{n}$

Answer 1

Sample space will be Total no of functions = $m^{n}$

Since we need only the functions where f(x) = f(y) 

so f(x) can map to any of the m elements which is same as selecting one element from m elements