# Number of increasing functions

Let $a > 0$, and $0 < n < m$ be given. How many functions $f:\{0, \ldots, n\} \rightarrow \{0, \ldots, m \}$ are there which satisfy

1. $f$ is non-decreasing
2. 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?

-

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

-
This is fine for strictly increasing functions. For non-decreasing, you sample with replacement, getting ${n+m \choose m}$. But neither respects criterion 2. –  Ross Millikan Nov 19 '12 at 14:01
I agree with Ross: the problem is much complicated by the extra requirement $f(i) \le a+i$ Restricting to nondecreasing sequences gives another standard thing to count, but with the extra requirement (2) the count is more difficult. –  coffeemath Nov 19 '12 at 14:15
This at least shows an upper bound, namely that the number of solutions is at most exponential. –  David Harris Nov 19 '12 at 14:39

There are $(m+1)$ choices for the target of 0. Then there are $(m+1-f(0))$ choices for the target of 1, $(m+1-f(1))$ for the target of 2 and so on.

So the total will be

$\sum_{i_1=0}^m\sum_{i_2=i_1}^m\cdots\sum_{i_n=i_{n-1}}^m\prod_{j=0}^n (m+1-i_j)$

-