A note on the number of squares in a word
A note on the number of squares in a word
复制标题
关于单词中的方格数量的注释
DOI：
10.1016/j.tcs.2007.03.025
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Lucian Ilie
中科院分区：
文献类型：
--
作者：
Lucian Ilie
Fraenkel和Simpson [A.S.辛普森（J. Simpson）的《一个字符串可以包含多少个正方形？》（How many squares can a string contain？J. Combin。Theory Ser. A 82（1998）112-120]证明了长度为n的字的平方数有2n的界。在本注记中，我们将此界改进为2n-Θ（logn）。基于数值证据，约束界为n。
Fraenkel and Simpson [A.S. Fraenkel, J. Simpson, How many squares can a string contain? J. Combin. Theory Ser. A 82 (1998) 112–120] proved that the number of squares in a word of length n is bounded by 2n. In this note we improve this bound to 2n−Θ(logn). Based on the numerical evidence, the conjectured bound is n.