What is the number of injective maps from a set of cardinality $m$ into a set of cardinality $n$ $(m \leq n)$?
Number of Injective Maps
7
$\begingroup$
combinatorics
functions
-
4**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. – 2012-11-24
-
0@AndréNicolas This is a very clean way to think about the problem. I think it deserves to be posted as an answer. – 2012-11-24
-
0It is not very different in spirit from yours. Instead of posting, might as well upvote yours. – 2012-11-24
1 Answers
11
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)!}. $$
-
1Small remark: the left hand side of the equation is more general, since it gives the right number (0) even when $m>n$. The right hand side is undefined when $m>n$ since the factorial of negative numbers is undefined. – 2018-11-16