Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$

share|improve this question
add comment

1 Answer

up vote 7 down vote accepted

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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