This site is supported by donations to The OEIS Foundation. 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 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.

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