

A258585


Number of equivalence classes of 3binomial complexity for binary words of length n


0



2, 4, 8, 16, 32, 64, 126, 247, 480, 926, 1764, 3337, 6208, 11408, 20608, 36649
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Two words x, y are 3binomial equivalent if the word binomial coefficients (xr) and (yr) coincide for all words r of length 1,2, and 3. A word binomial coefficient (xr) gives the number of times the word r appears as a (not necessarily contiguous) subsequence of x.


LINKS

Table of n, a(n) for n=1..16.
M. Rigo and P. Salimov, Another generalization of abelian equivalence: Binomial complexity of infinite words, Theoretical Computer Science 601 (2015), 4757.


EXAMPLE

For n=7 all words are an equivalence class by themselves, with the exception of {0110001,1000110} and {0111001,1001110}. So there are 2^7  2 = 126 equivalence classes.
G.f. = 2*x + 4*x^2 + 8*x^3 + 16*x^4 + 32*x^5 + 64*x^6 + 126*x^7 + 247*x^8 + ...


CROSSREFS

Sequence in context: A302934 A069050 A059174 * A235701 A054044 A325741
Adjacent sequences: A258582 A258583 A258584 * A258586 A258587 A258588


KEYWORD

nonn,more


AUTHOR

Jeffrey Shallit, Nov 06 2015


STATUS

approved



