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,2

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

Links

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

Example

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

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

Prog

(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

Crossrefs

Sequence in context: A205579 A089047 A133498 * A292200 A249576 A097600

Adjacent sequences: A282946 A282947 A282948 * A282950 A282951 A282952

Keyword

nonn,more

Author

Jeffrey Shallit, Feb 25 2017

Extensions

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

Status

approved