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

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|cite|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
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
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|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.