MIN-turns and MAX-turns in k-Dyck paths: A pure generating function approach

Helmut Prodinger
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 30, 2024, Number 2, Pages 213–222
DOI: 10.7546/nntdm.2024.30.2.213-222
Full paper (PDF, 188 Kb)

Details

Authors and affiliations

Helmut Prodinger
¹ Department of Mathematics, University of Stellenbosch
7602, Stellenbosch, South Africa
² NITheCS (National Institute for Theoretical and Computational Sciences),
South Africa

Abstract

-Dyck paths differ from ordinary Dyck paths by using an up-step of length . We analyze at which level the path is after the -th up-step and before the -st up-step. In honour of Rainer Kemp who studied a related concept 40 years ago, the terms max-terms and min-terms are used. Results are obtained by an appropriate use of trivariate generating functions; practically no combinatorial arguments are used.

Keywords

• Dyck paths
• Generating functions
• Kernel method
• Lagrange inversion

2020 Mathematics Subject Classification

• 05A15

References

1. Asinowksi, A., Hackl, B., & Selkirk, S. (2022). Down-step statistics in generalized Dyck paths. Discrete Mathematics & Theoretical Computer Science, 24(1), Article 17.
2. Deng, E. Y. P., & Mansour, T. (2008). Three Hoppy path problems and ternary paths. Discrete Applied Mathematics, 156(5), 770–779.
3. Flajolet, P., & Prodinger, H. (1987). Level number sequences for trees. Discrete Mathematics, 65(2), 149–156.
4. Flajolet, P., & Sedgewick, R. (2009). Analytic Combinatorics. Cambridge University Press, Cambridge.
5. Kemp, R. (1982). On the average oscillation of a stack. Combinatorica, 2(2), 157–176.
6. Prodinger, H. (2003 / 2004). The kernel method: A collection of examples. Seminaire Lotharingien de Combinatoire, 50, Article B50f.
7. Prodinger, H. (2023). A walk through my lattice path garden. Seminaire Lotharingien de Combinatoire, 87b, Article #1.
8. Prodinger, H. (2024). On k-Dyck paths with a negative boundary. Journal of Combinatorial Methods and Combinatorial Computing, 119, 3–12.
9. Selkirk, S. J. (2019). On a generalisation of k-Dyck paths. Master’s thesis, Stellenbosch University.
10. Sloane, N. J. A., & The OEIS Foundation Inc. (2023). The On-Line Encyclopedia of Integer Sequences. Available online at: https://oeis.org/

Manuscript history

• Received: 1 September 2023
• Accepted: 15 April 2024
• Online First: 4 May 2024

Copyright information

Ⓒ 2024 by the Author.
This is an Open Access paper distributed under the terms and conditions of the Creative Commons Attribution 4.0 International License (CC BY 4.0).