A282949 Number of distinct subword complexity profiles for binary strings of length n.

1, 2, 2, 3, 4, 5, 7, 9, 13, 18, 25, 34, 48, 67, 97, 134, 191, 258, 374, 521, 738, 1024, 1431, 1972, 2755, 3785, 5244, 7223, 9937, 13545, 18597, 25360, 34500

Offset: 1

Author

Jeffrey Shallit, Feb 25 2017

Keywords

• nonn
• more

Comments

The subword complexity function p_i(w) maps i to the number of distinct contiguous blocks (aka subwords, aka factors) of length i in a word w. The subword complexity profile of a word of length n is the list (p_1 (w), p_2 (w), ..., p_n (w)).

Examples

			For n = 6 the 5 distinct profiles are (1,1,1,1,1,1) (for the word 000000); (2,2,2,2,2,1) (for the word 000001); (2,3,3,3,2,1) (for the word 000010); (2,3,4,3,2,1) (for the word 000100); and (2,4,4,3,2,1) (for the word 000110).
		

Programs

Mathematica

prof[w_] := Table[ Length@ Union@ Partition[w, k, 1], {k, Length@w}]; a[n_] := Length@ Union[prof /@ Tuples[{0, 1}, n]]; Array[a, 12] (* Giovanni Resta, Feb 25 2017 *)

Python

from itertools import product
def p(i, w): return len(set(w[j:j+i] for j in range(len(w)-i+1)))
def scp(w): return tuple(p(i, w) for i in range(1, len(w)+1))
def a(n):
    return len(set(scp("0"+"".join(w)) for w in product("01", repeat=n-1)))
print([a(n) for n in range(1, 16)]) # Michael S. Branicky, Mar 20 2022

Extensions

a(26)-a(33) from Lars Blomberg, Mar 13 2017