3. Lexicographic sequence
1. The structure of the sequence. In Section 2 we arranged the Motzkin words in the image and likeness of natural numbers. Let's call the infinite ordered set of normalized Motzkin words
the Motzkin Row. In (3.1), each item is placed in a specific place. For example, in Section 1 the Motzkin word (1.1) is written as follows s1,418,009 = ((000)0(000)00)00. And it's easily to check using the connected software service . In on-line mode, the reader can receive the items of the Motzkin Row in any index interval specifying the initial index and the number of elements. The tableau below shows the first 130 elements (the indices start with 1). For better orientation, some cells are numbered; in addition, the cells with indices equal to Motzkin numbers are colored yellow.
Let us return to the Natural Number Series (see (2.4) in Section 2).
In each k-bit range (or
Like natural numbers, the elements of the Motzkin Row are compactly grouped
into character ranges along the size of the code.
In the tableau above, the Motzkin numbers are indices for the maxima (colored cells).
Or say so, the rth Motzkin number indexes the
Since the Motzkin Row is a chain and the ranges do not intersect, we can write the equality
2. Item with index 0: to be or not to be? Let us explain why we describe the Motzkin Row in detail. In the Motzkin Row, each element is assigned a unique index, and this index is a natural number. The Natural Number Series is self-indexed, here the index of the item is equal to its value. Evidently, there is a one-to-one correspondence (a bijection) between the two sequences. We can say that the Natural Number Series indexes the Motzkin Row. And we also add that the Motzkin numbers index the maxima in the ranges of the Motzkin Row.
Let's return to the Motzkin number M0,
which we proposed to accept as 0 (see Section 1), but which according to
OEIS A001006 is equal to 1.
Suppose we included the empty word s0 = ∅
in the Motzkin Row; at the same time, we are obliged to include zero in the Natural Number Series.
This means that at the beginning of the sequence, we added the virtual 0-range consisting of
a single element without "building blocks" (no parentheses and zeros),
Recall that in Section 1, we denoted by Un the number of unique  n-CPSZ (beginning with the left parenthesis). And this value is equal to the cardinality of the n-range in the Motzkin Row, that is,
The cardinality of the n-range decreases with decreasing n,
and at the lower stages of the Motzkin Row the 1-range and the 2-range are equally powerful:
The 0-range is empty (obviously, all previous ranges are also empty if there were such), and we again confirm the sequence (1.3). Thus, we exclude an empty element from the Motzkin Row, but we can talk about the empty 0-range (the empty set of elements of zero length). Note that we get M0 = 0 regardless of whether zero is included in the Natural Number Series or not.
A record of the form M0 = 0 is not informative; the fact of the absence of virtual elements is simply of no interest to anyone. Somehow, for mathematical objects, the missing attributes are not declared (usually we do not talk about what really does not exist). The Motzkin number M0 is useless, so there is no need to include it in the sequence. Let's delete this Motzkin number from the sequence, as a result we get a shortened sequence in which the elements are indexed starting from 1:
3. Something about the index series. Recall that the Natural Number Series and the Motzkin Row have an identical structure. These series are infinite and have an infinite number of character ranges. Additionally, for both series, the following rules are fulfilled:
- no duplicates;
- elements are ordered in ascending code size (external sorting);
- in each group of elements with the same code size, a strict lexicographic order is introduced (internal sorting).
The external sorting groups the elements along the size of the code, the elements with shorter codes are placed closer to the beginning of the series. The internal sorting lexicographically arranges elements in groups. Series in which these conditions are met, we call lexicographic sequence. Apparently, the Natural Number Series and the Motzkin Row are not the only such type. For example, in items of the Motzkin Row, you can remove all zeros, then remove the duplicates that appeared, and finally remove the empty item (the trace of 1-CPSZ "0"). As a result, we get a new series, the Dick Row, consisting of Dick words and ordered according to the rules of the lexicographic series.
Above we noted that the Natural Number Series is self-indexing, the index of a natural number coincides with its value, that is,
The k-maximum of the Motzkin Row (the maximum element of size k) is indexed by the k-th Motzkin number. If we select the indices of all the maxima, we get the sequence A001006 (without M0). For an arbitrary lexicographic sequence A, call the sequence of maximal element indices the index series I(A). The sequence of Motzkin numbers (without M0) can be written as I(S).
If A is a lexicographic sequence, then obviously the series I(A) is also lexicographic, and for A there is an index series of second order
For a numerical lexicographic sequence A, it is logical to assume I0(A) = A (i.e., the index series of null-order coincides with the original series). It is interesting when the index series of different orders coincide. In this case we can talk about the periodicity of index series.
Example 3.1. For the Natural Number Series the first-order index series has the following form:
It is easy to see that the index series for (4.1) coincides with the Natural Number Series, that is,
Thus, for a Natural Number Series, all index series of even order coincide (we assume that zero is even). Index series of odd order coincide too. The same is true for the lexicographic sequence (3.4). Consequently, for the natural series and the series (3.4), the index periodicity is equal to 2.