Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn two subclasses of Motzkin paths and their relation to ternary trees
66
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Two subclasses of Motzkin paths, S-Motzkin and T-Motzkin paths, are introduced. We provide bijections between S-Motzkin paths and ternary trees, S-Motzkin paths and non-crossing trees, and T-Motzkin paths and ordered pairs of ternary trees. Symbolic equations for both paths, and thus generating functions for the paths, are provided. Using these, various parameters involving the two paths are analyzed.
rate research
Read More
A {em Motzkin path} of length $n$ is a lattice path from $(0,0)$ to $(n,0)$ in the plane integer lattice $mathbb{Z}timesmathbb{Z}$ consisting of horizontal-steps $(1, 0)$, up-steps $(1,1)$, and down-steps $(1,-1)$, which never passes below the x-axis. A {em $u$-segment {rm (resp.} $h$-segment {rm)}} of a Motzkin path is a maximum sequence of consecutive up-steps ({rm resp.} horizontal-steps). The present paper studies two kinds of statistics on Motzkin paths: number of $u$-segments and number of $h$-segments. The Lagrange inversion formula is utilized to represent the weighted generating function for the number of Motzkin paths according to the statistics as a sum of the partial Bell polynomials or the potential polynomials. As an application, a general framework for studying compositions are also provided.
In this paper, we propose a notion of colored Motzkin paths and establish a bijection between the $n$-cell standard Young tableaux (SYT) of bounded height and the colored Motzkin paths of length $n$. This result not only gives a lattice path interpretation of the standard Young tableaux but also reveals an unexpected intrinsic relation between the set of SYTs with at most $2d+1$ rows and the set of SYTs with at most 2d rows.
A partial Motzkin path is a path from $(0, 0)$ to $(n, k)$ in the $XOY$-plane 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=(1, 0)$. A weighted partial Motzkin path is a partial Motzkin path with the weight assignment that all up steps and down steps are weighted by 1, the horizontal steps are endowed with a weight $x$ if they are lying on $X$-axis, and endowed with a weight $y$ if they are not lying on $X$-axis. Denote by $M_{n,k}(x, y)$ to be the weight function of all weighted partial Motzkin paths from $(0, 0)$ to $(n, k)$, and $mathcal{M}=(M_{n,k}(x,y))_{ngeq kgeq 0}$ to be the infinite lower triangular matrices. In this paper, we consider the sums of minors of second order of the matrix $mathcal{M}$, and obtain a lot of interesting determinant identities related to $mathcal{M}$, which are proved by bijections using weighted partial Motzkin paths. When the weight parameters $(x, y)$ are specialized, several new identities are obtained related to some classical sequences involving Catalan numbers. Besides, in the alternating cases we also give some new explicit formulas for Catalan numbers.
In this short note, we first present a simple bijection between binary trees and colored ternary trees and then derive a new identity related to generalized Catalan numbers.
We introduce a new concept of permutation avoidance pattern called hatted pattern, which is a natural generalization of the barred pattern. We show the growth rate of the class of permutations avoiding a hatted pattern in comparison to barred pattern. We prove that Dyck paths with no peak at height $p$, Dyck paths with no $ud... du$ and Motzkin paths are counted by hatted pattern avoiding permutations in $s_n(132)$ by showing explicit bijections. As a result, a new direct bijection between Motzkin paths and permutations in $s_n(132)$ without two consecutive adjacent numbers is given. These permutations are also represented on the Motzkin generating tree based on the Enumerative Combinatorial Object (ECO) method.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
