This question is related to one [I asked previously](https://mathoverflow.net/questions/35351/minimum-differences-in-vectors-of-naturals). 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](http://mathworld.wolfram.com/OrderStatistic.html) 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$ 



Maximum differences in sorted vectors of naturals
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](https://mathoverflow.net/questions/28649/how-many-hamiltonians-paths-there-are-in-almost-regular-graph/28654#28654). 


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.


