Maximum differences in sorted vectors of naturals

Question

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$

Answer 1

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.