Equivalence Classes of Motzkin Paths Modulo a Pattern of Length at Most Two

Jean-Luc Baril and Armen Petrossian LE2I UMR CNRS 6306 University of Bourgogne 21078 Dijon France

                     barjl@u-bourgogne.fr
                armen.petrossian@u-bourgogne.fr

Abstract

For any pattern α of length at most two, we enumerate equivalence classes of Motzkin paths where two paths of the same length are equivalent whenever they coincide on all occurrences of the pattern α.

1 Introduction and notation

A Motzkin path of length n, n ≥ 0, is a lattice path starting at point (0, 0), ending at (n, 0), and never going below the x-axis, consisting of up steps U = (1, 1), down steps D = (1, −1) and flat steps F = (1, 0). See Figure 1 for an illustration of a Motzkin path of length 18. Let M be the set of all Motzkin paths. A pattern of length one (resp., two) in M ∈ M consists of one step (resp., two consecutive steps). We will say that an occurrence of a pattern is at position i, i ≥ 1, in M whenever the first step of this occurrence appears at the i-th step of the path. The height of this occurrence is the minimal ordinate reached by its points. For instance, the path M = UUF DDF F UDUF UDDF F UD (see Figure 1) contains three occurrences of the pattern F U at positions 7, 11 and 16, respectively at heights 0, 1 and 0. A Motzkin path will be called Dyck path when it does not contain any flat step F. Let D be the set of all Dyck paths.

Figure 1: A Motzkin path M = UUF DDF F UDUF UDDF F UD.

Many statistics on Motzkin and Dyck paths have been studied. Almost always, it is shown how we can enumerate these paths according to several parameters, such as length, number of occurrences of a pattern, number of returns to the x-axis (see, for instance, [4, 7, 8, 9, 11, 12, 13, 15, 16, 19] for Dyck paths and [2, 3, 5, 6, 10, 14, 17] for Motzkin paths). Recently in [1], the authors investigate equivalence relations on the set D of Dyck paths where two Dyck paths of the same length are equivalent whenever they coincide on all occurrences of a given pattern.

In this paper, we study these equivalence relations on the set M of Motzkin paths for any pattern α of length at most two, i.e.,

two Motzkin paths of the same length are α-equivalent whenever all occurrences of the pattern α appear at the same positions in the two paths.

For instance, UDUF DF FUUF FUDDDFUD is F U-equivalent to the path in Figure 1 since all occurrences of the pattern F U (in boldface) appear at the same positions in the two paths.

For any pattern α of length at most two, we provide generating functions for the number of α-equivalence classes in M, with respect to the length (see Table 1). The general method used consists of exhibiting one-to-one correspondences between some subsets of Motzkin paths and the different sets of equivalence classes by using combinatorial reasonings, and then, evaluating algebraically the generating functions for these subsets.

2 Equivalence classes modulo a pattern of length one

Throughout this section, we study the α-equivalence in M for α ∈ {U, D, F }.

2.1 Modulo α = F

Let A be the set of Motzkin paths without any points of ordinate greater than one. For instance, we have UF DUDF ∈ A and UUDDUD ∉ A.

Lemma 1. There is a bijection between A and the set of F -equivalence classes of M.

Pattern  Sequence  Sloane  a_{n}, 1 ≤ n ≤ 10
\{U\}, \{D\}  \frac{2}{1−2x+\sqrt{1−4x^{2}}}  \underline{A001405} 1, 2, 3, 6, 10, 20, 35, 70, 126, 252
\{F \}  2^{n}  \underline{A000079} 1, 2, 4, 8, 16, 32, 64, 128, 256, 512
\{UU\}, \{DD\}  \frac{(x−1)^{2}−\sqrt{(1−3x^{2})(x^{2}+1)}}{2x(x^{3}−(1−x)^{2})}  \underline{A191385}  1, 1, 1, 2, 3, 5, 7, 12, 18, 31

{DU} Shift of Fibonacci

\underline{A132916}

1, 1, 1, 2, 3, 5, 8, 13, 21, 34
\{UD\}  Fibonacci  \underline{A000045} 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
\begin{matrix}\{UF \}, \{DF \}, \\ \{F U\}, \{F D\} \end{matrix}  \frac{2}{1−2x−\sqrt{1−4x^{3}}}  \underline{A165407}  1, 1, 2, 3, 4, 7, 11, 16, 27, 43
\{F F \}  \frac{x(1−x−x^{2}+3x^{3}−5x^{4}+3x^{5}−2x^{6}−x^{7}−x^{9})}{(1−x−2x^{4}−x^{6}−x^{7})(1−2x+x^{2}−x^{3})}  New  1, 2, 2, 5, 9, 17, 29, 53, 94, 168

Table 1: Number of α-equivalence classes for Motzkin paths.

Proof. Let M be a Motzkin path in M\A. Let us prove that there exists M′ ∈ A (with the same length as M) such that M and M′ belong to the same class. Since M does not belong to A, we can write M = RUQDS, where R is of maximal length so that it does not contain any point of ordinate two, and Q is a (possibly empty) Motzkin path.

Now, we define a sequence of Motzkin paths M_{0} = M, M_{1}, M_{2}, …, M_{k−1}, M_{k} = M′, k ≥ 1, where for any i, 1 ≤ i ≤ k, the Motzkin path M_{i} is obtained from M_{i−1} by performing the following process.

Let M_{i−1} = RUQDS be the above decomposition. Then, M_{i} = RDQUS is obtained from M_{i−1} by swapping the two steps U and D contiguous to Q.

The process finishes because it decreases the number of points of ordinate greater than one. All Motzkin paths M_{0} = M, M_{1}, …, M_{k} = P′ belong to the same equivalence class. So, at the end of the process M_{k} belongs to A. For instance, if

M = UUUDUF DF UF F DF F DDUD,

then we obtain M_{1} = M′ = UDUDUF DF UF F DF F UDUD. See Figure 2 for an illustration of this example.

Now we will prove that any F -equivalence class contains at most one element in A. For a contradiction, let M and M′ be two different Motzkin paths in A belonging to the same class. We write M = QR and M′ = QS where R and S start with two different steps. Since M and M′ lie in the same class, these steps cannot be F. Without loss of generality, let us assume that the first step of R is an up step U and then, the first step of S is a down step D. This means that the last point of Q has its ordinate equal to zero (otherwise, R would contain a point of ordinate at least two). As S starts with a down step, S has its second point (from the left) with an ordinate equal to −1, which gives a contradiction.

M = ⟶ M′ =

Figure 2: Illustration of the example described in the proof of Lemma 1.

Theorem 2. The generating function for the set of F -equivalence classes in M with respect to the length is given by

\frac{1 − x}{1 − 2x}.

Proof. Using Lemma 1, it suffices to obtain the generating function A(x) for the set A. A non-empty Motzkin path M ∈ A can be written either M = F Q where Q ∈ A or M = UF^{r}DQ where r ≥ 0 and Q ∈ A. Then, we deduce the functional equation A(x) = 1 + xA(x) + \frac{x^{2}}{1−x}A(x) which implies that A(x) = \frac{1−x}{1−2x}.

2.2 Modulo α = U or α = D

The result for the case α = D is deduced from α = U using a simple symmetry (the mirror transformation on Motzkin paths). So, we set α = U in this part.

Let B be the set of Motzkin paths without any flat steps at positive height. For instance, we have UDF UD ∈ B and UF DUD ∉ B.

Lemma 3. There is a bijection between B and the set of U-equivalence classes of M.

Let M be a Motzkin path in M\B. Let us prove that there exists a Motzkin path M′ ∈ B (with the same length as M) such that M and M′ belong to the same class. Since M does not belong to B, there exists a Motzkin path Q (possibly empty) such that M = RF QDS where R is maximal so that it does not contain any flat step at positive height, its last point has an ordinate of at least one, and Q is a Motzkin path.

Now, we define a sequence of Motzkin paths M_{0} = M, M_{1}, M_{2}, …, M_{k−1}, M_{k} = M′, k ≥ 1, where for any i, 1 ≤ i ≤ k, the Motzkin path M_{i} is obtained from M_{i−1} by performing the following process.

Let M_{i−1} = RF QDS be the above decomposition. Then, we define the Motzkin path M_{i} = RDQF S obtained from M_{i−1} by swapping the two steps F and D contiguous to Q.

The process finishes because it decreases the height of the leftmost flat step having a positive height. All Motzkin paths M_{0} = M, M_{1}, …, M_{k} = M′ belong to the same equivalence class. So, at the end of the process, M_{k} belongs to B. For instance, if we perform the above process on M = UUUDF F F F UUDDF F DDF F, then we obtain M_{1} = UUUDDF F F UUDDF F F DF F and M_{2} = M′ = UUUDDDF F UUDDF F F F F F (see Figure 3 for an illustration of this example).

M = M_{0} = ⟶ M_{1} =

⟶ M_{2} = M′ =

Figure 3: Illustration of the example described in the proof of Lemma 3.

Now we will prove that any U-equivalence class contains at most one element in B. For a contradiction, let M and M′ be two different Motzkin paths in B belonging to the same class. We write M = QR and M′ = QS where R and S start with two different steps. Since M and M′ lie in the same class, these steps cannot be U. Without loss of generality, let us assume that the first step of R is a down step D and then, the first step of S is a flat step F. This means that the last point of Q has its ordinate equal to zero (otherwise M′ could not belong to B). As the first step of R is D, the second point of R has an ordinate equal to -1 which gives a contradiction. □

Theorem 4. The generating function for the set of U-equivalence (resp., D-equivalence) classes in M with respect to the length is given by

\frac{2}{1 − 2x + \sqrt{1 − 4x^{2}}} .

Proof. Using Lemma 3, it suffices to obtain the generating function B(x) for the set B. A non-empty Motzkin path M ∈ B can be written either M = F Q where Q ∈ B or M = UQDQ′ where Q is a Dyck path in D and Q′ ∈ B. Then, we deduce the functional equation B(x) = 1 + xB(x) + x^{2}C(x^{2})B(x) where C(x) = \frac{1−\sqrt{1−4x}}{2x} is the generating function for the set D of Dyck paths. A simple calculation gives the result.

3 Equivalence classes modulo a pattern of length two

Throughout this section, we study the α-equivalence in M for any pattern α of length two. By considering the mirror transformation of Motzkin paths, it suffices to examine the cases where α ∈ {UU, UD, UF, F U, DU, F F }.

M = M_{0} =  ⟶^{(1),(1),(1)} M_{3}

⟶^{(2),(2)} M_{5} = M′ =

Figure 4: Illustration of the example described in the proof of Lemma 5.

3.1 Modulo α = UU

Let E be the set of Motzkin paths without any flat steps at positive height and having no ascents of length one, i.e., no maximal consecutive up steps of length one. For instance, we have UUDDF ∈ E and F UDF F ∉ E.

Lemma 5. There is a bijection between E and the set of UU-equivalence classes of M.

Proof. Let M be a Motzkin path in M\E. Let us prove that there exists a Motzkin path M′ ∈ E of the same length as M such that M and M′ belong to the same class.

We define a sequence of Motzkin paths M_{0} = M, M_{1}, M_{2}, …, M_{k−1}, M_{k} = M′, k ≥ 1, where for any i, 1 ≤ i ≤ k, the Motzkin path M_{i} is obtained from M_{i−1} by performing the following process.

(1) If there is an ascent of length one in M_{i−1}, then we write M_{i−1} = RUQDS where R is of maximal length so that it does not contains any ascent of length one, R does not finish with U, and Q is a Motzkin path (possibly empty) that does not start with an up step. So, we set M_{i} = RF QF S;

(2) Otherwise, if there is a flat step at positive height, then we perform the process described in the proof of Lemma 3.

This process finishes because part (1) of the process decreases by one the number of ascents of length one, and part (2) decreases the height of the leftmost flat step having a positive height (see the proof of Lemma 3). All Motzkin paths M_{0} = M, M_{1}, …, M_{k} = M′ belong to the same class. At the end of the process, M_{k} belongs to E. For instance, if we perform the above process on M = M_{0} = UUUDUF DF UUDDUDDDUD then we obtain M_{3} = UUUDF F F F UUDDF F DDF F after three runs of (1), and we obtain M_{5} = UUUDDDF F UUDDF F F F F F after two runs of (2) (see Figure 4 for an illustration of this example).

For a contradiction, let M and M′ be two different Motzkin paths in E belonging to the same class. We write M = QR and M′ = QS where R and S start with two different steps, and R and S cannot start with UU. We distinguish two cases. If the last step of Q is a down step D or a flat step F, then R and S cannot start with UF and UD (and also with U) because an ascent of length one would be created; if the last step of Q is an up step U, then R and S cannot start with U because a pattern UU would be created. Without loss of generality, we can assume (for the two last cases) that R (resp., S) starts with D (resp., with F); so, the last point of Q has a positive ordinate that implies that the first step of S is a flat step of positive height, which is a contradiction.

Theorem 6. The generating function for the set of UU-equivalence classes of M with respect to the length is given by

\frac{(x − 1)^{2} − \sqrt{(1 − 3x^{2})(x^{2} + 1)}}{2x(x^{3} − (1 − x)^{2})}.

Proof. Using Lemma 5, it suffices to give the generating function for the set E, which is already known (see \underline{A191385} in [18]).

3.2 Modulo α = DU

Let F be the set of Motzkin paths without any points of ordinate greater than one, and without any flat steps at height zero. For instance, we have UF DUF F DUD ∈ F and UDF UUDD ∉ F.

Lemma 7. There is a bijection between F ∪ {F } and the set of DU-equivalence classes of M.

Proof. Let M ≠ F be a Motzkin path in M\F (the case where M = F is clear). Let us prove that there exists a Motzkin path M′ ∈ F of the same length as M such that M and M′ belong to the same class.

Any Motzkin path M ∈ M can be uniquely written either

M = β_{0}  or  M = β_{0}(DUβ_{1}) ⋯ (DUβ_{r}),

where r ≥ 1, and β_{i}, 0 ≤ i ≤ r, (possibly empty) does not contain any pattern DU.

If M = β_{0} then we set M′ = UF^{s_{0}−2}D where s_{0} ≥ 2 is the length of M; otherwise, we set M′ = UF^{s_{0}−1}(DUF^{s_{1}}) ⋯ (DUF^{s_{r−1}})(DUF^{s_{r}−1})D where s_{i}, 0 ≤ i ≤ r, is the length of β_{i}. By construction, M and M′ belong to the same equivalence class and M′ lies in F. For instance, if M = F UF DUUUDUDDUUF F DDD then we obtain M′ = UF F DUF F DUF F DUF F F F D (see Figure 5 for an illustration of this example).

Any Motzkin path M ∈ F is characterized by the positions of its pattern DU. So, two different Motzkin paths in F cannot belong to the same class, which completes the proof.

Theorem 8. The generating function for the set of DU-equivalence classes of M with respect to the length is given by F (x) = \frac{1−x^{2}−x^{3}}{1−x−x^{2}} , that corresponds to a shift of the Fibonacci sequence.

Figure 5: Illustration of the example in the proof of Lemma 9.

Proof. Using Lemma 7, it suffices to provide the generating function F (x) for the set F ∪{F }. Let M be a non-empty Motzkin path in F. It can be written M = UF^{r}DQ where r ≥ 0 and Q ∈ F. So, we have the functional equation F (x) = 1 + x + \frac{x^{2}}{1−x}(F (x) − x) which implies the result.

3.3 Modulo α = UD

Let G be the set of Motzkin paths without any points of ordinate greater than one, and without any flat steps at positive height. For instance, we have F UDF UD ∈ G and UF DUUDD ∉ G.

Lemma 9. There is a bijection between G and the set of UD-equivalence classes of M.

Proof. Let M be a Motzkin path in M\G. Let us prove that there exists a Motzkin path M′ ∈ G of the same length as M such that M and M′ belong to the same class.

Any Motzkin path M ∈ M can be uniquely written either

M = β_{0}  or  M = β_{0}(UDβ_{1}) ⋯ (UDβ_{r}),

where r ≥ 1, and β_{i}, 0 ≤ i ≤ r, (possibly empty) does not contain any pattern UD.

If M = β_{0} then we set M′ = F^{s_{0}} where s_{0} ≥ 0 is the length of M; otherwise, we set M′ = F^{s_{0}}(UDF^{s_{1}}) ⋯ (UDF^{s_{r}}) where s_{i}, 0 ≤ i ≤ r, is the length of β_{i}. Obviously, M and M′ belong to the same equivalence class and M′ lies in G. For instance, if M = F UF DUUUDUDDUUUDDDD then we obtain M′ = F F F F F F UDUDF F F UDF F F (see Figure 6 for an illustration of this example).

M = ⟶ M′ =

Figure 6: Illustration of the example in the proof of Lemma 9.

Any Motzkin path M ∈ G is characterized by the positions of its pattern UD. So, two different Motzkin paths in G cannot belong to the same class, which completes the proof.

Theorem 10. The generating function for the set of UD-equivalence classes of M with respect to the length is given by F (x) = \frac{1}{1−x−x^{2}} , that corresponds to the Fibonacci sequence.

Proof. Using Lemma 9, it suffices to provide the generating function G(x) for the set G. Let M be a non-empty Motzkin path in G. It can be written either M = F Q or M = UDQ where Q ∈ G which implies that G(x) = \frac{1}{1−x−x^{2}} .

3.4 Modulo α = UF

Let H be the set of Motzkin paths without any patterns UD and UU, and such that all patterns F F and DF appear at height zero. For instance, we have F F UF UF DDF ∈ H and UDUF UF DDF ∉ H.

Lemma 11. There is a bijection between H and the set of UF -equivalence classes of M.

Proof. Let M be a Motzkin path in M\H. Let us prove that there exists a Motzkin path M′ ∈ H of the same length as M such that M and M′ belong to the same class.

Any Motzkin path M ∈ M can be uniquely written either

M = β_{0}  or  M = β_{0}Π_{i=1}^{r}(UF)^{k_{i}}β_{i},

where r ≥ 1, k_{i} ≥ 1 for 1 ≤ i ≤ r and β_{i}, 0 ≤ i ≤ r, (non-empty) does not contain any pattern UF.

If M = β_{0} then we set M′ = F^{s_{0}} where s_{0} ≥ 0 is the length of M; since an element in H avoids UU and UD, M′ is the only one element in H lying in the class of M (that avoids UF).

Otherwise, we set M′ = F^{s_{0}}Π_{i=1}^{r}(UF)^{k_{i}}β′_{i} with β′_{i} = D^{t_{i}}F^{s_{i}−t_{i}} for 1 ≤ i ≤ r, where s_{i}, 0 ≤ i ≤ r, is the length of β_{i} and t_{i}, i ≥ 1, is recursively defined by the equation

t_{i} = min(s_{i}, ∑_{j=1}^{i} k_{j} − ∑_{j=1}^{i−1} t_{j}).

It is worth noticing that ∑_{j=1}^{i} k_{j} (resp., ∑_{j=1}^{i−1} t_{j}) is the number of up steps (resp., down steps) before β′_{i} in M′. So, setting t_{i} = min(s_{i}, ∑_{j=1}^{i} k_{j} − ∑_{j=1}^{i−1} t_{j}) means that β′_{i} consists of the maximum possible of down steps, eventually completed with some flat steps at height zero. Then, M and M′ belong to the same equivalence class and M′ lies in G. For instance, if we have M = UUUF DF DUF UF F F DUDDD then we obtain M′ = F F UF DF F UF UF DDF F F F F (see Figure 7 for an illustration of this example).

Moreover, M′ is the unique element in H in the same class as M = β_{0}Π_{i=1}^{r}(UF)^{k_{i}}β_{i}. Indeed, β_{i}, i ≥ 1, does not contains any pattern UU, UF and UD implies that β_{i} does not contain any up steps; M does not contains F F and DF at positive height implies that β_{i} = D^{k_{i}}F^{s_{i}−k_{i}} where k_{i} is either the length s_{i} of β_{i} or the difference between the numbers of up steps and down steps before β_{i}, that is precisely ∑_{j=1}^{i} k_{j} − ∑_{j=1}^{i−1} t_{j}. Thus, we necessarily have M = M′ which completes the proof.

Figure 7: Illustration of the example in the proof of Lemma 11.

Theorem 12. The generating function for the set of UF -equivalence classes of M with respect to the length is given by H(x) = \frac{2}{1−2x−\sqrt{1−4x^{3}}} .

Proof. Using Lemma 11, it suffices to provide the generating function H(x) for the set H. Let M be a non-empty Motzkin path in H. It can be written either M = F Q or M = UQDR where Q and R are two Motzkin paths.

If we have M = F Q, then M belongs to H if and only if Q ∈ H. Otherwise, M = UQDR belongs to H if and only if R ∈ H and Q ∈ H such that Q = F Π_{i=1}^{r}(UF)^{k_{i}}D^{ℓ_{i}} for some k_{i} and ℓ_{i}, with 1 ≤ i ≤ r. Since Q is a Motzkin path of length n = 1 + 3 ∑_{i=1}^{r} k_{i}, this implies that Q′ = Π_{i=1}^{r}U^{k_{i}}D^{ℓ_{i}} is a Dyck path of semilength ∑_{i=1}^{r} k_{i} = \frac{n−1}{3}. Conversely, any Dyck path can be associated to a Motzkin path of the form of Q. So we deduce the functional equation H(x) = 1+xH(x)+x^{3}C(x^{3})H(x) where C(x) = \frac{1−\sqrt{1−4x}}{2x} is the generating function for the set D of Dyck paths, which completes the proof.

3.5 Modulo α = F U

Let I be the set of Motzkin paths starting with a flat step, without any patterns DU, UU, F D and such that all patterns F F appear at height zero. For instance, we have F F UF UDF UDD ∈ I and F F UF UF DDF UD ∉ I.

Lemma 13. There is a bijection between I and the set of F U-equivalence classes of M.

Proof. This is a simple adaptation of the proof of Lemma 11 by replacing UF with F U in the decomposition M = β_{0}Π_{i=1}^{r}(UF)^{k_{i}}β_{i}. So, we do not present this proof here.

Theorem 14. The generating function for the set of F U-equivalence classes of M with respect to the length is given by I(x) = \frac{2}{1−2x−\sqrt{1−4x^{3}}} .

Proof. Using Lemma 13, it suffices to provide the generating function I(x) for the set I. Let M be a non-empty Motzkin path in I. It can be uniquely decomposed M′ = F^{s_{0}}Π_{i=1}^{r}(F U)^{k_{i}}β′_{i} with β′_{i} = D^{t_{i}}F^{s_{i}−t_{i}} for 1 ≤ i ≤ r, where s_{i}, 0 ≤ i ≤ r, is the length of β_{i} and t_{i} is recursively defined by t_{i} = min(s_{i}, ∑_{j=1}^{i} k_{j} − ∑_{j=1}^{i−1} t_{j}). The transformation that consists of replacing all occurrence F U into an occurrence UF, induces a one-to-one correspondence between I and H. Therefore, the generating function I(x) for I verifies I(x) = H(x). Using Theorem 12, we complete the proof.

3.6 Modulo α = F F

Let M ∈ M be a Motzkin path. A long flat in M is a maximal sequence of at least two consecutive flat steps in M. An isolate flat step is a flat step which is not contiguous to another flat step.

Let J be the set of Motzkin paths without any points of ordinate greater than one, without any isolate flat steps, such that two long flats are separated by at most two steps, and at most one step precedes (resp., follows) the first (resp., last) long flat. For instance, there are five Motzkin paths in J of length 6: F F F F F F, F F UF F D, UF F DF F, UF F F F D and F F UDF F. For r, s ∈ {0, 1}, we define the set J_{r}^{s} of elements of J such that the height of the leftmost long flat is r and the height of the rightmost long flat is s. Obviously, we have J = ∪_{r,s∈{0,1}}J_{r}^{s}.

Let M be a Motzkin path without any points of ordinate greater than one. We denote by |M| its length, i.e., the number of the steps in M.

Fact 1: There is a unique decomposition of the form

M = β_{0}Π_{i=1}^{k}(Q_{i}β_{i})

with Q_{i} of maximal length in J for all 1 ≤ i ≤ k and where β_{i} ∈ M, 0 ≤ i ≤ k, does not contain any long flat, and only β_{0} and β_{k} can possibly be empty.

Fact 2: If M = β_{0}Π_{i=1}^{k}(Q_{i}β_{i}) is the decomposition obtained in Fact 1, then there exists M′ in the same class as M such that M′ = β′_{0}Π_{i=1}^{k}(Q_{i}β′_{i}) with β′_{i} = F if |β_{i}| = 1, β′_{i} = (UD)^{\frac{|β_{i}|}{2}} if |β_{i}| ≥ 2 is even and β′_{i} = UF D(UD)^{\frac{|β_{i}|−3}{2}} if |β_{i}| ≥ 3 is odd. In the following, a Motzkin path β′_{i} of the previous form will be called a hinge. It is worth noticing that any hinge is entirely characterized by its length.

Let K be the set of Motzkin paths M = β_{0}Π_{i=1}^{k}(Q_{i}β_{i}) verifying the conditions described in Fact 2, and such that all Q_{i} starts with F F whenever β_{i−1} and β_{i} are non-empty. For instance, the third Motzkin path UDUDUDF F UF F DUDF F UD in Figure 8 belongs to K. Its decomposition provides β_{0} = UDUDUD, Q_{1} = F F UF F D, β_{1} = UD, Q_{2} = F F and β_{2} = UD.

Lemma 15. There is a bijection between K and the set of F F -equivalence classes of M.

Proof. For any Motzkin path in M\K, the process described in the proof of Lemma 1 ensures that there is a Motzkin path M ∈ A in the same F -equivalence class, and thus in the same F F -equivalence class.

Let M = β_{0}Π_{i=1}^{k}(Q_{i}β_{i}) be the decomposition described in Fact 2.

We define a sequence of Motzkin path M_{0} = M, M_{1}, M_{2}, …, M_{k−1}, M_{k} = M′, k ≥ 1. For any i, 1 ≤ i ≤ k, the Motzkin path M_{i} is obtained from M_{i−1} by performing the

following process.

(a) If β_{i−1} and β_{i} are non-empty and Q_{i} = UW D, then we replace Q_{i} with W̄ where W̄ is obtained from W by exchanging U and D, and we replace β_{i−1} (resp., β_{i}) with a hinge of length |β_{i−1}| + 1 (resp., of length |β_{i}| + 1); (b) If β_{i−1} and β_{i} are non-empty and Q_{i} = UW F, then we replace Q_{i} with W̄ F D where W̄ is obtained from W by exchanging U and D, and we replace β_{i−1} (resp., β_{i}) with a hinge of length |β_{i−1}| + 1 (resp., of length |β_{i}| − 1).

By construction, all Motzkin paths M_{0} = M, M_{1}, M_{2}, …, M_{k−1}, M_{k} = M′, belong to the same class and M′ belongs to K. Moreover, M′ is the unique element in K in the same class as M; indeed, let M = β_{0}Π_{i=1}^{k}(Q_{i}β_{i}) and M′ = β′_{0}Π_{i=1}^{k′}(Q′_{i}β′_{i}) two different elements in K lying in the same class.

– From the definition of the sets K and J, it is clear that k = k′.

– If the long steps in M appear in M′ with the same height as in M, then we necessarily have Q_{i} = Q′_{i} for 1 ≤ i ≤ k. Thus, we deduce |β_{i}| = |β′_{i}| for i ≥ 0, and with the last remark of Fact 1, β_{i} = β′_{i} for all i ≥ 0, which is a contradiction with M ≠ M′.

– If there is a long flat in M with height h ∈ [0, 1] and such that it appears in M′ at height 1 − h. We choose the leftmost long flat with this property. Let i ≥ 1 be the integer such that this long flat of M appears in Q_{i}. Since any element in J has at most two steps between two long flats, and at most one step before (resp., after) the first (resp., the last) long flat step, any long flat step of height h′ ∈ [0, 1] in Q_{i} appears at height 1 − h′ in Q′_{i}. Since Q_{i} ∈ J, we have either Q_{i} = F F W F F and Q′_{i} = UF F W̄ F F D, or Q_{i} = F F W F F D and Q′_{i} = UF F W̄ F F, or Q_{i} = UF F W F F and Q′_{i} = F F W̄ F F D, or Q_{i} = UF F W F F D and Q′_{i} = F F W̄ F F.

Observing these four cases, Q_{i} cannot be a prefix nor a suffix of M (otherwise M′ could not have the leftmost F F at the same position as M). This means that β_{i−1} and β_{i} are nonempty. Thus, there is an element among M and M′ where there is i such that Q_{i} whenever the element is M, Q′_{i} whenever the element is M′, is contiguous with two non-empty hinges and such that the first long flat is of height zero. We obtain a contradiction with the fact that M and M′ belong to K which completes the proof.

\begin{aligned}& \underrightarrow{Lemma 1} M = \\ ⟶^{(b),(a)} M_{2} = \end{aligned}

Figure 8: Illustration of the example in the proof of Lemma 15.

For instance, if M = UF DUDUF F DF F UDUF F DF then the decomposition in Fact 2 implies β_{0} = UF DUD, Q_{1} = UF F DF F, β_{1} = UD, Q_{2} = UF F D and β_{2} = F. For i = 1, β_{0} and β_{1} are non-empty and Q_{1} = UW F with W = F F DF; the process (b) creates M_{1} = UDUDUDF F UF F DF UF F DF where β_{0} (resp., β_{1} and Q_{1}) is replaced with UDUDUD (resp., F and F F UF F D). For i = 2, β_{1} = F and β_{2} = F are non-empty and Q_{2} = UF F D; the process (a) creates M_{2} = UDUDUDF F UF F DUDF F UD where β_{1} (resp., β_{2} and Q_{2}) is replaced with UD (resp., UD and F F). See Figure 8 for an illustration of this example.

Lemma 16. The generating function for the set J, with respect to the length is given by J(x) = \frac{x^{4}−x^{2}+x−1}{x^{7}+x^{6}+2x^{4}+x−1}.

Proof. In order to obtain the generating function J(x) for the set J, we calculate the generating functions J_{r}^{s}(x) for the set J_{r}^{s} with r, s ∈ {0, 1}.

– If M is a Motzkin path in J_{0}^{0}. We have either M = F^{k} or M = W F^{k} or M = W′UDF^{k} with k ≥ 2, W ∈ J_{0}^{1} and W′ ∈ J_{0}^{0};

– if M is a Motzkin path in J_{1}^{0}. We have either M = W F^{k} or M = W′UDF^{k} with k ≥ 2, W ∈ J_{1}^{1} and W′ ∈ J_{1}^{0};

– If M is a Motzkin path in J_{0}^{1}. We have either M = W UF^{k}D or M = W′UF^{k}D with k ≥ 2, W ∈ J_{0}^{0} and W′ ∈ J_{0}^{1};

– If M is a Motzkin path in J_{1}^{1}. We have either M = UF^{k}D or M = W UF^{k}D or M = W′UF^{k}D with k ≥ 2, W ∈ J_{1}^{0} and W′ ∈ J_{1}^{1}.

We deduce the following system of functional equations:

\{ \begin{matrix}J_{0}^{0}(x) = & \frac{x^{2}}{1−x}(J_{0}^{1}(x) + x^{2}J_{0}^{0}(x) + 1) \\ J_{1}^{0}(x) = & \frac{x^{2}}{1−x}(J_{1}^{1}(x) + x^{2}J_{1}^{0}(x)) \\ J_{1}^{1}(x) = & \frac{x^{4}}{1−x}(J_{0}^{0}(x) + J_{0}^{1}(x)) \\ J_{1}^{0}(x) = & \frac{x^{4}}{1−x}(J_{1}^{0}(x) + J_{1}^{1}(x) + 1). \end{matrix}

A simple calculation (with Maple for instance) provides the generating functions for the four sets J_{0}^{0}, J_{0}^{1}, J_{1}^{1} and J_{1}^{0}, and thus for the set J = ∪_{r,s∈{0,1}}J_{r}^{s} which completes the proof.

Theorem 17. The generating function for the set of F F -equivalence classes of M with respect to the length is given by

\frac{x(1 − x − x^{2} + 3x^{3} − 5x^{4} + 3x^{5} − 2x^{6} − x^{7} − x^{9})}{(1 − x − 2x^{4} − x^{6} − x^{7})(1 − 2x + x^{2} − x^{3})}.

Proof. With Lemma 15, it suffices to obtain the generating function K(x) for the set K. First, we calculate the generating functions for the sets K_{r} with r, s ∈ {0, 1, 2}, where K_{0} (resp., K_{1}, resp., K_{2}) is the subset of K of Motzkin path starting by F F (resp., UF F, resp., a hinge). Let J_{r}^{s}(x), r, s ∈ {0, 1}, be the generating function obtained in the proof of Lemma 16. We set J_{1}(x) = J_{1}^{0}(x) + J_{1}^{1}(x) and J_{0}(x) = J_{0}^{0}(x) + J_{0}^{1}(x).

– Let M be a Motzkin path in K_{0}. We discuss on the number of hinges in M.

If M does not contains any hinge, then this means that M ∈ J_{0}; If M has only one hinge, then either M = QH_{k}S, k ≥ 2, or M = QH_{k}T, k ≥ 3, or M = RH_{k}S, k ≥ 1, or M = RH_{k}T, k ≥ 2 with Q ∈ J_{0}^{0}, R ∈ J_{0}^{1}, S ∈ J_{1}^{0} ∪ J_{1}^{1} ∪ {ϵ}, T ∈ J_{0}^{0} ∪ J_{0}^{1} and H_{k} is a hinge of length at least k; If M has at least two hinge, then either M = QH_{k}W, k ≥ 3, or M = RH_{k}W, k ≥ 2, with Q ∈ J_{0}^{0}, R ∈ J_{0}^{1} and W ∈ K_{0}\J_{0}.

Thus we have the functional equation:

\begin{aligned}K_{0}(x) = & J_{0}(x) + J_{0}^{0}(x)\frac{x^{2}}{1−x}(J_{1}(x) + 1) + J_{0}^{0}(x)\frac{x^{3}}{1−x}J_{0}(x) + J_{0}^{1}(x)\frac{x}{1−x}(J_{1}(x) + 1)+ \\ & J_{0}^{1}(x)\frac{x^{2}}{1−x}J_{0}(x) + J_{0}^{0}(x)\frac{x^{3}}{1−x}(K_{0}(x) − J_{0}(x)) + J_{0}^{1}(x)\frac{x^{2}}{1−x}(K_{0}(x) − J_{0}(x)) \end{aligned} .

– Let M be a Motzkin path in K_{1}. We discuss on the number of hinges in M. If M does not contain any hinge, then this means that M ∈ J_{1}; If M has only one hinge, then either M = Q′H_{k}S, k ≥ 2, or M = Q′H_{k}T, k ≥ 3, or M = R′H_{k}S, k ≥ 1, or M = R′H_{k}T, k ≥ 2 with Q′ ∈ J_{1}^{0}, R′ ∈ J_{1}^{1}, S ∈ J_{1}^{0} ∪ J_{1}^{1} ∪ {ϵ}, T ∈ J_{0}^{0} ∪ J_{0}^{1} and H_{k} is a hinge of length at least k; If M has at least two hinges, then either M = Q′H_{k}W, k ≥ 3, or M = R′H_{k}W, k ≥ 2, with Q′ ∈ J_{1}^{0}, R′ ∈ J_{1}^{1} and W ∈ K_{1}\J_{1}.

Thus we have the functional equation:

\begin{aligned}K_{1}(x) = & J_{1}(x) + J_{1}^{0}(x)\frac{x^{2}}{1−x}(J_{1}(x) + 1) + J_{1}^{0}(x)\frac{x^{3}}{1−x}J_{0}(x) + J_{1}^{1}(x)\frac{x}{1−x}(J_{1}(x) + 1)+ \\ & J_{1}^{1}(x)\frac{x^{2}}{1−x}J_{0}(x) + J_{1}^{0}(x)\frac{x^{3}}{1−x}(K_{0}(x) − J_{0}(x)) + J_{1}^{1}(x)\frac{x^{2}}{1−x}(K_{0}(x) − J_{0}(x)) \end{aligned} .

– Let M be a Motzkin path in K_{2}. We have either M = H_{k}S, k ≥ 1, or M = H_{k}T, k ≥ 2 with S ∈ J_{1}^{0} ∪ J_{1}^{1}, T ∈ J_{0}^{0} ∪ J_{0}^{1} ∪ {ϵ} and H_{k} is a hinge of length at least k.

Thus we have the functional equation:

K_{2}(x) = J_{1}(x)\frac{x}{1 − x} + (K_{0}(x) + 1)\frac{x^{2}}{1 − x}.

Using the Lemma 16, a simple calculation with Maple gives the generating function K(x) = K_{0}(x) + K_{1}(x) + K_{2}(x) for the set K.

References

[1] J.-L. Baril and A. Petrossian, Equivalence of Dyck paths modulo some statistics, Discrete Math. 338 (2015), 655–660.

[2] E. Barcucci, R. Pinzani and R. Sprugnoli, The Motzkin family, Pure Math. Appl. Ser. A 2 (1991), 249–279.

[3] C. Brennan and S. Mavhungu, Peaks and valleys in Motzkin paths, Quaest. Math. 33 (2010), 171–188.

[4] E. Deutsch, Dyck path enumeration, Discrete Math. 204 (1999), 167–202.

[5] R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Combin. Theory Ser. A 23 (1977), 291–301.

[6] D. Drake and R. Gantner, Generating functions for plateaus in Motzkin paths, J. Chungcheong Math. Society 25 (2012), 475–489.

[7] T. Mansour, Statistics on Dyck paths, J. Integer Sequences 9 (2006), Article 06.1.5.

[8] T. Mansour, Counting peaks at height k in a Dyck path, J. Integer Sequences 5 (2002), Article 02.1.1.

[9] T. Mansour and M. Shattuck, Counting Dyck paths according to the maximum distance between peaks and valleys, J. Integer Sequences 15 (2012), Article 12.1.1.

[10] T. Mansour, M. Schork and Y. Sun, Motzkin numbers of higher rank: Generating function and explicit expression, J. Integer Sequences 10 (2007), Article 07.7.4.

[11] D. Merlini, R. Sprugnoli and M. C. Verri, Some statistics on Dyck paths, J. Statis. Plann. Inference 101 (2002), 211–227.

[12] A. Panayotopoulos and A. Sapounakis, On the prime decomposition of Dyck paths, J. Combin. Math. Combin. Comput. 40 (2002), 33–39.

[13] P. Peart and W. J. Woan, Dyck paths with no peaks at height k, J. Integer Sequences 4 (2001), Article 01.1.3.

[14] H. Prodinger and S. Wagner, Minimal and maximal plateau lengths in Motzkin paths, 2007 Conference on Analysis of Algorithms, Discrete Math. Theor. Comput. Sci. Proc., AH (2007), 353–364.

[15] A. Sapounakis, I. Tasoula and P. Tsikouras, Counting strings in Dyck paths, Discrete Math. 307 (2007), 2909–2924.

[16] A. Sapounakis, I. Tasoulas and P. Tsikouras, Some strings in Dyck paths, Australasian J. Combin. 39 (2007), 49–72.

[17] A. Sapounakis and P. Tsikouras, Couting peaks and valleys in k-colored Motzkin words, Electron. J. Comb. 12 (2005), Article 12.

[18] N. J. A. Sloane: The On-line Encyclopedia of Integer Sequences, available electronically

at http://oeis.org.

[19] Y. Sun, The statistic “number of udu’s” in Dyck paths, Discrete Math. 287 (2004), 177–186.

[20] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999.

2010 Mathematics Subject Classification: Primary 68R15. Key words: Motzkin path, equivalence relation, statistics.

(Concerned with sequences \underline{A001405}, \underline{A000079}, \underline{A191385}, \underline{A132916}, \underline{A000045}, \underline{A165407}, and \underline{A191385}.)

Received January 12 2015; revised versions received May 20 2015; June 4 2015. Published in Journal of Integer Sequences, June 16 2015.

Return to Journal of Integer Sequences home page.