# Number of Injective Maps

What is the number of injective maps from a set of cardinality $m$ into a set of cardinality $n$ $(m \leq n)$?

-
Choose the range of the map. This can be done in $\binom{n}{m}$ ways. For any choice, there are $m!$ functions that have that range, for a total of $\binom{n}{m}m!$, none of the above. – André Nicolas Nov 24 '12 at 2:43
@AndréNicolas This is a very clean way to think about the problem. I think it deserves to be posted as an answer. – Austin Mohr Nov 24 '12 at 3:23
It is not very different in spirit from yours. Instead of posting, might as well upvote yours. – André Nicolas Nov 24 '12 at 4:53

## 1 Answer

You may map the first element of the domain to any of the $n$ choices in the codomain.

You may map the second element of the domain to any of the $n-1$ remaining choices in the codomain. It is $n-1$ because you cannot select your previous choice again (this is what it means for the function to be injective).

Continue in this way until you reach the last element of the domain, which can be mapped to any of the remaining $n-(m-1)$ (or $n - m + 1$) choices in the domain.

To get the total number of ways to build the function, you must multiply the number of choices at each step (this fact is sometimes called the Rule of Product). Doing so gives $$n(n-1)\cdots(n-m+1) = \frac{n!}{(n-m)!}.$$

-