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)$?

Solution 1:

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)!}. $$