

A335891


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


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Two words x, y are 5binomial equivalent if the word binomial coefficients (xr) and (yr) coincide for all words r of length 5. A word binomial coefficient (xr) gives the number of times the word r appears as a (not necessarily contiguous) subsequence of x. Observe that if (xr) and (yr) coincide for all words r of length 5, then (xr') and (yr') coincide for all words r' of length at most 5.
The integervalued vector (xr)_r where the index r runs through all possible binary words of length 5 is referred to as the 5deck of x. Hence, the number of distinct 5decks 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. 329438.
L. O. Kalashnik, "The reconstruction of a word from fragments," Numerical Mathematics and Computer Technology, Akad. Nauk. Ukrain. SSR Inst. Mat., Preprint IV (1973): 5657.
P. Ligeti and P. Sziklai, "Reconstruction from subwords," in 6th International Conference on Applied Informatics, Jan. 2004, pp. 17.


LINKS

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


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 4decks.


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



