OFFSET
1,1
COMMENTS
For a binary word x, its n-deck is the multiset of all its (not necessarily contiguous) subsequences.
For N < a(n), we can uniquely identify a word from its n-deck.
a(7) <= 50, a(8) <= 81, a(9) <= 131, a(10) <= 212.
REFERENCES
C. Chorut and 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
J. Chrisnata, H. M. Kiah, S. Rao, A. Vardy, E. Yaakobi and 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=1, the 1-decks of 01 and 10 are both {0,1}. In contrast, the 1-decks of 0 and 1 are {0} and {1}, respectively. Hence, a(1)=2.
For n=2, the 2-decks of 0110 and 1001 are both {00,01,01,10,10,11}.
For n=3, 01101001 and 10010110 have the same 3-deck.
For n=4, 011101001110 and 100111011001 have the same 4-deck.
For n=5, 0111100011111001 and 1001111100011110 have the same 5-deck.
For n=6, 011000001110000100011100000110 and 100001110000010110000011100001 have the same 6-deck.
PROG
(Python)
from collections import Counter
from itertools import combinations as combs, product
def ndeck(w, n):
out = Counter("".join(w[i] for i in c) for c in combs(range(len(w)), n))
return tuple(sorted(out.items()))
def a(n, verbose=False):
N = n + 1
while True:
ndecks = set()
for b in product("01", repeat=N):
bdeckn = ndeck(b, n)
if bdeckn in ndecks:
return N
ndecks.add(bdeckn)
if verbose: print("...", N, time()-time0)
N += 1
print([a(n) for n in range(1, 5)]) # Michael S. Branicky, Sep 20 2021
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Han Mao Kiah, Jun 28 2020
STATUS
approved