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?

**Contents**hide

#### Best Answer

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!}$.

### Similar Posts:

- Solved – Prove that the cdf is strictly increasing on the support if the support is a finite interval
- Solved – How to convert daily volatility to monthly
- Solved – MGF of the multivariate hypergeometric distribution
- Solved – MGF of the multivariate hypergeometric distribution
- Solved – You randomly select two distinct integers between 1 and 100. What is the probability that the larger number is exactly twice the smaller number