The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A335890 Number of equivalence classes of 4-binomial complexity for binary words of length n. Or, equivalently, the number of distinct 4-decks of binary words of length n. 2
 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4092, 8176, 16328, 32604, 65075, 129824, 258906, 516168, 1028448, 2048272, 4077316, 8111400, 16124458, 32034016, 63579386, 126076522, 249736704, 494124382, 976302888 (list; graph; refs; listen; history; text; internal format)
 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 Table of n, a(n) for n=1..30. 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 Cf. A258585. Sequence in context: A295081 A227843 A271482 * A219531 A168083 A221180 Adjacent sequences: A335887 A335888 A335889 * A335891 A335892 A335893 KEYWORD nonn AUTHOR Han Mao Kiah, Jun 28 2020 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 19 22:34 EDT 2024. Contains 374441 sequences. (Running on oeis4.)