Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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