Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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 4:55
    
Edited for clarity. Also, thank you for catching my mistake with the simple example. –  Vortico Jan 18 '13 at 5:01
5  
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 5:02
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
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. –  Joel Reyes Noche Jan 18 '13 at 7: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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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