Lattice paths of slope 2/5
Abstract
We analyze some enumerative and asymptotic properties of Dyck paths under a line of slope 2/5. This answers to Knuth's problem #4 from his "Flajolet lecture" during the conference "Analysis of Algorithms" (AofA'2014) in Paris in June 2014. Our approach relies on the work of Banderier and Flajolet for asymptotics and enumeration of directed lattice paths.
A key ingredient in the proof is the generalization of an old trick of Knuth himself (for enumerating permutations sortable by a stack), promoted by Flajolet and others as the "kernel method". All the corresponding generating functions are algebraic, and they offer some new combinatorial identities, which can be also tackled in the A=B spirit of Wilf--Zeilberger--Petkovšek.
We show how to obtain similar results for other slopes than 2/5, an interesting case being e.g. Dyck paths below the slope 2/3, which corresponds to the so called Duchon's club model.
References
[1]
Cyril Banderier, Mireille Bousquet-Mélou, Alain Denise, Philippe Flajolet, Danièle Gardy, and Dominique Gouyou-Beauchamps. Generating functions for generating trees. Discrete Math., 246(1-3):29--55, 2002. Formal power series and algebraic combinatorics (Barcelona, 1999).
[2]
Cyril Banderier and Michael Drmota. Coefficients of algebraic functions: formulae and asymptotics. Combinatorics, Probability, and Computing, To appear, 2014.
[3]
Cyril Banderier and Philippe Flajolet. Basic analytic combinatorics of directed lattice paths. Theoret. Comput. Sci., 281(1-2):37--80, 2002. Selected papers in honour of Maurice Nivat.
[4]
Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, and Michèle Soria. Random maps, coalescing saddles, singularity analysis, and Airy phenomena. Random Structures & Algorithms, 19(3-4):194--246, 2001.
[5]
Cyril Banderier and Bernhard Gittenberger. Analytic combinatorics of lattice paths: enumeration and asymptotics for the area. Discrete Math. Theor. Comput. Sci. Proc., AG:345--355, 2006.
[6]
M. T. L. Bizley. Derivation of a new formula for the number of minimal lattice paths from (0, 0) to (km, kn) having just t contacts with the line my = nx and having no points above this line; and a proof of Grossman's formula {...}. J. Inst. Actuar., 80:55--62, 1954.
[7]
Mireille Bousquet-Mélou, Éric Fusy, and Louis-François Préville-Ratelle. The number of intervals in the m-Tamari lattices. Electron. J. Combin., 18(2):Paper 31, 26, 2011.
[8]
Philippe Duchon. On the enumeration and generation of generalized Dyck words. Discrete Math., 225(1-3):121--135, 2000. Formal power series and algebraic combinatorics (Toronto, 1998).
[9]
Guy Fayolle, Roudolf Iasnogorodski, and Vadim Malyshev. Random walks in the quarter-plane, volume 40 of Applications of Mathematics (New York). Springer-Verlag, Berlin, 1999.
[10]
Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009.
[11]
Donald E. Knuth. The art of computer programming. Vol. 1: Fundamental algorithms. Second printing. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1969.
[12]
Toufik Mansour and Mark Shattuck. Pattern avoiding partitions, sequence A054391 and the kernel method. Appl. Appl. Math., 6(12):397--411, 2011.
[13]
Tomoki Nakamigawa and Norihide Tokushige. Counting lattice paths via a new cycle lemma. SIAM J. Discrete Math., 26(2):745--754, 2012.
Recommendations
Lattice paths and (n − 2)-stack sortable permutations
AbstractWe establish a bijection between the ( n − 2 )-stack sortable permutations and the labeled lattice paths. Using this bijection, we directly give combinatorial proof for the log-concavity of the numbers of ( n − 2 )-stack sortable ...
Symmetric Schröder paths and restricted involutions
Let A"k be the set of permutations in the symmetric group S"k with prefix 12. This paper concerns the enumeration of involutions which avoid the set of patterns A"k. We present a bijection between symmetric Schroder paths of length 2n and involutions of ...
Enumerating a class of lattice paths
Let D"0(n) denote the set of lattice paths in the xy-plane that begin at (0,0), terminate at (n,n), never rise above the line y=x and have step set S={(k,0):k@?N^+}@?{(0,k):k@?N^+}. Let E"0(n) denote the set of lattice paths with step set S that begin ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 2015
137 pages
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 04 January 2015
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 40Total Downloads
- Downloads (Last 12 months)15
- Downloads (Last 6 weeks)5
Reflects downloads up to 22 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in