# one-to-one functions question

Let $A$ be a set of size $m$, let $B$ be a set of size $n$, and assume that $n \geq m \geq 1$. How many functions $f : A \rightarrow B$ are there that are ${not}$ one-to-one? Justify your answer.

• Justify your question. – Marc van Leeuwen Jan 28 '14 at 6:56

Hint: There are $n^m$ functions from $A$ to $B$. Now let us count the one-to-one functions. Let $A=\{a_1,a_2,\dots,a_m\}$.
To make a one-to-one function $f$, $f(a_1)$ can be chosen in $n$ ways. For each such choice, $f(a_2)$ can be chosen in $n-1$ ways. And so on.
$n^m -n(n-1)\cdot \cdot \cdot(n-m+1)$