Count the number of functions Let $m$ and $n$ be two integers such that $m \geq n \geq 1$. Count the number of functions $f : \{1,2,3=...,n \} \rightarrow \{1,2,3=...,m \}$ such a that $f$ is strictly increasing. 
My attempt:
case 1: $m=n=1$,  only 1 , $f(1)=1$ 
case 2: $m>n=1$, $m$-many, as $f(1)$ can take any of the $m$-values in the range
case 3 : $m=n>1$, identity function, only $1$
case 4: $m>n>1$, $1$ can be mapped to $k_1 , 1 \leq k_1 \leq (m-n+1) $... i don't know how should I proceed and put the rest of the calculation into a formula. Any hints will be appreciated...
 A: If we choose $n$ elements in $\{1, 2, \cdots, m\}$, we can correspond the case to each $f$. 
For example, if $m=3, n=5$, in $\{1, 2, 3, 4, 5\}$ and choose 3 elements in that set, for example, 2, 3, 5, then the corresponding $f$ is defined as $f(1)=2, f(2)=3, f(3)=5$. 
Therefore the number of functions satisfying the strictly increasing condition is $\binom{m}{n}$ if $m\geq n$ and $0$ otherwise. 
A: You need to choose $n$ different output values to obtain a strictly increasing function, and once you choose them you can assign them to the arguments in exactly one way.
So with given constraints each resulting function is uniquely identified by the set of its values. Hence the question becomes:

How many different $n$–element subsets can you choose from the $m$–element set?

Answer:
$$m \choose n$$
Here's another way to view the problem.
Let's denote the number sought by $N(m,n)$. Suppose we shrink the codomain by one – we get $N(m-1,n)$ functions, which certainly satisfy all initial requirements. Let's shrink a domain, too – and we get $N(m-1,n-1)$ functions. Each of the latter, however, can be extended by appending the $n$-th term equal $m$ (as the largest in the codomain, the $m$ value may appear only at the end of an increasing sequence). Hence a recursive formula:
$$N(m,n) = N(m-1,n-1) + N(m-1,n)$$
with edge conditions:
$$\begin{cases}N(m,0)&=1 \\ N(m,m)&=1\end{cases}$$
which are 'there's just one function from the empty domain' and 'there's just one strictly increasing sequence of $m$ terms and all $m$ values'.
Which are properties of the $m\choose n$.
