VOOZH about

URL: https://oeis.org/A258585

⇱ A258585 - OEIS

login
A258585
Number of equivalence classes of 3-binomial complexity for binary words of length n.
3
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
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
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Nov 06 2015
EXTENSIONS
a(17)-a(38) from Han Mao Kiah, May 25 2020
STATUS
approved