1. Introduction
2. Numbers and brackets
3. Lexicographic sequence
4. Navigation
5. Service on-line
Russion version (2014)

            1. Introduction

In combinatorics, Motzkin words (named after Theodore Motzkin) are of particular interest. We will use the representation of a Motzkin word as a Correctly Parenthesized Sequences with Zeros (CPSZ). Let's convert the small simple arithmetic expression

y × [(12 − z) / (a + b) − 8] + 345.

First, replace the operands and operation signs by zeros. Further, replace all brackets by parentheses (preserving the orientation). The result is the following CPSZ:


The following two conditions are true for each CPSZ:

In every Motzkin word by a single way, we can split brackets into pairs of bi-direc­tional parentheses, called matched pairs. For instance, in (1.1) the outer matched pair is shown in red. For the matched pair of parentheses, two conditions are met:

Obviously, the set of consecutive Motzkin words is also a Motzkin word. You can say, any CPSZ is created using "building blocks" of the following three types: a left parenthesis, a right parenthesis, and zero. The simplest CPSZ contains only zeros.

In enumerative problems of combinatorics usually count the number of elements of a finite set. Obviously, there are only two Motzkin words of length 2; namely,

00,  ( ).

The three-character Motzkin word (or 3-CPSZ) can be obtained in four copies:

000,  0( ),  (0),  ( )0.

The first two 3-CPSZs (highlighted in green) are inherited from 2-CPSZs by adding a leading zero. The last two 3-CPSZs are unique. In the set of 4-CPSZs there are the following nine Motzkin words:

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

Similarly, the first four 4-CPSZs (again highlighted in green) are inherited from the 3-CPSZs (extra zero at the beginning of the code). The last five 4-CPSZs are unique. Naturally, this procedure can be continued.

Thus, the set of k-CPSZs can be divided into two disjoint subsets. The first subset combines the inherited elements; here are all the  (k–1)-CPSZs with extra zero at the beginning of the code. The elements of the second subset are unique, their codes begin with the left parenthesis, and these elements are usually the majority. The latter is easy to check, it suffices to compare neighboring elements of a known sequence of Motzkin numbers, OEIS A001006. Here is the beginning of the sequence A001006:

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

The Motzkin number  Mn (n = 0, 1, 2, ...)  is equal to the number of all n-CPSZs. As you can see,  Mn > 2Mn–1, n ≥ 4. Hence in the general case, in the set of CPSZs of the same size, there are more unique elements than inherited ones. We have already considered the particular case  n = 3, namely, the equality  M3 = 2M2. A similar doubling of  M2 = 2M1  will be obtained when we move from the single one-character Motzkin word "0" to two two-character words, namely: "00" (one inherited 2-CPSZ) and "( )" (one unique 2-CPSZ). Go down one more step, consider the relationship of the first two Motzkin numbers  M0  and  M1. Let's deal with the 1-CPSZ "0", is it unique or inherited?

In (1.2), the elements are indexed from zero, and  M0 = 1. Thus, the existence of an empty Motzkin word (virtual 0-CPSZ) is allowed, and it is in the singular. Denote a 0-CPSZ by  ∅. It is natural to assume that "0" is an inherited 1-CPSZ, this follows from the obvious equality  0∅ = 0 (there is no customary unique 1-CPSZ because a pair of parentheses are not placed in such a string). Let's look at  ∅  bit differently.

Above we noted that the adjacent matched parentheses contain nothing. But you can say this: there is  ∅  inside such a pair of parentheses. Moreover, we can "detect" a 0-CPSZ anywhere in the Motzkin word. Further, all strings  ∅, ∅∅, ∅∅∅, etc. are 0-CPSZs (or is it just one 0-CPSZ?). So there are doubts about the validity of numbers in (1.2).

In this article, we are interested in real constructions (not virtual ones). Thе 0-CPSZ does not contain the usual "building blocks" (no parentheses and zeros). We will construct a sequence of Motzkin words according to the pattern of a Natural Numbers Series. Among the natural numbers there is no virtual number or "empty number", that is, a number without digits. In mathematics, there is no such thing as a virtual number. In this sense, even zero is not an empty number, since it includes a real (not virtual) digit 0.

I will say the following from myself: as a rule, null elements are illogical, physical realities do not correspond to them. The values ​​of empty elements are meaningless, and it is logical to reset them (some authors do just that). Let's also abandon the empty Motzkin word, in other words, we will assume  M0 = 0. Correspondingly, we correct (1.2)

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

In this case, the status of 1-CPSZ immediately changes from the inherited to the unique, because the hereditary connection breaks off (the parent is lost). As a result, we get the only unique Motzkin word "0" that starts with zero. Let  Un  be the number of unique n-CPSZs. Obviously

Mn = Un + Mn−1 = Un + Un−1 + Mn−2 = . . . =   k ≤ nUk .

Usually, fixed-size Motzkin words are considered in applied problems. And at first glance, this is logical, as the sizes of objects (to which the mathematical model is applied) are fixed. For example, the bracket model is used to calculate the number of Hamiltonian cycles on a rectangular lattice. пример Here the length of the Motzkin word equal to the width of the lattice. Another realization is connected with Motzkin paths. The figure shows the lattice path for Motzkin word (1.1). A Motzkin path consists of up steps (1,1), down steps (1,−1), and horizontal steps (1,0), that represent left parentheses, right parentheses, and zeros, respectively.

Let's ask ourselves: what prevents us to refuse the fixed size of the CPSZs? Fixing the size, each time we deal with a specific finite set of Motzkin words. The cardinality of such a set is equal to the corresponding Motzkin number. What happens if we remove the useless leading zeros in Motzkin words (naturally, with the exception of the 1-CPSZs "0"). Leading zeros are useless (in my opinion) because they can easily be restored, if necessary. We call the procedure for removing leading zeros the normalization of Motzkin words. For example, in the normalized (or truncated) form, the string (1.1) looks so:


Without initial zeros, such strings become impersonal. Normalized elements should be more flexible, universal and, probably, more promising in mathematical models. As a result, we get an infinite set of Motzkin words of variable size. Elements in such a set are easy to sort and systematize. This will be discussed in other sections.

                            ||   Numbers and brackets   >>