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

%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