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$

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Robby McKilliam
    Commented 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$
    – Robby McKilliam
    Commented 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$
    – Aaron Meyerowitz
    Commented 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$
    – Aaron Meyerowitz
    Commented 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$
    – Robby McKilliam
    Commented Aug 13, 2010 at 0:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .