2. Numbers and brackets
The set of Motzkin words of size k, k >1, contains two types of elements:
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:
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
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
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
A positive integer takes its place in accordance with the two rules. Firstly,
Let's use similar template to build a strict order on the set S.
First of all, we sort the normalized Motzkin words by their size.
In the three-character range, there are two elements
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.
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.
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
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:
- in Motzkin words we remove the leading zeros (in each null-string we leave only one zero);
- delete duplicate items;
- sort the items into a chain in size, placing shorter Motzkin words at the beginning of the sequence;
- in each subset of words of the same size, we sort the elements in according to (2.5).