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

            2. Numbers and brackets

The set of Motzkin words of size  k, k >1, contains two types of elements: the  (k–1)-CPSZs with an additional leading zero (inherited elements), and unique  k-CPSZs begining with the left parenthesis. Once I saw all nine 4-CPSZs in the following order:

0000, ()00, 0()0, 00(), (0)0, 0(0), (00), ()(), (()).

Four inherited Motzkin words with leading zero are highlighted in red. As you can see, these elements are scattered in (2.1). There is a desire to place inherited 4-CPSZs compactly and at the top of the list. Let's do it:

0000, 0()0, 00(), 0(0), ()00, (0)0, (00), ()(), (()).

Next, if we want to introduce operations on expressions with parentheses (why not?!), then in Motzkin words, the leading zeros will become "ballast". Let's draw an analogy with natural numbers. In arithmetic expressions, usually we do not indicate the leading zeros in numbers; for example, no one writes  111− 072  or a completely uncomfortable  00111− 00072. Removing leading zeros in numbers, we abstract from the fixed bit capacity. If we remove the leading zeros in the Motzkin words, then, for example, in the case of rectangular lattices, we abstract from the width of the lattices. We rewrite the elements in (2.2) in a normalized form, without leading zeros.

0, ()0, (), (0), ()00, (0)0, (00), ()(), (()).

Naturally, in the first element, one zero must be saved, and this is the only Motzkin word starting with zero. The other normalized items (this list can be continued indefinitely) begin with the left parenthesis. Note, there are no inherited Motzkin words in (2.3). It's easy to see that the list is not organized, and you need to sort the items. Let  S  denote an ordered list of normalized Motzkin words. We put the items of  S  into a chain, in other words, we need to establish a strict total order  "<"  on  S. We show that for any  a, bS  (a ≠ b either  a < b  or  b < a .

Let's continue the analogy with natural numbers (assume zero is not a natural number). At a formal level, we will analyze a Natural Number Series

N  =  { 1, 2, …, 9,   10, 11, …, 99,   100, 101, …, 999, … }.

A positive integer takes its place in accordance with the two rules. Firstly, all  k-digit integers are located compactly in their digital range to the right of integers with a bit capacity less than  k  and to the left of integers with a bit capacity greater than  k. In (2.4) the intervals between digital ranges are increased. And secondly, within each range of numbers of the same length, there is a lexicographic order that is established by the following system of inequalities for decimal digits:

0 < 1 < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9.

Let's use similar template to build a strict order on the set  S. First of all, we sort the norma­lized Motzkin words by their size. The shortest 1-CPSZ "0" (an analog of the one-digit natural numbers) is only one, the others with this size do not exist. So we start the chain with the item "0" and assign the index 1 to it. The 2-CPSZ "( )" (an analog of the two-digit natural numbers) is also alone, so a pair of adjacent parentheses is placed in the chain at the next second position.

In the three-character range, there are two elements "( )0", "(0)". And here the lexicographic order is already necessary. We establish the strict order for the alphabet signs of Motzkin words by means of inequalities

0  <  (  <  ).

The inequalities (2.5) are quite logical and that's why. A chain of normalized Motzkin words begin with zero, so it is natural to consider zero as the smallest sign, or the alphabet symbol with a minimum weight. The other elements of set  S  begin with the left parenthesis, and therefore in the chain (2.5) this symbol is specified by the second. As a result, the items "(0)" and "() 0" are placed in  S  at the 3rd and 4th positions, respectively. The remaining elements in (2.3) are easy to build in a chain. Now we can show the first ranges of the normalized Motzkin words.

S  =  { 0,  (),  (0), ()0,  (00), (0)0, (()), ()00, ()(),  (000), …, ()()0, … }

Of course, you can choose a different order on the alphabet of Motzkin words. In the literature we find various sorting options, mention one of them. Here is a drawing, that we borrowed from Robert M. Dickau. реш-4 Nine paths of length 4 correspond to the considered Motzkin words, but the paths are given in the reverse order to (2.6). We can assume that the author adhered to the inverse system of inequalities  0 > ( > ). Of course, in each specific case, the order of enumeration of Motzkin words (normalized or not) may not have practical significance. Much depends on the nature and characteristics of the problem being solved. Nevertheless, in any set, the selection (or viewing) of the elements should carried out somehow. It is better to do such operations simply, quickly, conveniently, and reliably. In this respect, a Natural Number Series is ideal and unique: here the index of the element coincides with its value. Perhaps due to this ordering, the Natural Number Series has become so famous and popular. We can say that this series is the Foundation of mathematics. Certain dependences also exist for the elements of the set of normalized Motzkin words. We will talk about this in the following sections.

In this article, it is proposed to arrange Motzkin words in the image and likeness of natural numbers, thereby maximally approximate the new sequence to the series of natural numbers. First, it is suggested to regroup and pack Motzkin words of arbitrary size. Further, the Motzkin words are arranged in a chain according to the pattern of natural numbers. As a result, the simple and convenient strict order is introduced on the set of Motzkin words. We note four stages of constructing of such order:


<<   Introduction   ||   Lexicographic sequence   >>