From (2, 3)-Motzkin Paths to Schröder Paths

Sherry H. F. Yan Department of Mathematics Zhejiang Normal University Jinhua 321004 P. R. China

                          hfy@zjnu.cn

Abstract

In this paper, we provide a bijection between the set of restricted (2, 3)-Motzkin paths of length n and the set of Schröder paths of semilength n. Furthermore, we give a one-to-one correspondence between the set of (2, 3)-Motzkin paths of length n and the set of little Schröder paths of semilength n + 1. By applying the bijections, we get the enumerations of Schröder paths according to the statistics “number of udd’s” and “number of hd’s”.

1 Introduction and notations

A (2,3)-Motzkin path of length n is a lattice path from (0, 0) to (n, 0) that does not go below the x-axis and consists of up steps u = (1, 1), down steps d = (1, −1) and level steps l = (1, 0), where each up step is possibly colored by u_{1} or u_{2} and each level step is possibly colored by l_{1}, l_{2} or l_{3}. such Motzkin paths have been extensively studied by Woan [9, 10]. Ordinary Motzkin paths arise when both level steps and up steps are only of one color. They are counted by the so-called Motzkin numbers [1]. Denote by M_{n} the set of (2, 3)-Motzkin paths of length n and m_{n} its cardinality. Recall that m_{n} equals n+1-th super-Catalan number or little Schröder number (\underline{A001003} in [5]). A restricted (2,3)-Motzkin path of length n is a (2, 3)-Motzkin path such that each level step on the x-axis is possibly colored by l_{2} or l_{3}. Denote by M^{∗}_{n} the set of restricted (2, 3)-Motzkin paths of length n and m_{n}^{∗} its cardinality. m_{n}^{∗} equals n-th large Schröder number (\underline{A006318} in [5]).

A Schröder path of semilength n is a lattice path from (0, 0) to (2n, 0) that does not go below the x-axis and consists of up steps u = (1, 1), down steps d = (1, −1) and horizontal steps h = (2, 0). They are counted by the larger Schröder numbers (\underline{A006318} in [5]). Denote by R_{n} the set of Schröder paths of semilength n and r_{n} its cardinality. A little Schröder path is a Schröder path without horizontal steps on the x-axis. Denote by S_{n} the set of little Schröder paths of semilength n and s_{n} its cardinality. It is well known that s_{n} is the n-th super-Catalan number or little Schröder number (\underline{A001003} in [5]) with s_{0} = s_{1} = 1, s_{2} = 3, s_{3} = 11. Hence we have the relation s_{n+1} = m_{n} and r_{n} = m_{n}^{∗} for n ≥ 0 .

In this paper, we aim to provide a bijection between the set of restricted (2, 3)-Motzkin paths of length n and the set of Schröder paths of semilength n. By refining this bijection, we obtain a bijection between the set of (2, 3)-Motzkin paths of length n and the set of little Schröder paths of semilength n+1. The enumeration of Dyck paths according to semilength and various other parameters has been extensively studied in several papers [4, 3, 8]. The enumeration of Dyck paths according to the statistic “number of udu’s” has been recently considered by Sun[8]. His results was generalized by Mansour [3] by studying the statistic “number of uu … udu’s” and the statistic “number of udud … udu’s”. However, there are few results on the enumerations of little Schröder paths according to semilength and various other parameters. By applying bijections, we get the enumerations of Schröder paths according to the statistics: “ number of udd’s ” and “ number of hd’s”.

The organization of this paper is as follows. In Section 2, we give a bijection between the set of restricted (2, 3)-Motzkin paths of length n and the set of Schröder paths of semilength n. By refining this bijection, one-to-one correspondence between the set of (2, 3)-Motzkin paths of length n and the set of little Schröder paths of semilength n + 1 is found. In section 3, by specializing the bijections, we get the enumerations of Schröder paths according to statistics: “ number of udd’s ” and “ number of hd’s”.

2 Bijections between (2, 3)-Motzkin paths and Schröder paths

In this section, our goal is to construct a bijection between the set of restricted (2, 3)-Motzkin paths of length n and Schröder paths of semilength n. By refining this bijection we get a bijection between (2, 3)-Motzkin paths of length n and little Schröder paths of semilength n + 1.

Before giving the bijections, we recall some definitions. For any step in a lattice path, we say that it is at level k if the y-coordinate of its end point equals k. For an up step s at level k, its corresponding down step is defined to be the leftmost down step at level k − 1 right to s. Similarly, for a down step s at level k, its corresponding up step is defined to be the rightmost up step at level k + 1 left to s. In a Schröder path, the level of udd is equal to that of its step u and the level of hd is equal to that of its step h. A udd is said to be high if its level is larger than two. A hd is said to be high if its level is lager than one. In a Schröder path, a udd … d consists of an up step and at least two immediately followed down steps; similarly, a hd … d consists of a horizontal step and immediately followed down steps; a udd … d or hd … d is called maximal if it is not followed by another down step; a peak is said to be single if it is not followed immediately by a down step; similarly, a horizontal step is said to be single if it is not followed immediately by a down step; a down step is called a tail if it is the last down step of a maximal udd … d or hd … d; an up step is called a head

[figure: a; b; c; d; e; f]

Figure 1: A Schröder path

if it is the up step of udd … d.

Figure 1 is an illustration of the above definitions. Steps a, c, and d are at levels 1, 3, and 2, respectively; the corresponding down step of the step a is the step f and the corresponding up step of the step d is the step b; the step c altogether with the step d forms a maximal hd; the steps from e to f in the Schröder path form a maximal uddd; the first peak from left to right is a single peak; the second and the third horizontal steps from left to right are single; steps d and f are tails; the step e is a head.

Now we construct a map τ : M^{∗}_{n} → R_{n}. Given a restricted (2, 3)-Motzkin path P of length n, we can obtain a lattice path τ(P) by the following procedure.

1. Firstly, for each down step x, find its corresponding up step y. If y is at level k and colored by u_{1} (resp. u_{2}) and there are m level steps colored by l_{1} at level k between x and y, then remove the color of y, change x to h (resp. ud) and add m + 1 consecutive down steps immediately after h (resp. ud).

2. Secondly, change each level step colored by l_{1} to an up step.

3. Lastly, change each level step colored by l_{2} to a peak, each level step colored by l_{3} to a horizontal step.

It is clear that the obtained path τ(P) is a Schröder path of semilength n.

Figure 2 is an illustration of the map τ.

Conversely, we can obtain a (2, 3)-Motzkin path from a Schröder path. Given a Schröder path P of semilength n, we get a lattice path by the following procedure.

1. Firstly, change each single peak to a level step colored by l_{2} and each single horizontal step to a level step colored by l_{3}.

2. secondly, for each non-head up step x, find its corresponding down step y. If y is a tail of a maximal hd … d, then color x by u_{1} and change this hd … d to one down step. If y is a tail of a maximal udd … d, then color x by u_{2} and change this udd … d to one down step. Otherwise, change x to a level step colored by l_{1}.

It is easy to check that the obtained path is a (2, 3)-Motzkin paths of length n. Note that for any non-head up step at level one, its corresponding down step must be a tail of a maximal udd … d or hd … d. Hence, there is no level step colored by l_{1} at level zero in the obtained path. That is to say, the obtained path is a restricted (2, 3)-Motzkin path. Therefore, the map τ is reversible. Figure 3 is an illustration of the inverse map of τ.

[figure: ⟶; ⟶; l_{2}; l_{3}; l_{3}; ⟶; l_{2}; l_{1}; l_{3}; l_{3}; l_{2}; u_{2}; l_{1}; u_{1}; l_{3}; l_{3}]

Figure 2: From a restricted (2, 3)-Motzkin path to a Schröder path

[figure: ⟶; l_{2}; u_{2}; l_{1}; u_{1}; l_{3}; l_{3}; ⟶; l_{2}; l_{3}; l_{3}]

Figure 3: From a Schröder path to a (2, 3)-Motzkin path Theorem 1. The map τ is a bijection between the set of restricted (2, 3)-Motzkin paths of length n and Schröder paths of semilength n.

From the construction of the bijection τ, we immediately get the following corollary.

Corollary 2. The number of up steps colored by u_{1} in a restricted (2, 3)-Motzkin path is equal to that of hd’s in the corresponding Schröder path. The number of up steps colored by u_{2} in a restricted (2, 3)-Motzkin path is equal to that of udd’s in the corresponding Schröder path.

With the bijection τ, we can construct a map ϕ : M_{n} → S_{n+1}. Given a (2, 3)-Motzkin path P, it can be uniquely decomposed as P = P_{1}l_{1}P_{2} … l_{1}P_{m}, where each P_{i} is possibly empty restricted (2, 3)-Moztkin path. Now we can construct ϕ(P) as follows: firstly, we get a (2, 3)-Motzkin path P′ = l_{1}P_{1}l_{1}P_{2} … l_{1}P_{m} of length n + 1 by adding a level step colored by l_{1} at the beginning of P; then ϕ(P) = uτ(P_{1})duτ(P_{2})d … uτ(P_{m})d. Obviously, the obtained path ϕ(P) is a little Schröder path of semilength n + 1 and the map ϕ is invertible. Hence from Theorem 1 and Corollary 2, we have the following conclusions.

Theorem 3. The map ϕ is a bijection between the set of (2, 3)-Motzkin paths of length n and little Schröder paths of semilength n + 1.

Corollary 4. The number of up steps colored by u_{1} in a (2, 3)-Motzkin path is equal to that of high hd’s in the corresponding little Schröder path. The number of up steps colored by u_{2} in a (2, 3)-Motzkin path is equal to that of high udd’s in the corresponding little Schröder path.

3 Statistics on Schröder paths

In this section, we begin to study the statistics: “number of udd’s” and “number of hd’s” on Schröder paths.

Denote by m_{n,k} the number of (2,3)-Motzkin paths of length n and with k up steps. Then we have the following consequence.

Lemma 5.

m_{n,k} = 3^{n−2k}2^{k}\binom{n}{2k}c_{k},

where c_{k} = \frac{1}{k+1} \binom{2k}{k} is the k-th Catalan number (\underline{A000108} in [5]).

Proof. Given a Dyck path P of length 2k, we can construct a (2, 3)-Motzkin path of length n and with k up steps as follows: firstly, insert n − 2k level steps between the 2k + 1 positions between the steps of P. The number of ways to inserting such steps is counted by \binom{2k+1+n−2k−1}{n−2k} = \binom{n}{2k}. Then assign the colors to level steps and up steps. There are 3^{n−2k}2^{k} ways to arrange colors. It is clear that the obtained path is a (2, 3)-Motzkin path. Conversely, given a (2, 3)-Motzkin path with k up steps, we can remove all the colors of steps and all the level steps to get a Dyck path of length k. This completes the proof.

Summing over all the possible k’s, we get

m_{n} = ∑_{0≤k≤⌊ \frac{n}{2} ⌋} 3^{n−2k}2^{k}\binom{n}{2k}c_{k},

which is another expression of the little Schröder numbers.

From the bijection τ, we see that if there is no level step colored by l_{1} in a restricted (2, 3)- Motzkin path, then there is no uddd or hdd in its corresponding Schröder path. While, by the same way as the proof of Lemma 5, we can get that the number of such (2, 3)-Motzkin paths of length n and with k up steps is equal to 2^{n−k}\binom{n}{2k}c_{k}. Hence, by Theorem 1 and Corollary 2, the following conclusion holds immediately.

Corollary 6. The number of Schröder paths of semilength n and with altogether k udd and hd’s but without uddd or hdd is equal to

2^{n−k}\binom{n}{2k}c_{k}.

Similarly, if there is no level step colored by l_{1} and the up steps are only colored by u_{1} (resp. u_{2}) in a restricted (2, 3)-Motzkin path, then there is no uddd and hd (resp. udd)in its corresponding Schröder path. By simple computation, the number of such (2, 3)-Motzkin paths of length n and with k up steps is equal to 2^{n−2k}\binom{n}{2k}c_{k}. Hence, by Theorem 1 and Corollary 2, the following two conclusions are obtained.

Corollary 7. The number of Schröder paths of semilength n and with k udd’s but without uddd or hd is equal to

2^{n−2k}\binom{n}{2k}c_{k}.

Corollary 8. The number of Schröder paths of semilength n and with k hd’s but without udd or hdd is equal to

2^{n−2k}\binom{n}{2k}c_{k}.

A (2, 3)-Motzkin path with up steps colored by u_{2} and level steps colored by l_{2} can be reduced to an ordinary Motzkin path. It is well known that the number of ordinary Motzkin paths of length n and with k up steps is equal to \binom{n}{2k}c_{k}. From the construction of the bijection τ, a (2, 3)-Motzkin path with up steps colored by u_{2} and level steps colored by l_{2} corresponds to a Dyck path without uddd. Hence, by Theorem 1 and Corollary 2, the following conclusion is obtained.

Corollary 9. The number of Dyck paths of semilength n and with k udd’s but without uddd is equal to \binom{n}{2k}c_{k}.

By Theorem 3, Corollary 4 and Lemma 5, we get the following result.

Corollary 10. little Schröder paths of semilength n + 1 and with altogether k high udd and hd’s are counted by

3^{n−2k}2^{k}\binom{n}{2k}c_{k}.

If there is no up steps colored by u_{1} (resp. u_{2}) in a (2, 3)-Motzkin path, then there is no high udd (resp. high hd) in its corresponding Schröder path. It is easy to get that the number of such (2, 3)-Motzkin paths of length n and with k up steps is equal to 3^{n−2k}\binom{n}{2k}c_{k}. By Theorem 3 and Corollary 4, we get the following two results.

Corollary 11. The number of little Schröder paths of semilength n+1 and with k high udd’s but no high hd is equal to

3^{n−2k}\binom{n}{2k}c_{k}.

Corollary 12. The number of little Schröder paths of semilength n + 1 and with k high hd’s but no high udd is equal to

3^{n−2k}\binom{n}{2k}c_{k}.

From the construction of the bijection ϕ, a (2, 3)-Motzkin path with up steps colored by u_{2} and level steps colored by l_{1} or l_{2} corresponds to a Dyck path. It is easy to get that the number of such (2, 3)-Motzkin paths of length n and with k up steps equals 2^{n−2k}\binom{n}{2k}c_{k}. Hence, by Theorem 3 and Corollary 4, the following conclusion is obtained.

Corollary 13. The number of Dyck paths of length 2n + 2 and with k high udd’s is equal to

2^{n−2k}\binom{n}{2k}c_{k}.

Acknowledgments. The author would like to thank the referee for his helpful suggestions.

References

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

[2] G. Kreweras, Joint distributions of three descriptive parameters of bridges. Combinatoire Enumerative, 177–191, Lecture Notes in Math., Vol. 1234, Springer, Berlin, 1986.

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

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

[5] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences,

    http://www.research.att.com/∼njas/sequences.

[6] R. A. Sulanke, A symmetric variation of distribution of Kreweras and Poupard, J. Statist. Plann. Inference, 34 (1993) 291–303.

[7] R. A. Sulanke, Catalan path statistics having the Narayana distribution, Discrete Math., 180 (1998) 369–389.

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

[9] Wen-jin Woan, A recursive relation for weighted Motzkin sequences, J. Integer Sequences 8 (2005), Article 05.1.6.

[10] Wen-jin Woan, A relation between restricted and unrestricted weighted Motzkin paths, J. Integer Sequences 9 (2006), Article 06.1.7.

[11] D. Zeilberger, Six Études in generating functions, Intern. J. Computer Math., 29 (1989) 201– 215.

2000 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: Schröder path, (2, 3)-Motzkin path.

(Concerned with sequences \underline{A000108}, \underline{A001003}, and \underline{A006318}.)

Received June 18 2007; revised version received August 24 2007. Published in Journal of Integer Sequences, August 24 2007.

Return to Journal of Integer Sequences home page.