login
A306688
Number of length-n binary strings achieving the maximum possible subword complexity.
0
2, 2, 6, 8, 4, 36, 42, 48, 40, 16, 558, 718, 854, 920, 956, 960, 912, 704, 256, 79006, 107152, 140502, 177840, 218652, 259266, 297280, 330560, 358048, 378616, 381664, 371104, 353280, 310016, 263168, 188416, 65536
OFFSET
1,1
COMMENTS
The subword complexity function rho_i (w) counts the distinct (contiguous) subwords of length i in the word w. The maximum complexity function is max_{1 <= i <= |w|} rho_i (w). For length-n words w of maximum complexity, it is known that the maximum is attained by counting subwords of length i+1 when 2^i + i <= n <= 2^{i+1} + i (sequence A103354).
LINKS
M-C. Anisiu, Z. Blazsik, Z. Kasa, Maximal Complexity of Finite Words, Pure Math. Appl., 13, 1-2 (2002) 39-48; arXiv:1002.2724 [cs.DM], 2010.
CROSSREFS
Cf. A103354.
Sequence in context: A284748 A134457 A326479 * A092522 A116542 A231131
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Mar 05 2019
STATUS
approved