# Minimum differences in vectors of naturals

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$

-

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.

-
Hi Peter, I don't think this is correct. With ''m-subsets of $\{1,2,\cdots,n\}$'' you are not allowing repetition, but I mean for the question to allow repetition. This is wholly my fault, I should never have called $S$ a set! – Robby McKilliam Aug 12 '10 at 21:57
My comment makes no sense! Repetition implies that $d(S) = 0$. I'm going to have to stop and think about what I am asking. – Robby McKilliam Aug 12 '10 at 22:14
That is the answer for sets since one gets just those sets, and once each. Then $\binom {n}{m} = \sum_{k=1}^{n-1}N_k$. If you want to have an $N_0$ and $n^m = \sum_{k=0}^{n-1}N_k$ then you really are talking about vectors. Then, for $k \gt 0$, multiply the answer above by $m!$. And then $N_0$ is what it would have to be, $n^m-\frac{n!}{(n-m)!}$ – Aaron Meyerowitz Aug 12 '10 at 23:18
It seems that you really do mean vectors and not multisets as in your amended title. But the answer for multisets is cute. Then $N_k$ is as Peter said for $k \gt 0$ and $N_0=\binom{n+m-1}{m}-\binom{n}{m}$ which is the $k=0$ case of the formula. – Aaron Meyerowitz Aug 12 '10 at 23:44
Indeed, I mean vectors. I have fixed the title. I have made a bit of a mess of this question! And multiplying Peters answer by $m!$ as you have said give the desired result. – Robby McKilliam Aug 13 '10 at 0:28