I have run into this problem (or something similar to it) a few times now and I am wondering if the answer is known.

Given an vector $s$ of integers let $d(s)$ be the minimum difference between any two integers in $s$, that is $$d(s) = \min_{i,j \in s} |i - j|.$$ 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$ ?

I'm more interested in the case where $n$ is much larger than $m$.

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