Let $n, m$ and $k$ be three positive integers such that $n \geq m \geq k$. Let $S$ be a subset of $\left \{ 1, 2,\dots, n \right \}$ of size $k$. Consider sampling a function $f$ uniformly at random from the set of all functions mapping $\left \{ 1,\dots, n \right \}$ to $\left \{ 1,\dots, \text{m} \right \}$. What is the probability that $f$ is not injective on the set $S$, i.e., there exist $i,j \in S$ such that $f(i) = f(j)$?
In the following, the binomial coefficient $\binom{n}{k}$ counts the number of $k$-element subsets of an $n$-element set.
- $1-\frac{k!}{k^{k}}$
- $1-\frac{m!}{m^{k}}$
- $1-\frac{k!\binom{m}{k}}{m^{k}}$
- $1-\frac{k!\binom{n}{k}}{n^{k}}$
- $1-\frac{k!\binom{n}{k}}{m^{k}}$