How can we calculate the probability that the randomly chosen function will be strictly increasing? Consider the set of all functions from $\{1,2,...,m\}$ to $\{1,2,...,n\}$, where $n > m$. If a function is chosen from this set at random, what is the probability that it will be strictly increasing?
 A: Let $S(n,m)$ be the number of sub-arrays $1 \leqslant k_1 < k_2 < \cdots < k_m \leqslant n$ containing $m$ integer values that are increasing and are bounded by the values one and $n$.  This binary function is well-defined for all integers $1 \leqslant m \leqslant n$, giving a triangular array of values.
With a simple combinatorial argument$^\dagger$ we can establish the following recursive equations that define this binary function:
$$S(n+1,m) = S(n,m) + S(n,m-1) \quad \quad \quad \quad S(n,1) = n.$$
Solving this recursive equation gives us the explicit formula:
$$S(n,m) = {n \choose m} = \frac{n!}{m!(n-m)!}.$$
(There are other combinatorial arguments that also lead you to this result.  For example, choosing an increasing function is equivalent to choosing $m$ values in the co-domain, which are then placed in increasing order.)  Now, to get the result we need to be clear on exactly how a "random function" on this domain and co-domain is chosen.  The simplest specification is to say that each possible mapping is chosen with equal probability, which means that there are $n^m$ equiprobable functions.  Hence, the probability of interest is:
$$\mathbb{P}(\text{Increasing Function}) = \frac{n!}{m!(n-m)! \cdot n^m}.$$
Taking a first-order Stirling approximation for large $n$ gives $\mathbb{P}(\text{Increasing Function}) \approx 1/m!$, which is a very crude estimate that is suitable when $n$ is substantially larger than $m$.  So basically, we see that once the co-domain in this problem is large, the probability of getting an increasing sequence at random is small; this accords with intuition. 

$^\dagger$ If $m=1$ then we have only a single value in the mapping and every mapping to any of the $n$ places gives an increasing map.  We therefore have $S(n,1)=n$ for all $n \in \mathbb{N}$.  Moreover, the number of sub-arrays $S(n+1,m)$ includes all sub-arrays where the values occurs in the first $n$ places (there are $S(n,m)$ of these) and all the sub-arrays where the last value occurs in the last place and the remaining values occur before this (there are $S(n,m-1)$ of these).
A: Let us pick $m$ elements from $\{1,\dotsc,n\}$, let us call these $a_1 < a_2 < \dotsc , a_m$. Clearly these define a strictly increasing function $f$ from $\{1,\dotsc,m\} \to \{1,\dotsc,n\}$ via the rule $f(i) = a_i$. Furthermore, any strictly increasing function defined on the above sets is of this form.
Hence there are exactly ${n \choose m}$ strictly increasing functions. On the other hand, in total there are $n^m$ functions mapping between these two sets. Assuming that by "random" the OP means the uniform measure on the $n^m$ functions above, then the probability of picking a strictly increasing function is:
$$ \frac{{n \choose m}}{n^m} $$
For example, for $n >> m$, an application of Stirling's approximation, shows that the RHS is $ \approx \frac{1}{m!}$.
