首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到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.
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 k 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.
9.
Let us call a lattice path in Z×Z from (0,0) to (n,0) using U=(1,k), D=(1,?1), and H=(a,0) steps and never going below the x-axis, a (k,a)-path (of order n). A super   (k,a)-path is a (k,a)-path which is permitted to go below the x-axis. We relate the total number of humps in all of the (k,a)-paths of order n to the number of super (k,a)-paths, where a hump is defined to be a sequence of steps of the form UHiD, i0. This generalizes recent results concerning the cases when k=1 and a=1 or a=. A similar relation may be given involving peaks (consecutive steps of the form UD).  相似文献   

10.
我们在Dyck格路上构造了一个对合,研究了统计量``峰的数量'', ``返回的数量''和``最后一个峰的高度''的分布问题. 作为应用, 我们给出了若干Stirling统计量在避免132模式和避免321模式的排列集合上的同分布结果.  相似文献   

11.
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.
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 y-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 G is a graph and f:V(G)N is a mapping. For a nonnegative integer m, let f(m) be the extension of f to the graph G
 Km¯ for which f(m)(v)=|V(G)| for each vertex v of Km¯. Let mc(G,f) be the minimum m such that G
 Km¯ is not f(m)-choosable and mp(G,f) be the minimum m such that G
 Km¯ is not f(m)-paintable. We study the parameter mc(Kn,f) and mp(Kn,f) for arbitrary mappings f. For x=(x1,x2,,xn), an x-dominated path ending at (a,b) is a monotonic path P of the a×b grid from (0,0) to (a,b) such that each vertex (i,j) on P satisfies ixj+1. Let ψ(x) be the number of x-dominated paths ending at (xn,n). By this definition, the Catalan number Cn equals ψ((0,1,,n?1)). This paper proves that if G=Kn has vertices v1,v2,,vn and f(v1)f(v2)f(vn), then mc(G,f)=mp(G,f)=ψ(x(f)), where x(f)=(x1,x2,,xn) and xi=f(vi)?i for i=1,2,,n. Therefore, if f(vi)=n, then mc(Kn,f)=mp(Kn,f) equals the Catalan number Cn. We also show that if G=G1G2?Gp is the disjoint union of graphs G1,G2,,Gp and f=f1f2?fp, then mc(G,f)=i=1pmc(Gi,fi) and mp(G,f)=i=1pmp(Gi,fi). This generalizes a result in Carraher et al. (2014), where the case each Gi is a copy of K1 is considered.  相似文献   

14.
15.
A Dyck path is non-decreasing if the y-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.
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.
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.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号