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 is fine for strictly increasing functions. For non-decreasing, you sample with replacement, getting ${n+m \choose m}$. But neither respects criterion 2.2012-11-19
  • 0
    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.2012-11-19
  • 1
    This at least shows an upper bound, namely that the number of solutions is at most exponential.2012-11-19