co.combinatorics - Maximum differences in sorted vectors of naturals

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,nrbrace^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$