A330127 Number of length-n binary words containing at most distinct 11 palindromes as subwords (including the empty word).

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 292, 270, 268, 276, 276, 288, 320, 340, 364, 388, 404, 428, 476, 512, 560, 610, 644, 692, 768, 840, 924, 1020, 1100, 1190, 1316, 1452, 1612, 1786, 1952, 2134, 2348, 2598, 2896, 3228, 3552, 3908, 4300, 4752, 5296

Offset

0,2

Comments

Asymptotically, a(n) ~ c*alpha^n, where alpha ~ 1.1127756842787054706297 is the largest positive real zero of X^7 - X - 1 and c ~ 20.665.

Links

Table of n, a(n) for n=0..49.

Gabriele Fici and Luca Q. Zamboni, On the least number of palindromes contained in an infinite word, Theor. Comput. Sci. 481 (2013), 1-8.

Lukas Fleischer, Jeffrey Shallit, Words With Few Palindromes, Revisited, arxiv preprint arXiv:1911.12464 [cs.FL], November 27 2019.

Formula

a(n) = -a(n - 1) - a(n - 2) - a(n - 3) - a(n - 4) - a(n - 5) + 2a(n - 6) + 4a(n - 7) + 5a(n - 8) + 5a(n - 9) + 5a(n - 10) + 5a(n - 11) + 2a(n - 12) - 3a(n - 13) + -6a(n - 14) - 8a(n - 15) - 8a(n - 16) - 8a(n - 17) - 7a(n - 18) - 3a(n - 19) + 3a(n - 21) + 4a(n - 22) + 4a(n - 23) + 4a(n - 24) + 3a(n - 25) + 2a(n - 26) + a(n - 27) for n >= 42.

Crossrefs

Sequence in context: A113699 A113010 A366855 * A292568 A354600 A056767

Adjacent sequences: A330124 A330125 A330126 * A330128 A330129 A330130

Keyword

nonn

Author

Jeffrey Shallit, Dec 02 2019

Status

approved