MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question is related to one I asked previously. This is probably a little harder. I had a crack at it today, but have become stuck. I suspect the result is buried in the order statistics literature somewhere, and perhaps somebody is familiar with it. That, or Peter might insta-solve again :).

Given a vector $s$ of integers let $d(s)$ be the maximum difference between any two integers in $s$ when sorted in ascending order. That is, if we sort $s$ in ascending order to obtain $v$, then $$d(s) = \max_{i} (v_{i+1} - v_i).$$

For $s$ a vector of length $m$ from $\lbrace 1,2,\dots,n\rbrace^m$ we must have $0 \leq d(s) < n$.

Given $0 \leq k < n$, how may such vectors have $d(s) = k$ ?

Again, I'm more interested in the case where $n$ is much larger than $m$ and if reasonable bounds can be found for $d(s)$, then this would be useful too.

Note: If $N_k$ is the answer for $k$. Then you should have $n^m = \sum_{k=0}^{n-1}N_k$

share|cite|improve this question
up vote 1 down vote accepted

You are essentially looking at a graph (loops allowed) whose vertex set is $V=\{1,2,\dots,n\}$ with edges $E=\{(i,j) \ | \ |i-j|\le k\}$. These graphs are called path-schemes, see my answer here.

Let $A$ be the adjacency matrix of this graph, then $\sum_{r\le k} N_k$ is equal the sum of all entries in $A^{m-1}$, because $(A^{m-1})_{ij}$ is the number of walks in the graph of length $m-1$ from $i$ to $j$. I don't expect a simple expression in the end, however since $A$ is a Toeplitz matrix the calculations should be friendly.

share|cite|improve this answer
Neat idea. I think you might mean $A^{m-1}$? Also, don't you need to sum all of the elements in the matrix, not just those above and on the diagonal? – Robby McKilliam Aug 14 '10 at 4:19
Yes, I edited to fix that. – Gjergji Zaimi Aug 14 '10 at 4:27

Your Answer


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.