Maximum differences in sorted vectors of naturals - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T16:50:48Z http://mathoverflow.net/feeds/question/35444 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/35444/maximum-differences-in-sorted-vectors-of-naturals Maximum differences in sorted vectors of naturals Robby McKilliam 2010-08-13T06:27:35Z 2010-08-14T04:25:56Z <p>This question is related to one <a href="http://mathoverflow.net/questions/35351/minimum-differences-in-vectors-of-naturals" rel="nofollow">I asked previously</a>. 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 <a href="http://mathworld.wolfram.com/OrderStatistic.html" rel="nofollow">order statistics</a> literature somewhere, and perhaps somebody is familiar with it. That, or Peter might insta-solve again :).</p> <p>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).$$</p> <p>For $s$ a vector of length $m$ from $\lbrace 1,2,\dots,n\rbrace^m$ we must have $0 \leq d(s) &lt; n$. </p> <blockquote> <p>Given $0 \leq k &lt; n$, how may such vectors have $d(s) = k$ ? </p> </blockquote> <p>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.</p> <p>Note: If $N_k$ is the answer for $k$. Then you should have $n^m = \sum_{k=0}^{n-1}N_k$ </p> http://mathoverflow.net/questions/35444/maximum-differences-in-sorted-vectors-of-naturals/35448#35448 Answer by Gjergji Zaimi for Maximum differences in sorted vectors of naturals Gjergji Zaimi 2010-08-13T08:11:48Z 2010-08-14T04:25:56Z <p>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 <em>path-schemes</em>, see my answer <a href="http://mathoverflow.net/questions/28649/how-many-hamiltonians-paths-there-are-in-almost-regular-graph/28654#28654" rel="nofollow">here</a>. </p> <p>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.</p>