Efficient reconstruction of sequences from their subsequences of supersequences (Q5930025): Difference between revisions

Let \(X\) be a sequence of length \(n\) of elements of a \(q\)-element set. The following two questions are considered: (1) Given \(N_1\) subsequences of \(X\) of length \(n-t\), is it possible to reconstruct \(X\)? (2) Given \(N_2\) supersequences of \(X\) of length \(n+t\), is it possible to reconstruct \(X\)? Clearly, positive answers to these questions are only possible if \(N_1\) and \(N_2\) are large enough. If \(n,q,t\) are fixed, what are the minimum possible numbers for \(N_1\) and \(N_2\), respectively, such that the reconstruction problem has a positive answer? These numbers are explicitly determined in this paper. Quite obviously, to find these numbers required a lot of imagination. For question (1) the answer is recursive, while for question (2) an explicit formula in terms of a binomial sum is given. Moreover, for both cases an algorithm is provided that solves the reconstruction problem. This is part of a theory developed in another paper of the author [IEEE Trans. Inform. Theory 47, 2-22 (2001)]. Reviewer's remark: The author overlooks that it is also easy to provide an explicit formula for the desired number for question~(1). To be precise, if in Eq.~(16) the geometric series on the left-hand side are summed and subsequently the binomial theorem is applied to the powers of \((1-z^q)\) and \((1-z)\), respectively, then the formula \[ D_q(n,t)=\sum _{k=0} ^{\lfloor t/q\rfloor}(-1)^k\binom {n-t}k\binom {n-qk}{n-t} \] is obtained on comparing coefficients of powers of \(z\) on both sides. If this is substituted in Eq.~(28), the desired explicit formula results.