# Combinatorial Correctness of one-to-one functions

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