## 4. Navigation

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 *s*_{1}= 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-directional 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*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:

*a*⊖

*a'*=

*a"*or

*a'*⊕

*a"*=

*a*, ind

*a*≥ max { ind

*a'*, ind

*a"*}.

Obviously, if ind *a"* =1 (*a"* = *s*_{1} = 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.

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.

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

*a*⊕

*b*) ⊕

*c*=

*a*⊕ (

*b*⊕

*c*).

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 2

^{k}−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*k*th*a, b, c* can be grouped in five ways:

*a*,

*b*,

*c*}, {

*a*⊕

*b*,

*c*}, {

*a*,

*b*⊕

*c*}, {

*a*⊕

*c*,

*b*}, {

*a*⊕

*b*⊕

*c*}.

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 *i*_{1}, *i*_{2}, …,
*i _{j}*,

*j*≤

*k*, be indices of the extended blocks of

*s*such that:

*s*=

*s*

_{i1}⊕

*s*

_{i2}⊕ … ⊕

*s*.

_{ij}Then

*s*=

*i*

_{1}+

*i*

_{2}+ … +

*i*− Δ, Δ =

_{j}*j*−1.

*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,
*s*_{i1}, are in the same character range,
i.e., these two Motzkin words have the same length.
The code of *s*_{i1} 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
*s*_{i1}⊕() up to
*s*_{i1}⊕*s*_{i2}.
At each step, we get a new index, increased by 1.
Naturally, we skip the first element *s*_{1}= 0,
since *s*_{i1}⊕0 =
*s*_{i1} (i.e., the index is not increasing here).
As a result, for the new element of the Motzkin Row we get the index

*s*

_{i1}⊕

*s*

_{i2}) =

*i*

_{1}+

*i*

_{2}− (2 − 1).

Similarly, in the next step, we get

*s*

_{i1}⊕

*s*

_{i2}) ⊕

*s*

_{i3}) = (

*i*

_{1}+

*i*

_{2}− (2 − 1)) +

*i*

_{3}− (2 − 1) =

*i*

_{1}+

*i*

_{2}+

*i*

_{3}− (4 − 2),

or

*s*

_{i1}⊕

*s*

_{i2}⊕

*s*

_{i3}) =

*i*

_{1}+

*i*

_{2}+

*i*

_{3}− (3 − 1).

Further by induction, we obtain the final equality (4.3). Thus, Теорема 4.1 is true for the trivial blockwise decomposition; 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:

*s*

_{i1}⊕

*s*

_{i2}) =

*i*

_{1}+ (−1) +

*i*

_{2}, ind (

*s*

_{i1}⊕

*s*

_{i2}⊕

*s*

_{i3}) =

*i*

_{1}+ (−1) +

*i*

_{2}+ (−1) +

*i*

_{3}.

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

*s*=

*i*

_{1}+ (−1) +

*i*

_{2}+ (−1) + … + (−1) +

*i*.

_{k}⊕ 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 decomposition 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).

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 *i _{a}*,

*i*,

_{b}*i*,

_{c}*i*, respectively. And suppose the following equality holds:

_{d}*a*⊕

*b*=

*c*⊕

*d*, so

*i*−1+

_{a}*i*=

_{b}*i*−1+

_{c}*i*.

_{d}Let us move *b* to the right side of equality:

*a*= (

*c*⊕

*d*) ⊖

*b*, so

*i*= (

_{a}*i*−1+

_{c}*i*) − (−1+

_{d}*i*) =

_{b}*i*+

_{c}*i*−

_{d}*i*.

_{b}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

*c*⊕

*d*) ⊖

*b*≠

*c*⊕ (

*d*⊖

*b*).

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).

**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 *s*_{1} = 0,
*s*_{12} = (0()), *s*_{123} = ()(())0,
and so on, we enumerate *bracket constants*, that is,
the fixed elements of the series (see the tableau in Section 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 *S*_{7},
is *s*_{127}= ()()()0
(127 is the 7th Motzkin number, *M*_{7}).
The 7-maximum is decomposed into three single extended blocks:
*s*_{107}= ()00000,
*s*_{18}= ()000, *s*_{4}= ()0.
From *s*_{127}, you can extract three group extended blocks:
*s*_{124}= ()()000,
*s*_{110}= ()00()0, *s*_{21}= ()()0.
The trivial blockwise decomposition of

*s*

_{127}=

*s*

_{107}⊕

*s*

_{18}⊕

*s*

_{4}or ()()()0 = ()00000 ⊕ ()000 ⊕ ()0.

The corresponding index equation can have the form
*M*_{7} = 107+18+*M*_{3}−2.
We can form the bracket equation
()00000 = ()()()0 ⊖ ()()0
and immediately obtain the required index
*M*_{7} −*M*_{5} +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 *t _{r}* = ()00 ... 0
of length

*r*,

*r*>2, which is equal to the difference between the

*r*-maximum

*r*–2)

*t*= max

_{r}*S*⊖ max

_{r}*S*

_{r–2}and ind

*t*=

_{r}*M*−

_{r}*M*

_{r–2}+ 1.

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, *t _{k}*,
divides the interval between the

*k*–1)

*k*-maximum in a ratio of almost 3:1. It is easy to see that for the

*k*-maximum, item

*t*is the smallest extended block of the length

_{k}*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 *M*_{8}, ind (max *S*_{8}) = 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 | ()()()() ⊖ ()()() | M_{8} − (M_{6} − 1) |

274 | ()0000() | ()()()() ⊖ ()()() ⊕ () | M_{8} − (M_{6} − 1) + (M_{2} − 1) |

276 | ()000()0 | ()()()() ⊖ ()()() ⊕ ()0 | M_{8} − (M_{6} − 1) + (M_{3} − 1) |

280 | ()00()00 | ()()()() ⊖ ()()() ⊕ ()() ⊖ () | M_{8} − (M_{6} − 1) + (M_{4} − 1) − (M_{2} − 1) |

281 | ()00()() | ()()()() ⊖ ()()() ⊕ ()() | M_{8} − (M_{6} − 1) + (M_{4} − 1) |

290 | ()0()000 | ()()()() ⊖ ()()() ⊕ ()()0 ⊖ ()0 | M_{8} − (M_{6} − 1) + (M_{5} − 1) − (M_{3} − 1) |

291 | ()0()0() | ()()()() ⊖ ()()() ⊕ ()()0 ⊖ ()0 ⊕ () | M_{8} − (M_{6} − 1) + (M_{5} − 1) − (M_{3} − 1) + (M_{2} − 1) |

293 | ()0()()0 | ()()()() ⊖ ()()() ⊕ ()()0 | M_{8} − (M_{6} − 1) + (M_{5} − 1) |

315 | ()()0000 | ()()()() ⊖ ()() | M_{8} − (M_{4} − 1) |

316 | ()()00() | ()()()() ⊖ ()() ⊕ () | M_{8} − (M_{4} − 1) + (M_{2} − 1) |

318 | ()()0()0 | ()()()() ⊖ ()() ⊕ ()0 | M_{8} − (M_{4} − 1) + (M_{3} − 1) |

322 | ()()()00 | ()()()() ⊖ () | M_{8} − (M_{2} − 1) |

323 | ()()()() | ()()()() | M_{8} |

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.

**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
*M _{r}* −

*M*

_{r–1}, but jumps are possible only in the upper interval of

*S*) − ind

_{r}*t*+ 1 =

_{r}*M*− (

_{r}*M*−

_{r}*M*

_{r–2}+ 1) + 1 =

*M*

_{r–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
*u _{r}* = (00…0) and ends in

*t*= ()00…0. Both items contain

_{r}*r*–2 zeros, but for

*u*zeros are inside the parentheses, and for

_{r}*t*zeros are outside. We will be interested in intermediate elements, in particular

_{r}*v*= (0)0…0.

_{r}Obviously, *u _{r}* immediately follows
max

*S*

_{r–1}, we write this so

*S*

_{r–1}↑

*u*or ind

_{r}*u*=

_{r}*M*

_{r–1}+ 1.

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,

*s*

_{1}↑

*s*

_{2}↑

^{3}

*s*

_{5}↑

^{−1}

*s*

_{4}↑

^{0}

*s*

_{4}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:

*a*↑

^{k}

*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).

^{2}()00, ((0)0)0 ↑

^{2}((0))00, ((())0)0 ↑

^{2}((()))00, (())()00 ↑

^{−2}(())(0)0.

^{5}()000, (()00)() ↑

^{5}(()0)0(), ((0))0() ↑

^{−5}((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:

^{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 Ξ:

Let's define the distance between the above
*t _{r}* = ()00…0 and

*v*= (0)0…0. Both items belong to the

_{r}*r*-range and are converted into each other by moving the right parenthesis. To get

*t*, we must move the right parenthesis in

_{r}*v*from position

_{r}*r*–2 to position

*r*–1, that is, jump up the Motzkin Row by ξ

_{r–2}. Thus

*v*+ ξ

_{r}_{r–2}= ind

*t*.

_{r}Recall *u _{r}* = (00…0).
It is not hard to see that ind

*v*= ind

_{r}*u*+ ξ

_{r}_{1}+ ξ

_{2}+ … + ξ

_{r–3}. In addition, let's use the previous result (4.4) and (4.5). As a result, we get the following:

*M*_{r–1} +1+
ξ_{1} + ξ_{2} +…+ ξ_{r–3} +
ξ_{r–2} =
*M _{r}* −

*M*

_{r–2}+1, or ξ

_{1}+ ξ

_{2}+…+ ξ

_{r–2}=

*M*−

_{r}*M*

_{r–1}−

*M*

_{r–2}

Further we increase *r* by 1:
ξ_{1} + ξ_{2} + … + ξ_{r–2} +
ξ_{r–1} =
*M*_{r+1} −
*M _{r}* −

*M*

_{r–1}.

Subtract the last two equations: ξ

_{r–1}=

*M*

_{r+1}− 2

*M*+

_{r}*M*

_{r–2}.

As a result, we obtain the formula of the general term in (4.6):

_{n}=

*M*

_{n+2}− 2

*M*

_{n+1}+

*M*

_{n–1},

*n*≥ 2.

Recall ξ_{1} = 1, and this agrees with (4.7)
if we return *M*_{0} = 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 *u _{n}*= (00…0).
Here the left parenthesis is at the

*n*th position. The index of such an element is equal to

*M*

_{n–1}+1. Add to

*u*the leading zero and permutate it with the left parenthesis. As a result, we get the first element in the next (

_{n}*n*+1)-range with the index

*M*+1. The magnitude of the shift along the series is obvious.

_{n}In the outer block for the leftmost parenthesis in the *n*th position,
moving left one character gives a jump along the Motzkin Row by the value of
*M _{n}*−

*M*

_{n–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 *n*th position of the Motzkin word.
We move this parenthesis to the *m*th 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}=

*M*

_{m–1}−

*M*

_{n–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:

*M*_{r–1}+1, the beginning of the*r*-range (00…0);*M*−_{r}*M*_{r–2}+1 − ξ_{r–2}, the intermediate item (0)0…0;*M*−_{r}*M*_{r–2}+1, the intermediate item ()00…0;*M*, the end of the_{r}*r*-range ()()…()[0].

These four Motzkin words divide the *r*-range into approximately three
more or less equal intervals. Intermediate 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.