How many letters suffice to construct words with no repetition? [on hold]
$begingroup$
Given a finite set $A={a_1,ldots , a_k}$, consider the sequences of any length that can be constructed using the elements of $A$ and which contain no repetition, a repetition being a pair of consecutive subsequences (of any length) that are equal. Is it true that $k = 4$ is the minimum number of elements in $A$ that allows the construction of sequences of any length containing no repetition? Can anyone indicate a reference for this result, if true?
co.combinatorics symbolic-dynamics
edited 7 hours ago
YCor
29k486140
asked 9 hours ago
PiCoPiCo
412
New contributor
PiCo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
put on hold as off-topic by Emil Jeřábek, Jeremy Rickard, YCor, bof, Andrés E. Caicedo 28 mins ago
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Emil Jeřábek, Jeremy Rickard, bof
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
Given a finite set $A={a_1,ldots , a_k}$, consider the sequences of any length that can be constructed using the elements of $A$ and which contain no repetition, a repetition being a pair of consecutive subsequences (of any length) that are equal. Is it true that $k = 4$ is the minimum number of elements in $A$ that allows the construction of sequences of any length containing no repetition? Can anyone indicate a reference for this result, if true?
co.combinatorics symbolic-dynamics
edited 7 hours ago
YCor
29k486140
asked 9 hours ago
PiCoPiCo
412
New contributor
PiCo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
put on hold as off-topic by Emil Jeřábek, Jeremy Rickard, YCor, bof, Andrés E. Caicedo 28 mins ago
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Emil Jeřábek, Jeremy Rickard, bof
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
Given a finite set $A={a_1,ldots , a_k}$, consider the sequences of any length that can be constructed using the elements of $A$ and which contain no repetition, a repetition being a pair of consecutive subsequences (of any length) that are equal. Is it true that $k = 4$ is the minimum number of elements in $A$ that allows the construction of sequences of any length containing no repetition? Can anyone indicate a reference for this result, if true?
co.combinatorics symbolic-dynamics
edited 7 hours ago
YCor
29k486140
asked 9 hours ago
PiCoPiCo
412
New contributor
PiCo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Given a finite set $A={a_1,ldots , a_k}$, consider the sequences of any length that can be constructed using the elements of $A$ and which contain no repetition, a repetition being a pair of consecutive subsequences (of any length) that are equal. Is it true that $k = 4$ is the minimum number of elements in $A$ that allows the construction of sequences of any length containing no repetition? Can anyone indicate a reference for this result, if true?
co.combinatorics symbolic-dynamics
co.combinatorics symbolic-dynamics
edited 7 hours ago
YCor
29k486140
asked 9 hours ago
PiCoPiCo
412
New contributor
PiCo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 7 hours ago
YCor
29k486140
asked 9 hours ago
PiCoPiCo
412
New contributor
PiCo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 7 hours ago
YCor
29k486140
edited 7 hours ago
YCor
29k486140
edited 7 hours ago
YCor
29k486140
29k486140
asked 9 hours ago
PiCoPiCo
412
New contributor
PiCo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 9 hours ago
PiCoPiCo
412
asked 9 hours ago
PiCoPiCo
412
412
New contributor
PiCo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
PiCo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
PiCo is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
put on hold as off-topic by Emil Jeřábek, Jeremy Rickard, YCor, bof, Andrés E. Caicedo 28 mins ago
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Emil Jeřábek, Jeremy Rickard, bof
If this question can be reworded to fit the rules in the help center, please edit the question.
put on hold as off-topic by Emil Jeřábek, Jeremy Rickard, YCor, bof, Andrés E. Caicedo 28 mins ago
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Emil Jeřábek, Jeremy Rickard, bof
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Wikipedia has some examples of square-free sequences of infinite length (and therefore square-free words of arbitrary length) over alphabets with 3 letters.
https://en.wikipedia.org/wiki/Square-free_word
One example of an infinite square-free word over an alphabet of size 3 is the word over the alphabet {0,±1} obtained by taking the first difference of the Thue–Morse sequence.[6][7] That is, from the Thue–Morse sequence
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, ...
one forms a new sequence in which each term is the difference of two consecutive terms of the Thue–Morse sequence. The resulting square-free word is
1, 0, −1, 1, −1, 0, 1, 0, −1, 0, 1, −1, 1, 0, −1, ... (sequence A029883 in the OEIS).
answered 9 hours ago
user44191user44191
3,21511634
$endgroup$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Wikipedia has some examples of square-free sequences of infinite length (and therefore square-free words of arbitrary length) over alphabets with 3 letters.
https://en.wikipedia.org/wiki/Square-free_word
One example of an infinite square-free word over an alphabet of size 3 is the word over the alphabet {0,±1} obtained by taking the first difference of the Thue–Morse sequence.[6][7] That is, from the Thue–Morse sequence
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, ...
one forms a new sequence in which each term is the difference of two consecutive terms of the Thue–Morse sequence. The resulting square-free word is
1, 0, −1, 1, −1, 0, 1, 0, −1, 0, 1, −1, 1, 0, −1, ... (sequence A029883 in the OEIS).
answered 9 hours ago
user44191user44191
3,21511634
$endgroup$
add a comment |
$begingroup$
Wikipedia has some examples of square-free sequences of infinite length (and therefore square-free words of arbitrary length) over alphabets with 3 letters.
https://en.wikipedia.org/wiki/Square-free_word
One example of an infinite square-free word over an alphabet of size 3 is the word over the alphabet {0,±1} obtained by taking the first difference of the Thue–Morse sequence.[6][7] That is, from the Thue–Morse sequence
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, ...
one forms a new sequence in which each term is the difference of two consecutive terms of the Thue–Morse sequence. The resulting square-free word is
1, 0, −1, 1, −1, 0, 1, 0, −1, 0, 1, −1, 1, 0, −1, ... (sequence A029883 in the OEIS).
answered 9 hours ago
user44191user44191
3,21511634
$endgroup$
add a comment |
$begingroup$
Wikipedia has some examples of square-free sequences of infinite length (and therefore square-free words of arbitrary length) over alphabets with 3 letters.
https://en.wikipedia.org/wiki/Square-free_word
One example of an infinite square-free word over an alphabet of size 3 is the word over the alphabet {0,±1} obtained by taking the first difference of the Thue–Morse sequence.[6][7] That is, from the Thue–Morse sequence
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, ...
one forms a new sequence in which each term is the difference of two consecutive terms of the Thue–Morse sequence. The resulting square-free word is
1, 0, −1, 1, −1, 0, 1, 0, −1, 0, 1, −1, 1, 0, −1, ... (sequence A029883 in the OEIS).
answered 9 hours ago
user44191user44191
3,21511634
$endgroup$
Wikipedia has some examples of square-free sequences of infinite length (and therefore square-free words of arbitrary length) over alphabets with 3 letters.
https://en.wikipedia.org/wiki/Square-free_word
One example of an infinite square-free word over an alphabet of size 3 is the word over the alphabet {0,±1} obtained by taking the first difference of the Thue–Morse sequence.[6][7] That is, from the Thue–Morse sequence
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, ...
one forms a new sequence in which each term is the difference of two consecutive terms of the Thue–Morse sequence. The resulting square-free word is
1, 0, −1, 1, −1, 0, 1, 0, −1, 0, 1, −1, 1, 0, −1, ... (sequence A029883 in the OEIS).
answered 9 hours ago
user44191user44191
3,21511634
edited 3 hours ago
answered 9 hours ago
user44191user44191
3,21511634
answered 9 hours ago
user44191user44191
3,21511634
answered 9 hours ago
user44191user44191
3,21511634
3,21511634
add a comment |
add a comment |
