2
$\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$
  • $\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$ – Gerry Myerson Jan 18 '13 at 4:55
  • $\begingroup$ Edited for clarity. Also, thank you for catching my mistake with the simple example. $\endgroup$ – Vortico Jan 18 '13 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$ – Gerry Myerson Jan 18 '13 at 5:02
5
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Joel Reyes Noche Jan 18 '13 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 Jan 18 '13 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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.