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?