## 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

*S*= {

*s*},

_{i}*i*≥ 1,

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
*s*_{1,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 *k-range**k*–1*k* 9s*cardinality*) of the *k*-range*k*-range*k*–1)-range

Like natural numbers, the elements of the Motzkin Row are compactly grouped
into character ranges along the size of the code.
Each *r*-character*r-*range*S _{r}* with a minimum item,

*S*

_{r}*r-minimum*

*S*

_{r}*r-maximum*

*S*

_{7}= (00000)

*r*-range

*r*is even), the maximum is a sequence of pair of adjacent parentheses without a finite zero (the number of pairs is equal to

*r*/2); for example,

*S*

_{8}= ()()()()

*r*-range

*r*is odd and

*r*>2), just add a 0 to

*S*

_{r–1}

In the tableau above, the Motzkin numbers are indices for the maxima (colored cells).
Or say so, the *r*th Motzkin number indexes the *r*-maximum

*M*= ind (max

_{r}*S*

_{r}),

*r*≥ 1.

Since the Motzkin Row is a chain and the ranges do not intersect, we can write the equality

*S*

_{r}) =

*M*

_{r–1}+ 1,

*r*> 1.

**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 *M*_{0},
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 *s*_{0} = ∅
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),
that is, *S*_{0} = { ∅ }*S*_{0} is equal to *M*_{0} = 1*S*_{0}, *S*_{1}, *S*_{2} (not too much?).
Let us explain why such a construction is problematic and most likely impossible in our case.

Recall that in Section 1, we denoted by *U _{n}* 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,

*S*| =

_{n}*U*=

_{n}*M*−

_{n}*M*

_{n–1}or

*M*

_{n–1}=

*M*−

_{n}*U*.

_{n}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:
*U*_{1}= *U*_{2}= 1

*M*

_{0}=

*M*

_{1}−

*U*

_{1}= 1 − 1 = 0.

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 *M*_{0} = 0
regardless of whether zero is included in the Natural Number Series or not.

A record of the form *M*_{0} = 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 *M*_{0} 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,

*a*= ind

*a*,

*a*∈

*N*.

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 *M*_{0}).
For an arbitrary lexicographic sequence *A*,
call the sequence of maximal element indices
the *index series* *I*(*A*).
The sequence of Motzkin numbers (without *M*_{0})
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*

*I*(

*I*(

*A*)) =

*I*

^{2}(

*A*).

For a numerical lexicographic sequence *A*, it is logical to assume
*I*^{0}(*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:

*I*(

*N*) = { 9, 99, 999, ... }.

It is easy to see that the index series for (4.1) coincides with the Natural Number Series, that is,

*I*(

*I*(

*N*)) =

*I*

^{2}(

*N*) =

*N*.

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.