2
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Justify your question. $\endgroup$ – Marc van Leeuwen Jan 28 '14 at 6:56
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

$n^m -n(n-1)\cdot \cdot \cdot(n-m+1)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.