A335891 Number of equivalence classes of 5-binomial complexity for binary words of length n. Or, equivalently, the number of distinct 5-decks of binary words of length n.

2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65534, 131064, 262120, 524212, 1048360, 2096586, 4192896, 8385216, 16769254, 33536094, 67067294, 134124596, 268228914, 536416730, 1072750464

Offset

1,1

Comments

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.

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=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.

Crossrefs

Cf. A258585, A335890.

Sequence in context: A323830 A370748 A118655 * A249169 A247208 A325744

Adjacent sequences: A335888 A335889 A335890 * A335892 A335893 A335894

Keyword

nonn

Author

Han Mao Kiah, Jun 28 2020

Status

approved