Séminaire Lotharingien de Combinatoire, 87B.1 (2023), 49 pp.

Helmut Prodinger

A walk in my lattice path garden

Abstract. Various lattice path models are reviewed. The enumeration is done using generating functions. A few bijective considerations are woven in as well. The kernel method is often used. Computer algebra was an essential tool. Some results are new, some have appeared before, but all are interesting. The lattice path models considered are Hoppy walks and several models involving skew Dyck paths, Schröder paths, hex-trees, decorated ordered trees, multi-edge trees, etc., related to the sequence A002212 in the On-line Encyclopedia of Integer Sequences (created by N. Sloane). Weighted unary-binary trees also occur and we there improve on our old paper on Horton-Strahler numbers [P. Flajolet and H. Prodinger, 1986], by using a different substitution. Some material on Motzkin numbers and paths is also discussed. Some new results on `Deutsch paths' in a strip are included as well. During the Covid period, I spent much time with this beautiful concept that I dare to call Deutsch paths, since Emeric Deutsch stands at the beginning with a problem that he posted in the American Mathematical Monthly some 20 years ago. Peaks and valleys, studied by Rainer Kemp 40 years ago under the names max-turns and min-turns, are revisited with a more modern approach, streamlining the analysis, relying on the `subcritical case' (named so by Philippe Flajolet), the adding a new slice technique and once again the kernel method.


Received: December 13, 2021. Revised: August 3, 2023. Published: August 31, 2023.

The following versions are available:

If you need to cite this article, here is a bibtex:

@article{Prodinger23,
author = {Prodinger, Helmut},
title = {A walk in my lattice path garden},
fjournal = {S{\'e}minaire Lotharingien de Combinatoire},
journal = {S{\'e}min. Lothar. Combin.},
issn={1286-4889},
volume = {87B},
number= {1},
pages = {1--49},
year = {2023},
language = {English},
doi={10.48550/arXiv.2111.14797},
}