Dgdrxrt

Consider an alphabet $Sigma=1,dots,n$.
An ordered word is a word $w=w_1w_2dots w_kinSigma^*$ such that $w_1<w_2<dots<w_k$. In other words, an ordered word is a strictly increasing sequence over $1,dots,n$.

Let us call $O_n,k$ the set of all ordered words over $1,dots,n$ of length $k$. Clearly, there are $binomnk$ many ordered words of length $k$.

Now, what I am looking for is the maximal size of a subset $Msubseteq O_n,k$ such that each pair of letters $ij$ ($1le i<jle n$) occurs at most once as a consecutive substring in any word of $M$. What is the maximal size of such a subset?

Formally, let $#_ij(M)$ be the number of words in $M$ that contain $ij$ as a consecutive substring, then
$$m_n,k=max:Msubseteq O_n,ktext and #_ij(M)le 1text for all i,jtext with 1le i<jle n.$$
What is $m_n,k$?

Asymptotic behavior as well as some non-trivial lower and upper bounds would be helpful.

$ $

Example: $Sigma=1,2,3,4$ and $k=3$.

All ordered words of length $3$ are
$$O_4,3=123,124,134,234.$$
A maximal subset such that no pair occurs more than once would be
$$M=123,134,$$
because all pairs $(12,13,14,23,24,34)$ occur at most once as a consecutive substring in $M$ and there is no set of size $3$ with this property. It follows that $m_4,3=2$.

Thank for any help.

There is a simple upper bound of $$fracbinomn2k-1,$$ following from the fact that there are $binomn2$ ordered pairs of elements, and each ordered word contains $k-1$ of them.

There is an almost matching lower bound of
$$
fracbinomn-k+12k-1.
$$
This shows that for fixed $k$, the answer is asymptotically
$$
fracn^22(k-1) pm O(n).
$$

For every $c geq 1$ and $1 leq d leq c$, we can consider the collection of ordered words of the form
$$
d,d+c,ldots,d+(k-1)c \
d+(k-1)c,d+(k+1)c,ldots,d+2(k-1)c \
ldots
$$
These collections for all $c,d$ have disjoint pairs. For a given $m leq n$ and $c$, there is a word of this type if $m-(k-1)c geq 1$, that is, if $c leq fracm-1k-1$. Therefore, the total number of words is
$$
sum_m=k^n leftlfloor fracm-1k-1 rightrfloor.
$$
We can estimate this sum roughly by
$$
sum_m=k^n left(fracm-1k-1-1right) =
sum_m=k^n fracm-kk-1 = fracbinomn-k+12k-1.
$$