Número de funciones crecientes

Question

Deje $a > 0$, e $0 < n < m$ ser dado. Cómo muchas de las funciones $f:\{0, \ldots, n\} \rightarrow \{0, \ldots, m \}$ hay que satisfacer

1. $f$ es no decreciente
2. Para todos los $i \in \{0, \ldots, n \}$ tenemos $f(i) \leq a + i$

Estoy interesado en el caso de que $a, m = \Theta(n)$. En este caso, como $n \rightarrow \infty$, yo esperaba que el número de tales funciones es exponencial en $n$. ¿Qué es esta tasa de aumento exponencial?

Answer 1

Si $m$-secuencia está aumentando, a continuación, todos los términos de la misma son distintos, a partir de n disponible objetos que seleccione m objetos en $\binom{n}{m}$ formas en que se pueden organizar en el aumento de las secuencias de una manera única.Por lo que el número de secuencias con las propiedades deseadas es $$\binom{n}{m}=\frac{n!}{m!(n-m)!}$$ en el segundo caso tenemos las secuencias $$(a,a+1,a+2,...,a+m)$$ no $n-m\leq a+m\leq n$ o $a=1,2,...,n-m$ que significa ther existe $$n-m$$ secuencias de la segunda propperties

Answer 2

Hay $(m+1)$ opciones para el destino de 0. Luego hay $(m+1-f(0))$ opciones para el destino de 1, $(m+1-f(1))$ de la meta de 2 y así sucesivamente.

Por lo que el total será

$\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)$