Reconstruction of sequences (Q1182969): Difference between revisions

Every sequence of length \(n\) determines \(n\choose k\) subsequences of length \(k\). The authors investigate the relationship between such subsequences and the original sequence. In particular they consider the problem of reconstructing an \(n\)-sequence from its subsequences of length \(k\) --- an interesting problem apparently first raised by \textit{L. I. Kalashnik} [The reconstruction of a word from fragments, Numerical mathematics and computer technology, Akad. Nauk Ukrain. SSR, Inst. Mat., Preprint IV, 56-57 (1973)]. Among other results, the paper under review contains a proof that for \(n>7\) and \(k\geq[n/2]\) the subsequences uniquely determine the original sequence, and for \(k<\log_ 2 n\) they do not.