Dark Mode

66 views

2 votes

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,

- $p=0$
- $p=\frac{1}{n^m}$
- $0<p \leq \frac{1}{m^n}$
- $p=\frac{1}{m}$
- $p=\frac{1}{n}$