Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #22 May 25 2020 07:51:54
%S 2,4,8,16,32,64,126,247,480,926,1764,3337,6208,11408,20608,36649,
%T 63976,109866,185012,306285,497190,792920,1241936,1913566,2898574,
%U 4323980,6353060,9206137,13158574,18576644,25906122,35732157,48752228,65865024,88127370,116877787,153675644,200476056
%N Number of equivalence classes of 3-binomial complexity for binary words of length n.
%C 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.
%H Johan Chrisnata, Han Mao Kiah, Sankeerth Rao, Alexander Vardy, Eitan Yaakobi, Hanwen Yao, <a href="https://doi.org/10.1109/ISCIT.2019.8905191">On the Number of Distinct k-Decks: Enumeration and Bounds</a>, 19th International Symposium on Communications and Information Technologies (ISCIT 2019, Ho Chi Minh City, Viet Nam) 519-524.
%H M. Rigo and P. Salimov, <a href="http://dx.doi.org/10.1016/j.tcs.2015.07.025">Another generalization of abelian equivalence: Binomial complexity of infinite words</a>, Theoretical Computer Science 601 (2015), 47-57.
%e 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.
%e 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 + ...
%K nonn
%O 1,1
%A _Jeffrey Shallit_, Nov 06 2015
%E a(17)-a(38) from _Han Mao Kiah_, May 25 2020