Avoiding 2-binomial squares and cubes

作者：Rao Michael; Rigo Michel^*; Saimov Pavel

来源：Theoretical Computer Science, 2015, 572: 83-91.

DOI：10.1016/j.tcs.2015.01.029

• Combinatorics on words
• Binomial coefficient
• Binomial equivalence
• Avoidance
• Squarefree
• Cubefree

Two finite words u, v are 2-binomially equivalent if, for all words x of length at most 2, the number of occurrences of x as a (scattered) subword of u is equal to the number of occurrences of x in v. This notion is a refinement of the usual abelian equivalence. A 2-binomial square is a word uv where u and v are 2-binomially equivalent. In this paper, considering pure morphic words, we prove that 2-binomial squares (resp. cubes) are avoidable over a 3-letter (resp. 2-letter) alphabet. The sizes of the alphabets are optimal.

• 出版日期2015-3-23