cp's OEIS Frontend

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

%I A282949 #20 Mar 20 2022 18:29:01
%S A282949 1,2,2,3,4,5,7,9,13,18,25,34,48,67,97,134,191,258,374,521,738,1024,
%T A282949 1431,1972,2755,3785,5244,7223,9937,13545,18597,25360,34500
%N A282949 Number of distinct subword complexity profiles for binary strings of length n.
%C A282949 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 A282949 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 A282949 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 A282949 (Python)
%o A282949 from itertools import product
%o A282949 def p(i, w): return len(set(w[j:j+i] for j in range(len(w)-i+1)))
%o A282949 def scp(w): return tuple(p(i, w) for i in range(1, len(w)+1))
%o A282949 def a(n):
%o A282949     return len(set(scp("0"+"".join(w)) for w in product("01", repeat=n-1)))
%o A282949 print([a(n) for n in range(1, 16)]) # _Michael S. Branicky_, Mar 20 2022
%K A282949 nonn,more
%O A282949 1,2
%A A282949 _Jeffrey Shallit_, Feb 25 2017
%E A282949 a(26)-a(33) from _Lars Blomberg_, Mar 13 2017