1
$\begingroup$

This question is related to one I asked previously. This is probably a little harder. I had a crack at it today, but have become stuck. I suspect the result is buried in the order statistics literature somewhere, and perhaps somebody is familiar with it. That, or Peter might insta-solve again :).

Given a vector $s$ of integers let $d(s)$ be the maximum difference between any two integers in $s$ when sorted in ascending order. That is, if we sort $s$ in ascending order to obtain $v$, then $$d(s) = \max_{i} (v_{i+1} - v_i).$$

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$ ?

Again, I'm more interested in the case where $n$ is much larger than $m$ and if reasonable bounds can be found for $d(s)$, then this would be useful too.

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

1
$\begingroup$

You are essentially looking at a graph (loops allowed) whose vertex set is $V=\{1,2,\dots,n\}$ with edges $E=\{(i,j) \ | \ |i-j|\le k\}$. These graphs are called path-schemes, see my answer here.

Let $A$ be the adjacency matrix of this graph, then $\sum_{r\le k} N_k$ is equal the sum of all entries in $A^{m-1}$, because $(A^{m-1})_{ij}$ is the number of walks in the graph of length $m-1$ from $i$ to $j$. I don't expect a simple expression in the end, however since $A$ is a Toeplitz matrix the calculations should be friendly.

$\endgroup$
2
  • $\begingroup$ Neat idea. I think you might mean $A^{m-1}$? Also, don't you need to sum all of the elements in the matrix, not just those above and on the diagonal? $\endgroup$ Aug 14, 2010 at 4:19
  • $\begingroup$ Yes, I edited to fix that. $\endgroup$ Aug 14, 2010 at 4:27

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.