Maximal size of a set of ordered words such that no pair of letters occurs twice Consider an alphabet $\Sigma=\{1,\dots,n\}$.
An ordered word is a word $w=w_1w_2\dots w_k\in\Sigma^*$ such that $w_1&lt;w_2&lt;\dots&lt;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 $\binom{n}{k}$ many ordered words of length $k$.

Now, what I am looking for is the maximal size of a subset $M\subseteq O_{n,k}$ such that each pair of letters $ij$ ($1\le i&lt;j\le 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\{|M|:M\subseteq O_{n,k}\text{ and }\#_{ij}(M)\le 1\text{ for all }i,j\text{ with }1\le i&lt;j\le 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 $$\frac{\binom{n}{2}}{k-1},$$ following from the fact that there are $\binom{n}{2}$ ordered pairs of elements, and each ordered word contains $k-1$ of them.

There is an almost matching lower bound of
$$
\frac{\binom{n-k+1}{2}}{k-1}.
$$
This shows that for fixed $k$, the answer is asymptotically
$$
\frac{n^2}{2(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 \frac{m-1}{k-1}$. Therefore, the total number of words is
$$
\sum_{m=k}^n \left\lfloor \frac{m-1}{k-1} \right\rfloor.
$$
We can estimate this sum roughly by
$$
\sum_{m=k}^n \left(\frac{m-1}{k-1}-1\right) =
\sum_{m=k}^n \frac{m-k}{k-1} = \frac{\binom{n-k+1}{2}}{k-1}.
$$