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
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:
- brackets are balanced, i.e. the number of left and right parentheses is always the same (the CPSZ may contain only zeros, no parentheses);
- in any initial fragment of the string, the number of right brackets never exceeds the number of left ones.
In every Motzkin word by a single way, we can split brackets into pairs of bi-directional 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:
- the left bracket precedes the right one;
- the pair contains either any CPSZ or nothing (the case of adjacent parentheses).
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,
The three-character Motzkin word (or 3-CPSZ) can be obtained in four copies:
The first two 3-CPSZs (highlighted in green) are inherited from 2-CPSZs
by adding a leading zero. The last two
Similarly, the first four 4-CPSZs (again highlighted in green) are inherited
Thus, the set of k-CPSZs can be divided into two disjoint subsets.
The first subset combines the inherited elements; here are all the
The Motzkin number Mn (n = 0, 1, 2, ...)
is equal to the number of all n-CPSZs. As you can see,
In (1.2), the elements are indexed from zero, and M0 = 1.
Thus, the existence of an empty Motzkin word (virtual
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
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
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.
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.