Parity reversing involutions on plane trees and 2-Motzkin paths

DOI10.1016/J.EJC.2004.07.013zbMATH Open1082.05005arXivmath/0503300OpenAlexW2022051109MaRDI QIDQ819014FDOQ819014

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)

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.

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

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

zbMATH Keywords

Catalan numberinvolutionDyck pathplane tree

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• An identity involving Narayana numbers
• Operated semigroups, Motzkin paths and rooted trees
• On the parity of the Wiener index
• Sign-balance identities of Adin-Roichman type on 321-avoiding alternating permutations
• The butterfly decomposition of plane trees
• 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)