A306688 Number of length-n binary strings achieving the maximum possible subword complexity.

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

Table of n, a(n) for n=1..36.

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

Adjacent sequences: A306685 A306686 A306687 * A306689 A306690 A306691

Keyword

nonn,more

Author

Jeffrey Shallit, Mar 05 2019

Status

approved