Parity reversing involutions on plane trees and 2-Motzkin paths

DOI10.1016/J.EJC.2004.07.013MaRDI QIDQ819014zbMATH OpenOpenAlexFDO

Authors William Y. C. Chen, Louis W. Shapiro, Laura L. M. Yang

Publication date 22 March 2006

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0503300

zbMATH Keywords

Catalan numberDyck pathinvolutionplane tree

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Trees (05C05) Enumeration in graph theory (05C30)

Abstract: The problem of counting plane trees with $n$ edges and an even or an odd number of leaves was studied by Eu, Liu and Yeh, in connection with an identity on coloring nets due to Stanley. This identity was also obtained by Bonin, Shapiro and Simion in their study of Schr"oder paths, and it was recently derived by Coker using the Lagrange inversion formula. An equivalent problem for partitions was independently studied by Klazar. We present three parity reversing involutions, one for unlabelled plane trees, the other for labelled plane trees and one for 2-Motzkin paths which are in one-to-one correspondence with Dyck paths.

Recommendations

• Odd or even on plane trees
• Trees associated with the Motzkin numbers
• Old and young leaves on plane trees
• The butterfly decomposition of plane trees
• scientific article; zbMATH DE number 4128814

Cites work

• A bijection between ordered trees and 2-Motzkin paths and its many consequences
• A bijection on ordered trees and its consequences
• A correspondence between ordered trees and noncrossing partitions
• A general bijective algorithm for trees.
• Counting Even and Odd Partitions
• Enumerating a class of lattice paths
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• Odd or even on plane trees
• Old and young leaves on plane trees
• Ordered trees and non-crossing partitions
• Some \(q\)-analogues of the Schröder numbers arising from combinatorial statistics on lattice paths
• The statistic ``number of udu's in Dyck paths

Cited in

(7)

• Operated semigroups, Motzkin paths and rooted trees
• On the parity of the Wiener index
• An identity involving Narayana numbers
• The butterfly decomposition of plane trees
• Sign-balance identities of Adin-Roichman type on 321-avoiding alternating permutations
• New refinements of Narayana polynomials and Motzkin polynomials
• Old and young leaves on plane trees

This page was built for publication: Parity reversing involutions on plane trees and 2-Motzkin paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q819014)