A282949 - OEIS

%I #20 Mar 20 2022 18:29:01

%S 1,2,2,3,4,5,7,9,13,18,25,34,48,67,97,134,191,258,374,521,738,1024,

%T 1431,1972,2755,3785,5244,7223,9937,13545,18597,25360,34500

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

%C 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)).

%e 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).

%t 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 *)

%o (Python)

%o from itertools import product

%o def p(i, w): return len(set(w[j:j+i] for j in range(len(w)-i+1)))

%o def scp(w): return tuple(p(i, w) for i in range(1, len(w)+1))

%o def a(n):

%o     return len(set(scp("0"+"".join(w)) for w in product("01", repeat=n-1)))

%o print([a(n) for n in range(1, 16)]) # _Michael S. Branicky_, Mar 20 2022

%K nonn,more

%O 1,2

%A _Jeffrey Shallit_, Feb 25 2017

%E a(26)-a(33) from _Lars Blomberg_, Mar 13 2017