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

2, 4, 8, 16, 32, 64, 126, 247, 480, 926, 1764, 3337, 6208, 11408, 20608, 36649, 63976, 109866, 185012, 306285, 497190, 792920, 1241936, 1913566, 2898574, 4323980, 6353060, 9206137, 13158574, 18576644, 25906122, 35732157, 48752228, 65865024, 88127370, 116877787, 153675644, 200476056

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

Johan Chrisnata, Han Mao Kiah, Sankeerth Rao, Alexander Vardy, Eitan Yaakobi, Hanwen Yao, On the Number of Distinct k-Decks: Enumeration and Bounds, 19th International Symposium on Communications and Information Technologies (ISCIT 2019, Ho Chi Minh City, Viet Nam) 519-524.

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: A069050 A343844 A059174 * A235701 A054044 A325741

Adjacent sequences: A258582 A258583 A258584 * A258586 A258587 A258588

Keyword

nonn

Author

Jeffrey Shallit, Nov 06 2015

Extensions

a(17)-a(38) from Han Mao Kiah, May 25 2020

Status

approved