Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 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

share|improve this answer
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. –  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)$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.