1. Introduction
2. Numbers and brackets
3. Lexicographic sequence
4. Navigation
5. Service on-line

      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  =  { si }, 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  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 k-range) there are the minimum item consisting of a 1 and  k–1 0s, and the maximum item consisting of  k 9s. The length (cardinality) of the k-range is equal to the difference between the maximum elements of the k-range and the (k–1)-range. With decrease bit capacity, the maximum element loses 9s, and the minimal element loses 0s. By decreasing the digit capacity by one, the range cardinality is reduced tenfold. In the lowest single-digit range, the minimum element is left without zeros.

Like natural numbers, the elements of the Motzkin Row are compactly grouped into character ranges along the size of the code. Each r-character range (r-range) is a subset  Sr with a minimum item, min Sr or r-minimum, and a maximum item, max Sr or r-maximum. The minima is similar in all ranges: it is a sequence of zeros bounded by parentheses; for example,  min S7 = (00000). In the even 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,  max S8 = ()()()(). To get the maxi­mum of the odd r-range (r is odd and  r >2), just add a 0 to  max Sr–1. In a singleton subset (the 1-range and the 2-range), the maximum and minimum coincide.

In the tableau above, the Motzkin numbers are indices for the maxima (colored cells). Or say so, the rth Motzkin number indexes the r-maximum. This follows directly from (1.4) (see Section 1). Let's write it as follows

Mr =  ind (max Sr),  r ≥ 1.

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

ind (min Sr)  =  Mr–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 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), that is,  S0 = { ∅ }. The element  ∅  is both a minimum and a maximum, and the cardinality of  S0 is equal to  M0 = 1. So in the Motzkin Row, we already get three singleton ranges  S0, S1, S2  (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 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,

| Sn |  =  Un  =  MnMn–1  or  Mn–1 = MnUn.

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:  U1= U2= 1. Hence we obtain a zero value for the initial number of Motzkin:

M0  =  M1U1  =  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  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:

1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, ...

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:

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,  aN.

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

I(I(A))  =  I2(A).

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:

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))  =  I2(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.



<<   Numbers and brackets   ||   Navigation  >>