66 views

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,

1. $p=0$
2. $p=\frac{1}{n^m}$
3. $0<p \leq \frac{1}{m^n}$
4. $p=\frac{1}{m}$
5. $p=\frac{1}{n}$

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

1 vote