3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Commented Jan 18, 2013 at 4:55
  • $\begingroup$ Edited for clarity. Also, thank you for catching my mistake with the simple example. $\endgroup$
    – Vortico
    Commented Jan 18, 2013 at 5:01
  • 6
    $\begingroup$ 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. $\endgroup$ Commented Jan 18, 2013 at 5:02

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – JRN
    Commented Jan 18, 2013 at 7:05
  • 1
    $\begingroup$ 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. $\endgroup$
    – Vortico
    Commented Jan 18, 2013 at 13:26
3
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .