1
$\begingroup$

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$

$\endgroup$

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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! $\endgroup$ Aug 12, 2010 at 21:57
  • $\begingroup$ 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. $\endgroup$ Aug 12, 2010 at 22:14
  • $\begingroup$ 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)!}$ $\endgroup$ Aug 12, 2010 at 23:18
  • $\begingroup$ 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. $\endgroup$ Aug 12, 2010 at 23:44
  • $\begingroup$ 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. $\endgroup$ Aug 13, 2010 at 0:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.