# 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. 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) 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 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}.$$