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

We continue the analogy between the Natural Number Series and the Motzkin Row, S. Any procedure for the transition from one natural number to another can be considered as navigation in a sequence of numbers. In mathematics, the choice of the next/preceding natural number (increment/decrement) is fundamental operation. These operations are defined on the whole Natural Number Series except for a single case (the smallest natural number has no predecessor). For the Motzkin Row, it is not difficult to obtain the next/previous element (except for the analogous case  s1= 0).

Natural numbers can be added and subtracted. In this section, we consider similar operations with elements of the Motzkin Row, procedures that resemble addition and subtraction of integers. In addition, simple procedures for modifying the Motzkin words are described. A permutation of a single parenthesis with a neighboring zero allows us to make "jumps" along the Motzkin Row.

1. Character arithmetic. Recall that in a Motzkin word, we can split brackets into pairs of bi-direc­tional parentheses, called matched pairs. Inside each matched pair there is either some Motzkin word or nothing (the case of adjacent parentheses). A matched pair and its contents are called a block. In the Motzkin word  a ∈ S  of the  n-range,  n ≥ 2,  let's select a block, replace all parentheses outside the block by zeros, and remove the leading zeros (if there are any). As a result, we get an extended block, the element  a' ∈ S  from the  n'-range. In general,  ind a' ≤ ind a  and  n' ≤ n.

Using the described procedure, we cut out an extended block  a'  from  a ∈ S. How to get the remainder  a″  of such an operation? It's very simple, in  a  you need to clean the processed block with zeros. Let's call this operation the extract (like subtraction for numbers) of a block from the Motzkin word and denote by ⊖. We call the inverse operation the overlay (like addition for numbers) of Motzkin words and denote by ⊕. Let's represent the performed actions with  a,a',a″ ∈ S  as follows:

aa' = a"  or  a'a" = a,  ind a ≥ max { ind a', ind a" }.

Obviously, if ind a" =1 (a" = s1 = 0), then ind a = ind a', that is, a = a'. Further, we will understand the extraction of expanded blocks as subtraction of Motzkin words. Similarly, we will identify the overlay of blocks and the addition of Motzkin words.

Example 4.1. Below we consider some variants of subtraction and addition of Motzkin words. For convenience, the processing blocks are marked in red. The last case (f) is special; blocks are not processed here. We will talk about this option separately.

(a)  ()0(0)0 ⊖ (0)0 = ()00000,   (0)0 ⊕ ()00000 = ()0(0)0;

(b)  ((0)0)000 ⊖ ((0)0)000 = 0,   ((0)0)000 ⊕ 0 = ((0)0)000;

(c)  (())()00 ⊖ (())0000 = ()00,   (())0000 ⊕ ()00 = (())()00;

(d)  ()(0())(0) ⊖ (0())000 = ()00000(0),   (0())000 ⊕ ()00000(0) = ()(0())(0);

(e)  ()0(0())(0) ⊖ ()0000 = ()0(000)(0),   ()0000 ⊕ ()0(000)(0) = ()0(0())(0);

(f)  (()) ⊖ (0) = (0)0,   (0) ⊕ (0)0 = (()).
■

In Motzkin words, character arithmetic is performed character-by-symbol from the end of the code. Next is a list of character arithmetic for individual characters.

0 ⊕ 0 = 0    0 ⊕ ( = (    0 ⊕ ) = )    ( ⊕ 0 = (    ) ⊕ 0 = )

0 ⊖ 0 = 0    ( ⊖ 0 = (    ( ⊖ ( = 0    ) ⊖ 0 = )    ) ⊖ ) = 0
(4.1)

Currently, at the symbol level for ⊕ and ⊖ operations, there are only 10 options in (4.1); the other pairs of terms are not allowed. Therefore, ⊕ and ⊖ are partial operations. As we see in Example 4.1, all the Motzkin words are processed in accordance with (4.1). Obviously, ⊕ operation is commutative and associative (the order of the processing terms does not matter). ⊖ operation is neither commutative nor associative. In pairs of  a,b,c ∈ S, let the character arithmetic (4.1) be observed concerning ⊕ operation, then

(ab) ⊕ c  =  a ⊕ (bc).

Next, we will consider only outer blocks; an outer blocks is not contained within any matched pair. In Example 4.1 in first four options, outer blocks are processed; but the last two cases (options 4.1e and 4.1f) do not suit us. In the option 4.1e, the selected block is not outer. Especially we note the last variant 4.1f as a sample of wronge processing of Motzkin words, since we do not deal with blocks here.

2. Bracket equations. In general, any nonzero element of the Motzkin Row can be divided into a group of outer blocks (hereinafter just blocks). The considered procedure for extracting a block from the Motzkin word can be applied to the group of (outer) blocks. This allows us to receive group extended blocks. The element of the Motzkin Row including  k outer blocks (k-block element) can be decomposed into  k  single extended blocks. But taking into account the group extraction, we can generate  2k−1 single and group extended blocks.

The number of decompositions of the k-block element of the Motzkin Row is equal to the number of partitions of the k-element set, that is, the kth Bell number. For example, three extended blocks  a, b, c  can be grouped in five ways:

{ a, b, c },   { ab, c },   { a, bc },   { ac, b },   { abc }.

In this list there are two trivial decompositions. The first elementwise (or blockwise) decomposition does not contain the group extended blocks. In the last decomposition, the single extended block coincides with the original Motzkin word. The following theorem allows us to calculate the index of the element of the Motzkin Row if the indices of its extended blocks are known.

Теорема 4.1.  Let s be a k-block item of  S, and let  i1, i2, …, ijjk,  be indices of the extended blocks of s such that:

s  =  si1si2 ⊕ … ⊕ sij.
(4.2)

Then

ind s  =  i1 + i2 + … + ij − Δ,  Δ = j −1.
(4.3)

Proof.  In the case  k = j =1, the validity of the theorem is obvious. So k ≥ 2, and for the sake of definiteness, we assume that the indices are listed in decreasing order in (4.2). This means that the initial item s and the first extended block, si1, are in the same character range, i.e., these two Motzkin words have the same length. The code of  si1 contains zero areas, on which the codes of the remaining extended blocks is overlaid.

First, we consider the trivial blockwise decomposition, that is, in (4.2), all the extended blocks are single (non-group), therefore  j= k. Let's go through the Motzkin Row from  si1⊕()  up to  si1si2. At each step, we get a new index, increased by 1. Naturally, we skip the first element  s1= 0, since  si1⊕0 = si1 (i.e., the index is not increasing here). As a result, for the new element of the Motzkin Row we get the index

ind (si1si2)  =  i1 + i2 − (2 − 1).

Similarly, in the next step, we get

ind ((si1si2) ⊕ si3)  =  (i1 + i2 − (2 − 1)) + i3 − (2 − 1)  =  i1 + i2 + i3 − (4 − 2),

or

ind (si1si2si3)  =  i1 + i2 + i3 − (3 − 1).

Further by induction, we obtain the final equality (4.3). Thus, Теорема 4.1 is true for the trivial blockwise decompo­sition; in this case all the sum operands in (4.2) are 1-block elements of the Motzkin Row.

Let's write down the last two partial sums in the following form:

ind (si1si2)  =  i1 + (−1) + i2,   ind (si1si2si3)  =  i1 + (−1) + i2 + (−1) + i3.

Similarly, let's rewrite the equality (4.3) in an equivalent form:

ind s  =  i1 + (−1) + i2 + (−1) + … + (−1) + ik.
(4.3a)

⊕ is commutative, so we can simply rearrange single extended blocks in (4.2); and it is also desirable to rearrange the corresponding indices in (4.3a). Becides, ⊕ is associative, so you can group any adjacent blocks in (4.2); and simultaneously in (4.3a), it is necessary to sum the corresponding groups of indices together with the inner  −1s.

Thus, by rearranging and grouping single extended blocks in (4.2), you can get any permissible decompo­sition that includes both single and group extended blocks. And here two things are important. First, the described transformations preserve equality in (4.2). And second, manipulations with indices do not change the total sum of the operands in (4.3a).

o

Let's call the equation of the form (4.3) or (4.3a) an index equation. The index equation corresponds to some bracket equation, in which the items of the Motzkin Row are connected by the ⊕ and ⊖ operations. Consider a small example.

Example 4.2. Let  a,b,c,d ∈ S  have the indices  ia, ib, ic, id,  respectively. And suppose the following equality holds:

ab  =  cd,  so  ia −1+ ib  =  ic −1+ id.

Let us move b to the right side of equality:

a  =  (cd) ⊖ b,  so  ia =  (ic−1+ id) − (−1+ ib)  =  ic + idib.

Working with index equations it is desirable not to simplify the intermediate expressions. In the last bracket expression, the order of operations is important, since in the general case

(cd) ⊖ b  ≠  c ⊕ (db).

In more complex expressions, the transition from bracket equations to index ones may not be obvious. Before performing ⊕ and ⊖ operations, it is necessary in each case to check both operands for character arithmetic (4.1) and not only this (see the last two options in Example 4.1).

o

3. Derivative Motzkin word. In bracket equations of Example 4.2, we used bracket variables, that is, arbitrary elements of the Motzkin Row. When we write  s1 = 0,  s12 = (0()),  s123 = ()(())0,  and so on, we enumerate bracket constants, that is, the fixed elements of the series (see the tableau in Sec­tion 3). Such equalities are identities, since a specific element of the Motzkin Row is indicated to the left of the equality sign, and its bracket form is to the right. In the next small example, we will practice with bracket and index equations.

Example 4.3. The maximum item of the 7-character range of the Motzkin Row, 7-maximum or  max S7,  is  s127= ()()()0  (127 is the 7th Motzkin number, M7). The 7-maximum is decomposed into three single extended blocks:  s107= ()00000,  s18= ()000,  s4= ()0. From  s127, you can extract three group extended blocks:  s124= ()()000,  s110= ()00()0,  s21= ()()0. The trivial blockwise decompo­sition of 7-maximum can be represented as follows:

s127 = s107s18s4  or  ()()()0 = ()00000 ⊕ ()000 ⊕ ()0.

The corresponding index equation can have the form  M7 = 107+18+M3−2. We can form the bracket equation  ()00000 = ()()()0 ⊖ ()()0  and immediately obtain the required index  M7 −M5 +1 = 127−21+1 = 107.

Recall that the Motzkin numbers index the range maxima of the Motzkin Row, so it is convenient to use them as labels in the Motzkin Row. For example, if it is necessary to construct a Motzkin word with a given index (or calculate the index of the known Motzkin word), then you first need to determine the search range in the Motzkin Row. Such an interval is determined by two neighboring Motzkin numbers from a given index or from the code length of the famous Motzkin word. You can significantly reduce the search interval by entering additional labels.

Let's consider the item  tr = ()00 ... 0  of length r, r >2, which is equal to the difference between the r-maximum and the (r–2)-maximum, that is,

tr = max Sr ⊖ max Sr–2   and   ind tr = MrMr–2 + 1.
(4.4)

Let us call the result of the bracket expression with maxima the derivative Motzkin word. We will call the index of the derivative Motzkin word the derivative Motzkin number. The received derivative Motzkin word,  tk, divides the interval between the (k–1)-maximum and  k-maximum in a ratio of almost 3:1. It is easy to see that for the k-maximum, item  tk  is the smallest extended block of the length k.

In each k-range of the Motzkin Row, there is a certain number of derivative Motzkin words. In any derivative Motzkin word, all matched pairs are adjacent, since only the maxima are allowed in the bracket expressions. For the k-maximum, each (single or group) extended block of length k is derivative Motzkin word, the converse is not true. In general, many derivative Motzkin words are not extended blocks of the k-maximum. We show this in the next example.

Example 4.4. Let us compose the set of derived Motzkin numbers generated by  M8, ind (max S8) = 323, and select the Motzkin Row elements that are indexed by these numbers. We are only interested in item of length 8 with adjacent matched parentheses. There were 13 derivative Motzkin words, including the 8-maximum. Below in the tableau are collected: (a) derivative Motzkin numbers, indices of the derivative Motzkin words, (b) derivative Motzkin words, (c) expressions with parentheses, and (d) index expressions.

 273 ()000000 ()()()() ⊖ ()()() M8 − (M6 − 1) 274 ()0000() ()()()() ⊖ ()()() ⊕ () M8 − (M6 − 1) + (M2 − 1) 276 ()000()0 ()()()() ⊖ ()()() ⊕ ()0 M8 − (M6 − 1) + (M3 − 1) 280 ()00()00 ()()()() ⊖ ()()() ⊕ ()() ⊖ () M8 − (M6 − 1) + (M4 − 1) − (M2 − 1) 281 ()00()() ()()()() ⊖ ()()() ⊕ ()() M8 − (M6 − 1) + (M4 − 1) 290 ()0()000 ()()()() ⊖ ()()() ⊕ ()()0 ⊖ ()0 M8 − (M6 − 1) + (M5 − 1) − (M3 − 1) 291 ()0()0() ()()()() ⊖ ()()() ⊕ ()()0 ⊖ ()0 ⊕ () M8 − (M6 − 1) + (M5 − 1) − (M3 − 1) + (M2 − 1) 293 ()0()()0 ()()()() ⊖ ()()() ⊕ ()()0 M8 − (M6 − 1) + (M5 − 1) 315 ()()0000 ()()()() ⊖ ()() M8 − (M4 − 1) 316 ()()00() ()()()() ⊖ ()() ⊕ () M8 − (M4 − 1) + (M2 − 1) 318 ()()0()0 ()()()() ⊖ ()() ⊕ ()0 M8 − (M4 − 1) + (M3 − 1) 322 ()()()00 ()()()() ⊖ () M8 − (M2 − 1) 323 ()()()() ()()()() M8

Note that in the tableau, the five derivative Motzkin words are not extended blocks of the 8-maximum, their indices are 276, 290, 291, 293, 318.

o

4. Wandering single right parenthesis.  With the help of the derivative Motzkin numbers, it is possible to move in a discontinuous manner within any range of the Motzkin Row. However, the magnitude of such jumps is small. The size of the r-range, r >2, is equal to  Mr − Mr–1, but jumps are possible only in the upper interval of

ind (max Sr) − ind tr + 1 = Mr − (MrMr–2 + 1) + 1 = Mr–2.

In general, the obtained value is less than a quarter of the rest of the r-range. Let us consider the remainder, which begins in  ur = (00…0) and ends in  tr = ()00…0. Both items contain  r –2  zeros, but for  ur  zeros are inside the parentheses, and for  tr  zeros are outside. We will be interested in intermediate elements, in particular  vr = (0)0…0.

Obviously,  ur  immediately follows max Sr–1, we write this so

max Sr–1ur   or   ind ur  =  Mr–1 + 1.
(4.5)

Let's call the operator ↑ a transition. This operator allows you to form chains of elements and also perform jumps along the Motzkin Row. For example,

s1s23 s5−1 s40 s4   and so on.

The exponent of the arrow indicates the value of the jump, that is, the index increment with a plus or minus sign depending on the direction up or down the sequence. The following two records are equivalent:

ak b   and   ind a  + k  =  ind b  > 0.

Example 4.5. Let us choose in the Motzkin Row some chains of elements. The reader can check the data either from the tableau in Section 3 or get it himself using the connected online service. Below the migrating right parenthesis is shown in red.

1. (0) ↑ ()0,   ()0(0) ↑ ()0()0,   (()()0) ↑ (()())0,   ()0(())0 ↑−1 ()0(()0).

2. (0)0 ↑2 ()00,   ((0)0)0 ↑2 ((0))00,   ((())0)0 ↑2 ((()))00,   (())()00 ↑−2 (())(0)0.

3. (0)00 ↑5 ()000,   (()00)() ↑5 (()0)0(),   ((0))0() ↑−5 ((0)0)().

4. (0)()0 ↑13 ()0()0,   (()0)0() ↑13 (())00(),   (()0)0(0) ↑−13 (()00)(0).

In lines 1–4, the same cases are selected (in the last entries, a back jump is performed). Let's collect a small chain from the considered transitions and make the equivalent end-to-end jump:

(()00)() ↑5 (()0)0() ↑13 (())00(),   and the total jump   (()00)() ↑18 (())00().
■

Here are the necessary conditions that, if implemented, will allow you to calculate the index increment when the right parenthesis is moved to one position (right or left):

• the right parenthesis is the last in any outer block;
• the parenthesis is adjacent to zero, with which the permutation is performed.

To calculate the index increment of the word Motkin, it is sufficient to determine the position of the right parenthesis and to select the direction of its displacement. The index increment increases as the parenthesis is removed from the end of the Motzkin word to its beginning.

In the numbered lines of the example 4.5, we see the initial increments ​​of the index when the right parenthesis gradually drifts to the beginning of the Motzkin word. It is not difficult to compose the corresponding sequence of the index increments. Let

Ξ  =  { ξi },  i ≥ 1,

denote the infinite sequence of the index increments. In  Ξ, the items are indixed with 1, that is,  ξ1=1. Here is the beginning of  Ξ:

1, 2, 5, 13, 34, 90, 240, 645, 1745, 4750, 13001, 35762, 98815, 274158, 763479, 2133396, …
(4.6)

Let's define the distance between the above  tr = ()00…0  and  vr = (0)0…0. Both items belong to the r-range and are converted into each other by moving the right parenthesis. To get  tr , we must move the right parenthesis in  vr  from position  r–2  to position  r–1, that is, jump up the Motzkin Row by  ξr–2. Thus

ind vr  +  ξr–2  =  ind tr.

Recall  ur = (00…0). It is not hard to see that   ind vr = ind ur + ξ1 + ξ2 + … + ξr–3. In addition, let's use the previous result (4.4) and (4.5). As a result, we get the following:

Mr–1 +1+ ξ1 + ξ2 +…+ ξr–3 + ξr–2 = MrMr–2 +1,  or   ξ1 + ξ2 +…+ ξr–2 = Mr Mr–1 Mr–2.

Further we increase r by 1:   ξ1 + ξ2 + … + ξr–2 + ξr–1 = Mr+1MrMr–1.
Subtract the last two equations:   ξr–1 = Mr+1 − 2Mr + Mr–2.
As a result, we obtain the formula of the general term in (4.6):

ξn  =  Mn+2 − 2Mn+1 + Mn–1,   n ≥ 2.
(4.7)

Recall  ξ1 = 1, and this agrees with (4.7) if we return  M0 = 1.

Thus, in the Motzkin word, an arbitrary external block can be compressed by moving the rightmost parenthesis, if there is a zero in front of the parenthesis. In doing so, we obtain a new Motzkin word whose index exceeds by  ξn (n is the starting position of the moved parenthesis). Obviously, we will get a reverse jump to the same value, if we return the parenthesis to its original position.

5. Wandering single left parenthesis.  In the Motzkin word, we can move both the rightmost and the leftmost parentheses of the outer block. The calculations are much simpler for the leftmost parenthesis. Let's consider the simplest case.

In the n-range of the Motzkin Row, the first element is  un= (00…0). Here the left parenthesis is at the nth position. The index of such an element is equal to  Mn–1+1. Add to  un the leading zero and permutate it with the left parenthesis. As a result, we get the first element in the next (n+1)-range with the index  Mn +1. The magnitude of the shift along the series is obvious.

In the outer block for the leftmost parenthesis in the nth position, moving left one character gives a jump along the Motzkin Row by the value of  MnMn–1. It is easy to show that this is independent of the position of the outer block in the Motkin word (the block can be either the first/last or the intermediate). There is one limitation, namely, the moving left parenthesis should not be adjacent to the neighboring block.

In general, the left parenthesis can be moved to several positions at once. Let the leftmost parenthesis of the outer block be in the nth position of the Motzkin word. We move this parenthesis to the mth position, provided that there are no other brackets between the positions n, m. Moving the left parenthesis step by step, we get a total jump

δnm  =  Mm–1Mn–1.

Obviously, the jump will be negative (a back jump to the beginning of the series) if  m < n.

Conclusion. Let us summarize some of the results in the navigation on the Motzkin Row. To identify the Motzkin word, first based on its length, we determine the range in which the desired element is located. Further, in the selected r-range, some points is fixed; below we write down several indexes in ascending order:

• Mr–1 +1,  the beginning of the r-range  (00…0);
• MrMr–2 +1 − ξr–2,  the intermediate item  (0)0…0;
• MrMr–2 +1,  the intermediate item  ()00…0;
• Mr,  the end of the r-range  ()()…()[0].

These four Motzkin words divide the r-range into approximately three more or less equal intervals. Inter­mediate points significantly accelerate the identification of elements in the r-range. But it is not difficult to obtain additional intermediate points. In the codes, zero endings can be replaced by the corresponding derivative Motzkin words. And in this case we work with unchanged blocks, which are used like children's cubes in various combinations. Working with the wandering right parenthesis, we can stretch or compress a block.

<<   Lexicographic sequence  ||   Service on-line   >>