1,1

Two words x, y are 5-binomial equivalent if the word binomial coefficients (x|r) and (y|r) coincide for all words r of length 5. A word binomial coefficient (x|r) gives the number of times the word r appears as a (not necessarily contiguous) subsequence of x. Observe that if (x|r) and (y|r) coincide for all words r of length 5, then (x|r') and (y|r') coincide for all words r' of length at most 5.

The integer-valued vector (x|r)_r where the index r runs through all possible binary words of length 5 is referred to as the 5-deck of x. Hence, the number of distinct 5-decks is equal to the number of equivalence classes.

C. Chorut, J. Karhumäki, "Combinatorics of words," in: G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, vol. I, Springer, Berlin, 1997, pp. 329-438.

L. O. Kalashnik, "The reconstruction of a word from fragments," Numerical Mathematics and Computer Technology, Akad. Nauk. Ukrain. SSR Inst. Mat., Preprint IV (1973): 56-57.

P. Ligeti and P. Sziklai, "Reconstruction from subwords," in 6th International Conference on Applied Informatics, Jan. 2004, pp. 1-7.

J. Chrisnata, H. M. Kiah, S. Rao, A. Vardy, E. Yaakobi, H. 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. Dudik and L. J. Schulman, Reconstruction from subsequences, Journal of Combinatorial Theory, vol. 103, no. 2, pp. 337-348, 2003.

I. Krasikov and Y. Roditty, On a reconstruction problem for sequences, Journal of Combinatorial Theory, vol. 77, no. 2, pp. 344-348, 1997.

B. Manvel, A. Meyerowitz, A. Schwenk, K. Smith, and P. Stockmeyer, Reconstruction of sequences, Discrete Math, vol. 94, no. 3, pp. 209-219, 1991.

M. Rigo and P. Salimov, Another generalization of abelian equivalence: Binomial complexity of infinite words, Theoretical Computer Science 601 (2015), 47-57.

A. D. Scott, Reconstructing sequences, Discrete Mathematics, vol. 175, no. 1-3, pp. 231-238, 1997.

For n=16, all words are an equivalence class by themselves, with the exception of {0111100011111001, 1001111100011110} and {1000011100000110, 0110000011100001}. So there are 2^16 - 2 = 65534 equivalence classes, or, 65534 distinct 4-decks.

Cf. A258585, A335890.

Sequence in context: A392142 A370748 A118655 * A249169 A247208 A325744

Adjacent sequences: A335888 A335889 A335890 * A335892 A335893 A335894

Han Mao Kiah, Jun 28 2020

approved