共查询到20条相似文献,搜索用时 15 毫秒
1.
The statistics concerning the number of appearances of a string τ in Dyck paths as well as its appearances in odd and even level have been studied extensively by several authors using mostly algebraic methods. In this work a different, bijective approach is followed giving some known as well as some new results. 相似文献
2.
Robert Cori 《Journal of Combinatorial Theory, Series A》2009,116(8):1326-1343
Hypermaps were introduced as an algebraic tool for the representation of embeddings of graphs on an orientable surface. Recently a bijection was given between hypermaps and indecomposable permutations; this sheds new light on the subject by connecting a hypermap to a simpler object. In this paper, a bijection between indecomposable permutations and labeled Dyck paths is proposed, from which a few enumerative results concerning hypermaps and maps follow. We obtain for instance an inductive formula for the number of hypermaps with n darts, p vertices and q hyperedges; the latter is also the number of indecomposable permutations of Sn with p cycles and q left-to-right maxima. The distribution of these parameters among all permutations is also considered. 相似文献
3.
《Discrete Mathematics》2023,346(3):113247
A 3-dimensional Catalan word is a word on three letters so that the subword on any two letters is a Dyck path. For a given Dyck path D, a recently defined statistic counts the number of Catalan words with the property that any subword on two letters is exactly D. In this paper, we enumerate Dyck paths with this statistic equal to certain values, including all primes. The formulas obtained are in terms of Motzkin numbers and Motzkin ballot numbers. 相似文献
4.
《Discrete Mathematics》2020,343(9):111995
We provide generating functions for the popularity and the distribution of patterns of length at most three over the set of Dyck paths having a first return decomposition constrained by height. 相似文献
5.
We study the enumeration of Dyck paths having a first return decomposition with special properties based on a height constraint. We exhibit new restricted sets of Dyck paths counted by the Motzkin numbers, and we give a constructive bijection between these objects and Motzkin paths. As a byproduct, we provide a generating function for the number of Motzkin paths of height with a flat (resp. with no flats) at the maximal height. 相似文献
6.
Using the bijection between partitions and vacillating tableaux, we establish a correspondence between pairs of noncrossing free Dyck paths of length 2n and noncrossing partitions of [2n+1] with n+1 blocks. In terms of the number of up steps at odd positions, we find a characterization of Dyck paths constructed from pairs of noncrossing free Dyck paths by using the Labelle merging algorithm. 相似文献
7.
In this paper we introduce a new bijection from the set of Dyck paths to itself. This
bijection has the property that it maps statistics that appeared recently in the study of patternavoiding
permutations into classical statistics on Dyck paths, whose distribution is easy to obtain.
We also present a generalization of the bijection, as well as several applications of it to
enumeration problems of statistics in restricted permutations.AMS Subject Classification: 05A15, 05A05. 相似文献
8.
《Discrete Mathematics》2020,343(12):112118
9.
Let us call a lattice path in from to using , , and steps and never going below the -axis, a -path (of order ). A super -path is a -path which is permitted to go below the -axis. We relate the total number of humps in all of the -paths of order to the number of super -paths, where a hump is defined to be a sequence of steps of the form , . This generalizes recent results concerning the cases when and or . A similar relation may be given involving peaks (consecutive steps of the form ). 相似文献
10.
11.
Sergi Elizalde 《Journal of Combinatorial Theory, Series A》2007,114(8):1481-1503
A k-triangulation of a convex polygon is a maximal set of diagonals so that no k+1 of them mutually cross in their interiors. We present a bijection between 2-triangulations of a convex n-gon and pairs of non-crossing Dyck paths of length 2(n−4). This solves the problem of finding a bijective proof of a result of Jonsson for the case k=2. We obtain the bijection by constructing isomorphic generating trees for the sets of 2-triangulations and pairs of non-crossing Dyck paths. 相似文献
12.
Éva Czabarka Rigoberto Flórez Leandro Junes José L. Ramírez 《Discrete Mathematics》2018,341(10):2789-2807
A valley in a Dyck path is a local minimum, and a peak is a local maximum. A Dyck path is non-decreasing if the -coordinates of the valleys of the path valley form anon-decreasing sequence. In this paper we provide some statistics about peaks and valleys in non-decreasing Dyck paths, such as their total number, the number of low and high valleys, low and high peaks, etc. Our methods include bijective proofs, recursive relations, and the symbolic method for generating functions. 相似文献
13.
The Catalan numbers occur in various counting problems in combinatorics. This paper reveals a connection between the Catalan numbers and list colouring of graphs. Assume is a graph and is a mapping. For a nonnegative integer , let be the extension of to the graph for which for each vertex of . Let be the minimum such that is not -choosable and be the minimum such that is not -paintable. We study the parameter and for arbitrary mappings . For , an -dominated path ending at is a monotonic path of the grid from to such that each vertex on satisfies . Let be the number of -dominated paths ending at . By this definition, the Catalan number equals . This paper proves that if has vertices and , then , where and for . Therefore, if , then equals the Catalan number . We also show that if is the disjoint union of graphs and , then and . This generalizes a result in Carraher et al. (2014), where the case each is a copy of is considered. 相似文献
14.
15.
A Dyck path is non-decreasing if the -coordinates of its valleys form a non-decreasing sequence. In this paper we give enumerative results and some statistics of several aspects of non-decreasing Dyck paths. We give the number of pyramids at a fixed level that the paths of a given length have, count the number of primitive paths, count how many of the non-primitive paths can be expressed as a product of primitive paths, and count the number of paths of a given height and a given length. We present and prove our results using combinatorial arguments, generating functions (using the symbolic method) and parameterize the results studied here using the Riordan arrays. We use known bijections to connect direct column-convex polyominoes, Elena trees, and non-decreasing Dyck paths. 相似文献
16.
Termeh Kousha 《Statistics & probability letters》2012,82(2):340-347
In this work, we obtain a large and moderate deviation principle for the law of the maximum of a random Dyck path. Our result extends the results of Chung (1976), Kennedy (1976) and Khorunzhiy and Marckert (2009). 相似文献
17.
18.
We analyze the service times of customers in a stable M/M/1 queue in equilibrium depending on their position in a busy period. We give the law of the service of a customer at the beginning, at the end, or in the middle of the busy period. It enables as a by-product to prove that the process of instants of beginning of services is not Poisson. We then proceed to a more precise analysis. We consider a family of polynomial generating series associated with Dyck paths of length 2n and we show that they provide the correlation function of the successive services in a busy period with n+1 customers. 相似文献
19.
Toufik Mansour 《Journal of Difference Equations and Applications》2013,19(6):555-563
In this paper, we solve several recurrence relations with two indices by using combinatorial methods. Moreover, we present several recurrence relations with two indices related to Dyck paths and Schröder paths. 相似文献
20.
In [Ferrari, L. and Pinzani, R.: Lattices of lattice paths. J. Stat. Plan. Inference 135 (2005), 77–92] a natural order on Dyck paths of any fixed length inducing a distributive lattice structure is defined. We transfer this order to noncrossing partitions along a well-known bijection [Simion, R.: Noncrossing partitions. Discrete Math. 217 (2000), 367–409], thus showing that noncrossing partitions can be endowed with a distributive lattice structure having some combinatorial relevance. Finally we prove that our lattices are isomorphic to the posets of 312-avoiding permutations with the order induced by the strong Bruhat order of the symmetric group. 相似文献