# Raggedness measure of a sequence

Define a raggedness measure $$r$$ of a sequence $$S$$ in this way:

• Two members $$S_i,S_j$$ of the sequence (who don't have to be adjacent!) are called neighbors if $$\not\exists_{k\in]i,j[}|S_k\in]S_i,S_j[$$.
• Example: $$S=(1,4,3,2,5)$$. 4 and 5 are neighbors (3 and 2 are outside of their size interval), 4 and 2 are not (3 falls inbetween), 1 and 4 are, 4 and 3 are (up or down doesn't matter).
• $$r=card(neighbor-pairs(S))/n$$ ($$r=8/5$$ for the example)
• WLOG for $$S$$ we can limit ourselves to permutations of $$\{1,\dots,n\}$$. (Some series below are noninteger, we can simply "stretch" them to integer.)

$$r$$ is at minimum $$O(1)$$ (obvious, all adjacent members of $$S$$ are also neighbors) and at maximum $$O(\log n)$$ (this follows from a seminal result of E.Demaine on binary search trees). Some further examples that I tried:

• $$S=id, r=1$$ (trivial)
• $$S$$ is the bitwise permutation, $$r=O(\log n)$$ (well known)
• $$S$$ is the Gray code permutation, $$r=185/48$$ if I could compute and sequence-guess correctly :-)
• $$S$$ is the Farey series sorted by denominator and then by nominator, $$r=O(\log n)$$ (says the experiment - can you verify?)
• $$S$$ is the Stern-Bacrot series, my best guess is $$r=O(\log n)$$ again (ditto?)

My questions:

• Do you have a reference for sequence raggedness in general?
• Do you have a reference for this measure in particular?
• Do you have an idea for some (not too convoluted :-) $$S$$ with $$O(1)?