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, 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

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