Recent Results on Paths, Permutations and Trees

William Y. C. Chen ^[1]

Center for Combinatorics, LPMC

Nankai University, Tianjin 300071, P. R. China

chen@nankai.edu.cn

Abstract. Full Text PDF

We will give a brief survey of some recent results on paths, permutations and trees obtained by the group at Center for Combinatorics, Nankai University. These results involve, Motzkin paths, Dyck paths, plane trees, partitions and involutions with forbidden patterns.

· Dyck paths and -noncrossing matchings

We construct a bijection between -noncrossing matchings and pairs of noncrossing Dyck paths with the same origin and destination. From our correspondence it follows an enumerative formula for the number of poor -noncrossing partitions on elements. This answers a question recently raised by M. Klazar [7]. We also present a labeling for the steps of a pair of noncrossing Dyck paths, which leads to a direct construction for -nonnesting matchings. This correspondence turns out to be simpler than the one given by D. Gouyou-Beauchamps [4].

· Restricted partitions and labelled -Motzkin paths

We establish correspondences between two classes of -free and -free partitions and labelled -Motzkin paths with certain restrictions. These labelled -Motzkin paths and restricted partitions serve as two combinatorial interpretations for the sequences mentioned by E. Barcucci, A. D. Lungo, E. Pergola and R. Pinzani [1], and can be viewed as a “discrete continuity" between Motzkin and Catalan numbers. As an application of the labeling scheme, we obtain a bijection between -regular -free partitions and connected -free partitions, which gives a simpler correspondence than the one given by J. N me ek and M. Klazar in term of nonnegative words [8].

· Generating trees for -avoiding involutions

Using the methodology of generating trees, we obtain a bijection between the set of -avoiding involutions and Motzkin paths. It was conjectured by O. Guibert [5] that -avoiding involutions are counted by the Motzkin numbers. It is easy to see that 3214-avoiding involutions are in one-to-one correspondence with 1432-avoiding involutions by reverse complementation. Recently, Jaggard [6] proved the conjecture of Guibert by establishing a correspondence between 3214-avoiding involutions and 1234-avoiding involutions. Using our generating tree rules, we may derive a bijection between 3214-avoiding involutions and Motzkin paths. Special cases of this bijection lead to some known results of Simion and Schmidt [9], and E. Deutsch, A. Robertson and D. Saracino [3]. Some new results are derived as well.

· Colored combinatorial objects

We introduce the structures of colored Dyck paths, colored plane trees and colored hilly poor noncrossing partitions. We obtain enumerative formulas for these structures by using generating functions and give bijective proofs as well. As a consequence, we answer two questions posed by C. Coker [2]. Our bijections are related to the following identities:

References

[1] E. Barcucci, A. D. Lungo, E. Pergola and R. Pinzani, From Motzkin to Catalan permutations, Discrete Math., 217 (2000), 33-49.

[2] C. Coker, Enumerating a class of lattice paths, Discrete Math. 271 (2003) 13-28.

[3] E. Deutsch, A. Robertson, D. Saracino, Refined restricted involutions, Europ. J. Combin. to appear.

[4] D. Gouyou-Beauchamps, Standard Young tableaux of height and , Europ. J. Combin., 10 (1989), no. 1, 69-82.

[5] O. Guibert, Combinatoire des permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young, Ph. D. Thesis, University Bordeaux I, France, 1995.

[6] A. D. Jaggard, Prefix exchanging and pattern avoidance by involutions, Electron. J. Combin. 9 (2) (2003), R16.

[7] M. Klazar, Bell numbers, their relatives, and algebraic differential equations, J. Combinatorial Theory, Series A, 102 (2003), 63-87.

[8] J. N me ek and M. Klazar, A bijection between nonegative words and sparse -free partitions, Discrete Math., 265(1-3) (2003), 411-416.

[9] R. Simion, F. W. Schmidt, Restricted permutations, Europ. J. Combin. 6 (1985) 383–406.

---

^[1] This is joint work with Yu P. Deng, Rosena R. X. Du, Sherry H. F. Yan and Laura L. M. Yang