|
|
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.
|
|
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 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
|
B. Manvel, A. Meyerowitz, A. Schwenk, K. Smith, and P. Stockmeyer, Reconstruction of sequences, Discrete Math, vol. 94, no. 3, pp. 209-219, 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 4-decks.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|