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$ 



Minimum differences in vectors of naturals
The number of $m$-subsets of {$1,2,\ldots,n$} with distance at least $k$ between any pair is
$n - (k-1)(m-1) \choose m$.


Proof: for any subset of size $m$ of the first $n-(k-1)(m-1)$ integers, you can get a subset $S$ of the first $n$ with $d(S)\geq k$ by just adding $k-1$ consecutive integers after each of the first $m-1$ elements of $S$. 


So your answer is ${ n - (k-1)(m-1) \choose m } -{ n - k(m-1) \choose m }$ .


**UPDATE** The intended question was about vectors and not sets. Essentially the same proof works; see the comments.


