Algorithms for the exact solution of the problems of enumeration, coding, and generation of serial sequences (Q2714068)

The author studies the sets of finite binary and serial sequences of a specific structure. These sets are defined by constraints on the structure of the set of elements in sequences. The typical examples of serial sequences appear in molecular biology, structural chemistry, theory of information, and other areas under the description of experiment data, coding, and enumeration. Let \(X\) be the set of serial sequences of a given structure and let \(x = (x_i\mid x_i\in \{0,1,\dots, n-1\},\;i = 1, 2,\dots, m)\) be a sequence in \(X\). The author discusses the following problems: find the number \(|X|\) of distinct representatives \(x\in X\) (enumeration problem); indicate how to map the sequences \(x\in X\) into the set \(\{0,1,\dots,|X|- 1\}\) (enumeration coding); construct the inverse mapping for reconstructing the elements \(x_i\in x\) with zero error.NEWLINENEWLINENEWLINEThe aim of the article under review is to solve the above-mentioned problems. It is proven that for some basic types of these sequences there exist generalized formulas for the exact solution of the enumeration problem without resort to generating functions. A generalized algorithm is exposed for coding and generation of the binary serial sequences with structures determined by limitations on the number of series of unities, on the weight of the sequence, on the length of the series of unities, and on the lengths of the series of zeros.