# Largest binary sequence with no more than two repeated subsequences

$A$ is an ordered sequence of elements $a_i = 0, 1$ containing no more than two adjacent repeated subsequences $[a_i, a_{i + k})$. What is the longest sequence $A$? Is it even finite?

For example, the subsequence $\{0\}$ is found three times in a row in $\{0, 0, 0\}$, and $\{1, 0\}$ is found in $\{\ldots, 1, 0, 1, 0, 1, 0, \cdots\}$ at least three times in a row. Therefore, both sequences are invalid.

As a simplification, if the number of allowed repeated subsequences is decreased to one, the sequences with the maximum cardinality under this new restriction are simply $\{0, 1, 0\}$ and $\{1, 0, 1\}$, each containing 3 elements.

• This is confusing. 10 is not found in ...000... at all, and 01 and 10 are both repeated in 01010 and in 10101. Anyway, you might be interested in "cube-free sequences", about which much is known. Commented Jan 18, 2013 at 4:55
• Edited for clarity. Also, thank you for catching my mistake with the simple example. Commented Jan 18, 2013 at 5:01
• Thanks for the edit. Now I'm almost certain you want to look up cube-free sequences, especially cube-free binary sequences, and in particular the Thue-Morse sequence. Commented Jan 18, 2013 at 5:02

As Gerry Myerson noted in the comments, you're probably interested in cube-free binary words. There are many cube-free infinite binary words (words of infinite length). In fact, there are an infinite number of them. Furthermore, there are an uncountably infinite number of them.

• If you're interested in sequences with no repeated subsequences, then you might want to look at square-free words: en.wikipedia.org/wiki/Squarefree_word. The field of study concerned with these is called combinatorics on words.
– JRN
Commented Jan 18, 2013 at 7:05
• Thanks, this answers my question! I was also surprised to see that there are an infinite number of squarefree words with an alphabet of three or more characters. Commented Jan 18, 2013 at 13:26

A simple and unusually interesting example is the Thue-Morse sequence. Let: \begin{align} S_0 & = \langle 0\rangle \\ S_1 & = \langle 0, 1\rangle \\ S_2 & = \langle 0, 1, 1, 0\rangle \\ S_3 & = \langle 0, 1, 1, 0, 1, 0, 0, 1\rangle \\ S_4 & = \langle 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0\rangle \\ &\vdots \end{align}

Where $S_{i+1}$ is formed by concatenating $S_i$ with its own inverse, which has 1 wherever $S_i$ has 0 and vice-versa. The Thue-Morse sequence is the "limit" of this process: The $i$th element of the Thue-Morse sequence is the same as the $i$th element of the first $S_n$ that is long enough to have an $i$th element.

$TM$ satisfies the following recurrence:

\begin{align} TM(0) & = 0 \\ TM(2n) & = TM(n) \\ TM(2n+1) & = 1-TM(n) \end{align}

This sequence $TM$ has the property that for any sequence $X$, $TM$ does not contain $XXX$.