4 views
Let $n$, $m$ and $k$ be three positive integers such that $n \geq m \geq k$. Let $S$ be a subset of $\{1, 2, …, n\}$ of size $k$. Consider sampling a function uniformly at random from the set of all functions mapping $\{1, …, n\}$ to $\{1, …, m\}$. What is the probability that $f$ is not injective on the set S, i.e., there exists $i, j \in S$ such that $f(i) = f(j)$?

In the following, the binomial coefficient $n\choose k$ counts the number of $k$-element subsets of an n-element set.

(A) $1 – \frac{k!}{k^k}$

(B) $1 – \frac{m!}{m^k}$

(C) $1 – \frac{k!{m\choose k}}{m^k}$

(D) $1 – \frac{k!{n\choose k}}{n^k}$

(E) $1 – \frac{k!{n\choose k}}{m^k}$
| 4 views