A Bijection Between 3-Motzkin Paths and Schröder Paths With No Peak at Odd Height

Louis W. Shapiro^{1} Mathematics Department Howard University Washington, DC 20059 USA

                      lshapiro@howard.edu

Carol J. Wang Center for Combinatorics, LPMC-TJKLC Nankai University, Tianjin 300071 P. R. China

                  wangjian@cfc.nankai.edu.cn

Abstract A new bijection between 3-Motzkin paths and Schröder paths with no peak at odd height is presented, together with numerous consequences involving related combinatorial structures such as 2-Motzkin paths, ordinary Motzkin paths and Dyck paths.

1 Introduction

We define k-Motzkin paths as paths from (0, 0) to (n, 0) not going below x-axis using steps U = (1, 1), D = (1, −1) and L = (1, 0) where the L steps can be any of k colors. The cases with k = 0, 1, 2 and 3 counting these paths yield

k = 0, Catalan numbers, 1, 0, 1, 0, 2, 0, 5, 0, 14, 0, …, \underline{A097331};

1All correspondence should be directed to this author.

k = 1, Motzkin numbers, 1, 1, 2, 4, 9, 21, 51, 127, …, \underline{A001006};
k = 2, Catalan numbers(C_{n+1}), 1, 2, 5, 14, 42, 132, …, \underline{A000108};
k = 3, Harary-Read Benzene numbers, 1, 1, 3, 10, 36, 137, 543, …, \underline{A002212}.

The ‘A’ numbers are from Sloane’s Encyclopedia [8].

Harary-Read Benzene numbers count the number of restricted hexagonal polyominoes with n cells and equivalently rooted planar trees where the outdegree of each vertex is 0, 1 or 2. If the outdegree is 1, then it can be a left, right, or middle child. If the outdegree is 2, the vertex must have a left and right child. Denote such trees by HR-trees. This last condition prohibits the configuration shown below.

We denote the generating function (GF for short) for the k-Motzkin numbers as M_{[k]}. If we change the level step requirement by one kind of level step of length 2, we get the Schröder paths and the sequence of numbers counting the Schröder paths starts 1, 2, 6, 22, 90, 394, …, \underline{A006318}.

Returning to the k-Motzkin paths but not allowing any level steps at height 0, we have the k-Riordan paths. This yields

k = 1, the Riordan numbers, 1, 0, 1, 1, 3, 6, 15, 36, 91, …, \underline{A005043};

k = 2, the Fine numbers, 1, 0, 1, 2, 6, 18, 57, …, \underline{A000957};

k = 3, the 3-Riordan numbers, 1, 0, 1, 3, 11, 42, 167, 684, …, \underline{A117641}.

For Benzene molecules A, B, C, D, …, the 3-Riordan numbers count the number of ways pasting Benzene rings with no attachments occurring on the dark edges. The 3-Riordan numbers also count the number of HR-trees with no middle children on the rightmost branch. Figure 1 is a small example to illustrate these concepts.

The GF for counting k-Riordan paths is denoted R_{[k]}. More detail can be found in [9]. For information about M_{[3]}, see also [1] and [6].

The basic identities for these GF s are

M_{[k]} = 1 + kzM_{[k]} + z^{2}M_{[k]}^{2} and R_{[k]} = 1 + z^{2}M_{[k]}R_{[k]}.

The two generating functions are linked by the identity

M_{[k]} = R_{[k]} + R_{[k]} · kz · R_{[k]} + R_{[k]} · kz · R_{[k]} · kz · R_{][k]} + ⋯

= \frac{R_{[k]}}{1 − kzR_{[k]}} ,

Base A B C D  ⟺  A middle B C left  D

Figure 1: Benzene Molecules and the corresponding HR-tree.

where, for instance, R_{[k]} · kz · R_{[k]} accounts for k-Motzkin paths with one level step at height 0.

This research started while investigating Möbius transformations of generating functions. It was noticed that \frac{R_{[1]}}{1−zR_{[1]}} = M_{[1]} yields the Motzkin numbers, and \frac{R_{[2]}}{1−2zR_{[2]}} yields the Catalan

numbers. Next in the series is M_{[3]} = \frac{R_{[3]}}{1−3zR_{[3]}} . Consulting Sloane [8] yielded the peculiar fact that these numbers also counted Schröder paths with no peak at odd height. This fact was noticed by Emeric Deutsch who outlined a proof via generating function for us. However such a coincidence seemed worthy of a more combinatorial approach.

In this paper, we present an easy bijection between the Schröder paths of length 2n with no peak at odd height and 3-Motzkin paths of length n − 1. One consequence of this simple bijection is that many new occurrences of paths counted by the Catalan, Motzkin, Fine, and Riordan numbers can be found as Schröder paths with various restrictions. We will examine a few such cases in detail and then list some of the others.

A recent paper of Yan [10] discusses a different bijection between (2, 3)-Motzkin paths and Schröder paths for the purpose of enumerating the UDD and LD subsequences. For more information about the Fine number sequences, see [2] and [4]. Some useful generating function identities are discussed in [3]. Another paper of definite interest [7] of Mansour, Schork, and Sun discusses Motzkin paths where not only level steps but also up and down steps are colored. In particular if the up steps are bicolored and neither level nor down steps are, then the sequence \underline{A025235} which starts 1, 1, 3, 7, 21, 61, 191, … is obtained. If both level and up steps are bicolored the result is the sequence \underline{A071356} starting 1, 2, 6, 20, 72, 272, 1064, . . ..

2 The bijection

We describe the bijection, denoted by ϕ, between Schröder paths of length 2n with no peak at odd height and 3-Motzkin paths of length n − 1. Let ω be a Schröder path of length 2n with no peak at odd height. First interchange peaks and level steps. We will call this the toggle. We now have a Schröder path with no level steps at even height. Next eliminate the first step (U) and the last step (D), and denote the remaining path by ω′. Thus, ω′ is a Schröder path except that it can go down to height −1. We call this step push down. At this point we have no level steps at odd height. We define the bijection ϕ as follows. Traverse ω′ from left to right two steps at a time where L is regarded as two steps:

• for consecutive UU (resp. DD) steps, set ϕ(UU) = u (resp. ϕ(DD) = d);

• set ϕ(L) = l;

• set ϕ(UD) = ∧;

• set ϕ(DU) = v.

It is easy to see that we have obtained a 3-Motzkin path and also that the mapping can be easily reversed. More precisely, a Schröder path of length 2n without peaks at odd height corresponds to a 3-Motzkin path of length n − 1. For an example, see Figure 2.

(0, 0)  (19, 0) We get a 3-Motzkin path from (0, 0) to (19, 0) with v := ∧ := l := L ⟷ l peak (UD) ⟷ ∧ valley (DU) ⟷ v (0, 0)  (38, 0) Start with a Schröder path from (0, 0) to (40, 0) and do the toggle and push down steps (0, 0)  (40, 0)

Figure 2: The bijection ϕ

Bijective correspondences. Table 1 lists features carried by the bijection ϕ from Schröder paths to 3-Motzkin paths. For instance, a level step at height 0 becomes a peak at height 1 after the toggle. After the push down we have a peak at height 0. Counting two steps at a time splits the peak into parts of two consecutive valleys. If the original level step is at either end of the Schröder path then half of it would be taken by the push down and the other half would contribute to one valley.

The other cases follow by similar reasoning.

Schröder paths  3-Motzkin paths

(with no peaks at odd height)

L steps at height 0  vv consecutive steps at height 0

or a v at either end of the path

L steps at even height 2k (k ≥ 1)  uv, vd, vv, ud consecutive steps

where either u or v is at height k − 1 (k ≥ 1)

L steps at odd height  ∧ steps
peaks  l steps
UU or UL  u steps

where the first U is at odd height

DD or LD  d steps

where the second D is at odd height

Table 1: Bijective correspondences.

3 Special Cases

Recall that 2-Motzkin paths are counted by the Catalan numbers, C_{n+1}. If we allow no level steps at height 0, we have the Fine numbers. Similarly we get Motzkin paths by allowing just one kind of level step. If we then forbid level steps at height 0, we obtain the Riordan paths. Thus applying the ϕ^{−1} algorithm will carry all these variations simultaneously.

As one example, we consider the case where the level steps for the 2-Motzkin paths are labeled l and v. Starting to apply ϕ^{−1} gives us the building blocks UU, L, DU and DD with the Catalan condition that the number of DDs never exceeds the number of UUs. We now have L steps possible at even height, peaks at even height. At this stage, the paths could go as low as the line y = −1.

We add a single U step at the beginning, a D step at the end (the push up) and we now have Schröder paths with level steps and peaks only at odd height. These are counted by the Catalan number, C_{n}. If we complete the ϕ^{−1} algorithm by interchanging level steps and peaks (the toggle), we again have peaks and level steps allowed only at even height. The 5 such (Catalan) Schröder paths from (0, 0) to (6, 0) are in Figure 3.

If we also prohibit L steps at height 0, we get the Fine numbers, 1, 0, 1, 2, 6, 18, 57, . . .. The 6 (Fine) Schröder paths from (0, 0) to (8, 0) without toggle and push up steps are shown in Figure 4. After the toggle and the push up, we have the elevated Schröder paths with level steps at height 2k (k ≥ 1) and peaks at height 2k (k ≥ 2).

toggle

To obtain one of the settings for the Motzkin numbers, we eliminate l also. This gives us Schröder paths without level steps and peaks only at odd height. If we interchange peaks Figure 3: (Catalan) Schröder paths of length 6.

Figure 4: (Fine) Schröder paths of length 8.

and level steps we get Schröder paths with no peaks, and level steps only at even height. Here in Figure 5 are the four (Motzkin) Schröder paths from (0, 0) to (8, 0).

toggle

Figure 5: (Motzkin) Schröder paths of length 8.

In these last two settings we can eliminate peaks at height 1 (respectively, level steps at height 0). For paths from (0, 0) to (10, 0), we get three (Riordan) Schröder paths. We show these in Figure 6 with and without the toggle.

3.1 Remarks

We now list some of the other possibilities. We have \binom{3}{2} ways to choose 2 of 3 kinds of level steps each leading to a Catalan setting and with it a Fine setting. By then eliminating one of the two kinds of level steps, we obtain two settings for the Motzkin numbers and then Riordan numbers. By not using the toggle, we double the numbers of possibilities. When the v step is not one of the level steps, we can eliminate the push down-push up steps. Since we proceed two steps at a time this also yields new settings.

Figure 6: (Riordan) Schröder paths of length 10.

The complete ϕ^{−1} algorithm consists of both the push up and toggle steps. As fascinating as each setting is individually, the list gets quite long quite quickly.

3.2 Catalan numbers

We call a path is elevated if the path is strictly above the x-axis except the initial and end points.

If the level steps for the 2-Motzkin paths are labeled ∧ and l, then by the complete ϕ^{−1} algorithm, we have the elevated Schröder paths with no peaks at odd height, no valley at even height and each L at even height occurring as part of a ULD subsequence.

If the level steps are either ∧ or v, then the complete ϕ^{−1} algorithm will give us the Schröder paths with no peaks.

Eliminating all the level steps from 3-Motzkin paths, we have Dyck paths, which are counted by aerated Catalan numbers, whose first several terms are 1, 0, 1, 0, 2, 0, 5, 0, . . .. By the complete ϕ^{−1} algorithm, we have the elevated Schröder paths with no peaks, valleys only at odd height and level steps only at height 2k (k ≥ 1) and occurring as part of a ULD subsequence.

3.3 Motzkin numbers

In this section, we consider Motzkin paths, first with ∧ as the level step, then with l. If the level steps of Motzkin paths are labeled ∧, then the complete ϕ^{−1} algorithm pro-

duces the elevated Schröder paths with neither valley at even height nor peaks and where each L at even height occurs as part of a ULD subsequence.

If we denote the level steps in Motzkin paths by l and apply the complete inverse algorithm, then we obtain the elevated Schröder paths with no peaks at odd height, no valley at even height and L steps only at height 2k (k ≥ 1) occurring as part of ULD subsequences.

3.4 Fine numbers

We next consider 2-Riordan (i.e., Fine) paths with two kinds of level steps, ∧ and l, allowed except at height 0 where there are no level steps. Applying the complete ϕ^{−1} algorithm, we have the elevated Schröder paths with no valley at even height, peaks only at height 2k (k ≥ 2), L steps at height ≥ 2 and each L at even height occurring as part of a ULD subsequence.

If the level steps are either ∧ and v and we apply the complete ϕ^{−1} algorithm, we end up with elevated Schröder paths with no peaks and L steps at height k ≥ 2 .

Eliminating all level steps in 3-Motzkin paths and forbidding peaks at height 1, we will also have the Fine numbers. By applying the complete ϕ^{−1} algorithm, we have the elevated Schröder paths with no peaks, no valleys at even height, L steps only at height 2k (k ≥ 2) and occurring as part of ULD subsequences.

3.5 Riordan numbers

If we eliminate the level steps at height 0 in Motzkin paths, we have the Riordan paths. If the level steps in Riordan paths are v’s, then by the complete ϕ^{−1} algorithm, we have

elevated Schröder paths with no peaks and L steps at height 2k (k ≥ 1).

If the level steps are all labeled ∧, then the complete ϕ^{−1} algorithm leads to the elevated Schröder paths with no peaks, no valleys at even height, level steps at height ≥ 2 and level steps at even height occurring as part of ULD subsequences.

If we consider the case where level steps are l’s and apply the complete ϕ^{−1} algorithm, then we have the elevated Schröder paths with peaks only at even height ≥ 4, no valley at even height, level steps only at height 2k (k ≥ 1) and occurring as part of ULD subsequences.

Some results, similar to ours, but not in a Schröder context appear in a recent paper of Eu, Liu and Yeh [5].

4 Acknowledgments

This work was supported by the 973 Project, the PCSIRT Project of the Ministry of Education, the Ministry of Science an Technology, and the National Science Foundation of China. The first author was also supported by the NSF grant HRD 0401697.

References

[1] S. J. Cyvin, B. N. Cyvin, J. Brunvoll, and E. Brendsdal, Enumeration and classification of certain polygonal systems representing polycyclic conjugated hydrocarbons: annelated catafusenes, J. Chem. Inf. Comput. Sci. 34 (1994), 1174–1180.

[2] E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math. 204 (1999), 167–202.

[3] E. Deutsch and L. Shapiro, Seventeen Catalan identities, Bulletin of the ICA 31 (2001), 31–38.

[4] E. Deutsch and L. Shapiro, A bijection between ordered trees and 2-Motzkin paths and its many consequences, Discrete Math. 256 (2002), 655–670.

[5] S. Eu, S. Liu, and Y. N. Yeh, Dyck paths with peaks avoiding or restricted to a given set, Studies in App. Math. 111 (2003), 453–465.

[6] F. Harary and R. C. Read, The enumeration of tree-like polyhexes, Proc. Edinb. Math. Soc. 17 (1970), 1–13.

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

[8] N. J. A. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press, San Diego, 1995. Also on-line at The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/^{∼}njas/sequences/index.html.

[9] R. P. Stanley, Enumerative Combinatorics, Vol. 2, Chapter 6, Cambridge Uiversity Press, 1999, and see also website: http://www-math.mit.edu/∼rstan/ec, the Catalan Addendum.

[10] S. H. F. Yan, From (2, 3)-Motzkin paths to Schröder Paths, J. Integer Seq. 10 (2007), Article 07.9.1.

2000 Mathematics Subject Classification: 05A05, 05A15, 05A19. Keywords: 3-Motzkin paths, Schröder paths, 2-Motzkin paths, Motzkin paths, Dyck paths, Fine paths, Riordan paths, Catalan numbers.

(Concerned with sequences \underline{A000108}, \underline{A000957}, \underline{A001006}, \underline{A002212}, \underline{A005043}, \underline{A006318}, \underline{A097331}, \underline{A117641}.

Received September 2 2008; revised version received February 21 2009. Published in Journal of Integer Sequences, March 14 2009.

Return to Journal of Integer Sequences home page.