主题
Search

无平方词

“平方”词由两个相同的相邻子词组成（例如，acbacb）。无平方词不包含任何平方词作为子词（例如，abcacbabcb）。唯一的无平方二进制词是 a, b, ab, ba, aba, 和 bab （因为 aa、bb、aaa、aab、abb、baa、bba 和 bbb 分别包含平方的相同相邻子词 a、b、a、a、b、a、b 和 b）。

然而，存在任意长的三元无平方词。长度为 n=1, 2, ... 的三元无平方词的数量 s(n) 为 1, 3, 6, 12, 18, 30, 42, 60, ... (OEIS A006156)，并且 s(n) 有界，界限为

6·1.032^n<=s(n)<=6·1.379^n

(Brandenburg 1983)。此外，

S=lim_(n->infty)[s(n)]^(1/n)=1.302...

(Brinkhuis 1983, Noonan 和 Zeilberger 1999)。

长度为 n=1, 2, ... 的四元无平方词的数量为 4, 12, 36, 96, 264, 696, ... (OEIS A051041)。

另请参阅

字母表, 无立方词, 无重叠词, 词

使用 Wolfram|Alpha 探索

参考文献

Allouche, J.-P. 和 Shallit, J. "Repetition in Words." §1.6 in Automatic Sequences: Theory, Applications, Generalizations. Cambridge, England: Cambridge University Press, pp. 14-16, 2003.Baake, M.; Elser, V.; 和 Grimm, U. "The Entropy of Square-Free Words." 8 Sep 1998. http://arxiv.org/abs/math-ph/9809010.Bean, D. R.; Ehrenfeucht, A.; 和 McNulty, G. F. "Avoidable Patterns in Strings of Symbols." Pacific J. Math. 85, 261-294, 1979.Berstel, J. 和 Reutenauer, C. "Square-Free Words and Idempotent Semigroups." In Combinatorics on Words (Ed. M. Lothaire). Reading, MA: Addison-Wesley, pp. 18-38, 1983.Brandenburg, F.-J. "Uniformly Growing kth Power-Free Homomorphisms." Theor. Comput. Sci. 23, 69-82, 1983.Brinkhuis, J. "Non-Repetitive Sequences on Three Symbols." Quart. J. Math. Oxford Ser. 2 34, 145-149, 1983.Crochemore, M. "Sharp Characterizations of Squarefree Morphisms." Theor. Comput. Sic. 18, 221-226, 1982.Crochemore, M. "Tests sur les morphismes faiblement sans carré." In Combinatorics on Words (Ed. L. J. Cummings). Toronto: Academic Press, pp. 63-89, 1983.Finch, S. R. "Pattern-Free Word Constants." §5.17 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 367-371, 2003.Kobayashi, Y. "Repetition-Free Words." Theor. Comput. Sci. 44, 175-197, 1986.Leconte, M. "kth Power-Free Codes." In Automata on Infinite Words (Ed. M. Nivat 和 D. Perrin). Berlin: Springer-Verlag, pp. 172-178, 1985.Noonan, J. 和 Zeilberger, D. "The Goulden-Jackson Cluster Method: Extensions, Applications, and Implementations." J. Differ. Eq. Appl. 5, 355-377, 1999.Pleasants, P. A. B. "Nonrepetitive Sequences." Proc. Cambridge Philos. Soc. 68, 267-274, 1970.Restivo, A. 和 Salemi, S. "Overlap-Free Words on Two Symbols." In Automata on Infinite Words (Ed. M. Nivat 和 D. Perrin). New York: Springer-Verlag, pp. 198-206, 1985.Sloane, N. J. A. Sequences A006156/M2550 和 A051041 in "The On-Line Encyclopedia of Integer Sequences."Thue, A. "Über unendliche Zeichenreihen." Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiana 7, 1-22, 1906. Reprinted in Nagell, T.; Selberg, A.; Selberg, S.; 和 Thalberg, K. (Eds.). Selected Mathematical Papers of Axel Thue. Oslo, Norway: Universitetsforlaget, pp. 139-158, 1977.Thue, A. "Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen." Norske Vid. Selsk. Skr. I, Mat. Nat. Kl. Christiana 1, 1-67, 1912. Reprinted in Nagell, T.; Selberg, A.; Selberg, S.; 和 Thalberg, K. (Eds.). Selected Mathematical Papers of Axel Thue. Oslo, Norway: Universitetsforlaget, pp. 413-477, 1977.

在 Wolfram|Alpha 中引用

无平方词

请按如下方式引用

Weisstein, Eric W. "无平方词。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/SquarefreeWord.html

主题分类