Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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 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)!}. $$

share|improve this answer

Your Answer

 
discard

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.