OFFSET
1,1
COMMENTS
Two words x, y are 4-binomial equivalent if the word binomial coefficients (x|r) and (y|r) coincide for all words r of length 4. 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 4, then (x|r') and (y|r') coincide for all words r' of length at most 4.
The integer-valued vector (x|r)_r where the index r runs through all possible binary words of length 4 is referred to as the 4-deck of x. Hence, the number of distinct 4-decks is equal to the number of equivalence classes.
REFERENCES
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.
LINKS
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.
EXAMPLE
For n=12, all words are an equivalence class by themselves, with the exception of {011101001110, 100111011001}, {011100101110, 100110111001}, {100010110001, 011000100110} and {100011010001, 011001000110}. So there are 2^12 - 4 = 4092 equivalence classes, or, 4092 distinct 4-decks.
CROSSREFS
KEYWORD
nonn
AUTHOR
Han Mao Kiah, Jun 28 2020
STATUS
approved