login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A258585 Number of equivalence classes of 3-binomial 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 3-binomial equivalent if the word binomial coefficients (x|r) and (y|r) coincide for all words r of length 1,2, and 3.  A word binomial coefficient (x|r) 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), 47-57.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 22 08:46 EST 2019. Contains 329389 sequences. (Running on oeis4.)