4

$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.

Vortico
  • 1,633
  • 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. – Gerry Myerson Jan 18 '13 at 04:55
  • Edited for clarity. Also, thank you for catching my mistake with the simple example. – Vortico Jan 18 '13 at 05:01
  • 6
    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. – Gerry Myerson Jan 18 '13 at 05:02

2 Answers2

7

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.

Community
  • 1
JRN
  • 6,566
  • 1
    If you're interested in sequences with no repeated subsequences, then you might want to look at square-free words: https://en.wikipedia.org/wiki/Squarefree_word. The field of study concerned with these is called combinatorics on words. – JRN Jan 18 '13 at 07:05
  • 1
    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. – Vortico Jan 18 '13 at 13:26
4

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$.

MJD
  • 65,394
  • 39
  • 298
  • 580