Let $a > 0$, and $0 < n < m$ be given. How many functions $f:\{0, \ldots, n\} \rightarrow \{0, \ldots, m \}$ are there which satisfy
- $f$ is non-decreasing
- For all $i \in \{0, \ldots, n \}$ we have $f(i) \leq a + i$
I am interested in the case where $a, m = \Theta(n)$. In this case, as $n \rightarrow \infty$, I expected that the number of such functions is exponential in $n$. What is this rate of exponential increase?
Best Answer
If $m$-sequence is increasing then all terms of it are distinct, from n disponible objects we choose m objects in $\binom{n}{m}$ ways that can be arranged in increasing sequences in an unique way.So number of sequences with desired properties is $$\binom{n}{m}=\frac{n!}{m!(n-m)!}$$ in the second case we have sequences $$(a,a+1,a+2,...,a+m)$$ there $n-m\leq a+m\leq n$ or $a=1,2,...,n-m$ that mean ther exists $$n-m$$ sequences with second propperties