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.

Let $\lbrack k\rbrack$ be the set of integers $\{1, 2, \ldots, k\}$. What is the number of one-to-one functions from $m$ to $n$ if $m \leq n$? My answer is: $\dfrac{n!}{(n-m)!}$

My reasoning is the following:

We have an $m$-step, independent process:

Step 1: choose the first $m \in \lbrack m \rbrack$ to be mapped to a $n \in \lbrack n \rbrack$ There are $n$ choices.

Step 2: choose the second $m \in \lbrack m \rbrack$ to be mapped to a $n \in \lbrack n \rbrack$ There are $n-1$ choices here since we cannot map to the $n$ in the previous step (as we must count one-to-one functions)

Repeat this until for $1, 2, \ldots m$. This is $n(n-1)(n-2) \ldots (n-m+1) = \dfrac{n!}{(n-m)!}$

  1. Is this correct?
  2. Is my reasoning correct?
share|improve this question
    
Idea is right. There are a number of little typos, a couple of times $i$ when you mean $[i]$, a $k$ almost at the end when you mean $m$. And $n \in [n]$ is not best notation. –  André Nicolas Jan 22 '13 at 22:28
2  
Why do you have $m_1,m_2,\dots,m_k$? It is $1,2,\dots,m$. Also in first line, beginning of second you want from $[m]$ to $[n]$ where $m\le n$. –  André Nicolas Jan 22 '13 at 22:36
add comment

1 Answer

up vote 1 down vote accepted

It is OK, modulo minor problems. You don't have to select the $m$'s, just go with the natural order 1, 2, ... Take a look at the notation suggested by Knuth et al in "Concrete Mathematics", it really does clean up much clutter.

share|improve this answer
add comment

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.