Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBijections for Dyck paths with all peak heights of the same parity
144
0
0.0
(
0
)
Authors
David Callan
Ask ChatGPT about the research
No Arabic abstract
We show bijectively that Dyck paths with all peaks at odd height are counted by the Motzkin numbers and Dyck paths with all peaks at even height are counted by the Riordan numbers.
rate research
Read More
For any integer $mge 2$ and a set $Vsubset {1,dots,m}$, let $(m,V)$ denote the union of congruence classes of the elements in $V$ modulo $m$. We study the Hankel determinants for the number of Dyck paths with peaks avoiding the heights in the set $(m,V)$. For any set $V$ of even elements of an even modulo $m$, we give an explicit description of the sequence of Hankel determinants in terms of subsequences of arithmetic progression of integers. There are numerous instances for varied $(m,V)$ with periodic sequences of Hankel determinants. We present a sufficient condition for the set $(m,V)$ such that the sequence of Hankel determinants is periodic, including even and odd modulus $m$.
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.
Garsia and Xin gave a linear algorithm for inverting the sweep map for Fuss rational Dyck paths in $D_{m,n}$ where $m=knpm 1$. They introduced an intermediate family $mathcal{T}_n^k$ of certain standard Young tableau. Then inverting the sweep map is done by a simple walking algorithm on a $Tin mathcal{T}_n^k$. We find their idea naturally extends for $mathbf{k}^pm$-Dyck paths, and also for $mathbf{k}$-Dyck paths (reducing to $k$-Dyck paths for the equal parameter case). The intermediate object becomes a similar type of tableau in $mathcal{T}_mathbf{k}$ of different column lengths. This approach is independent of the Thomas-Williams algorithm for inverting the general modular sweep map.
In this paper we study a subfamily of a classic lattice path, the emph{Dyck paths}, called emph{restricted $d$-Dyck} paths, in short $d$-Dyck. A valley of a Dyck path $P$ is a local minimum of $P$; if the difference between the heights of two consecutive valleys (from left to right) is at least $d$, we say that $P$ is a restricted $d$-Dyck path. The emph{area} of a Dyck path is the sum of the absolute values of $y$-components of all points in the path. We find the number of peaks and the area of all paths of a given length in the set of $d$-Dyck paths. We give a bivariate generating function to count the number of the $d$-Dyck paths with respect to the the semi-length and number of peaks. After that, we analyze in detail the case $d=-1$. Among other things, we give both, the generating function and a recursive relation for the total area.
A {em k-generalized Dyck 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 $(k, 0)$ for a given integer $kgeq 0$, up-steps $(1,1)$, and down-steps $(1,-1)$, which never passes below the x-axis. The present paper studies three kinds of statistics on $k$-generalized Dyck paths: number of $u$-segments, number of internal $u$-segments and number of $(u,h)$-segments. The Lagrange inversion formula is used to represent the generating function for the number of $k$-generalized Dyck paths according to the statistics as a sum of the partial Bell polynomials or the potential polynomials. Many important special cases are considered leading to several surprising observations. Moreover, enumeration results related to $u$-segments and $(u,h)$-segments are also established, which produce many new combinatorial identities, and specially, two new expressions for Catalan numbers.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
