主题
Search

无重叠词

如果一个词不包含形如 xyxyx 的子词，则称其为无重叠词。无平方词是无重叠词，无重叠词是无立方词。

长度为 n=1, 2, ... 的二元无重叠词的数量 t(n) 为 2, 4, 6, 10, 14, 20, ... (OEIS A007777)。t(n) 满足

p·n^(1.155)<=t(n)<=q·n^(1.587)
(1)

对于某些常数 p 和 q (Restivo and Selemi 1985, Kobayashi 1988)。此外，虽然

lim_(n->infty)(lnt(n))/(lnn)
(2)

不存在，

1.155<T_L<1.276<1.332<T_U<1.587,
(3)

其中

T_L=liminf_(n->infty)(lnt(n))/(lnn)
(4)
T_U=limsup_(n->infty)(lnt(n))/(lnn)
(5)

(Cassaigne 1993)。

Thue-Morse 序列是无重叠的 (Allouche and Shallit 2003, p. 15)。

另请参阅

无立方词, 无平方词, 词

使用 Wolfram|Alpha 探索

参考文献

Allouche, J.-P. and Shallit, J. "Repetition in Words." §1.6 in Automatic Sequences: Theory, Applications, Generalizations. Cambridge, England: Cambridge University Press, pp. 14-16, 2003.Cassaigne, J. "Counting Overlap-Free Binary Words." In STACS '93: Tenth Annual Symposium on Theoretical Aspects of Computer Science, Würzburg, Germany, February 25-27, 1993 Proceedings (Ed. G. Goos, J. Hartmanis, A. Finkel, P. Enjalbert, K. W. Wagner). New York: Springer-Verlag, pp. 216-225, 1993.Cassaigne, J. Motifs évitables et régularités dans les mots (Thèse de Doctorat). Tech. Rep. LITP-TH 94-04. Paris: Institut Blaise Pascal, 1994.Finch, S. R. "Pattern-Free Word Constants." §5.17 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 367-371, 2003.Kobayashi, Y. "Enumeration of Irreducible Binary Words." Discrete Appl. Math. 20, 221-232, 1988.Restivo, A. and Salemi, S. "Overlap-Free Words on Two Symbols." In Automata on Infinite Words (Ed. M. Nivat and D. Perrin). New York: Springer-Verlag, pp. 198-206, 1985.Séébold, P. "Overlap-Free Sequences." In Combinatorics on Words (Ed. L. J. Cummings). Toronto: Academic Press, pp. 207-215, 1983.Sloane, N. J. A. Sequence A007777 in "The On-Line Encyclopedia of Integer Sequences."

在 Wolfram|Alpha 中被引用

无重叠词

请引用为

Weisstein, Eric W. "无重叠词。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/OverlapfreeWord.html

主题分类