4
$\begingroup$

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?

1 Answers 1

2

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

  • 1
    This at least shows an upper bound, namely that the number of solutions is at most exponential.2012-11-19