A335892 Smallest value of N such that two distinct binary words of length N share the same n-deck.

2, 4, 7, 12, 16, 30

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

Table of n, a(n) for n=1..6.

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

Cf. A258585, A335890, A335891.

Sequence in context: A362652 A266186 A306673 * A181020 A049631 A239955

Adjacent sequences: A335889 A335890 A335891 * A335893 A335894 A335895

Keyword

nonn,hard,more

Author

Han Mao Kiah, Jun 28 2020

Status

approved