On some problems about ternary paths: a linear algebra approach

MaRDI QIDQ1983200zbMATH OpenFDO

Authors Helmut Prodinger

Publication date 10 September 2021

Published in Rocky Mountain Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.02320

zbMATH Keywords

generalized binomial seriesgenerating functionsternary paths

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Trees (05C05)

Abstract: Ternary paths consist of an up-step of one unit, a down-step of two units, never go below the $x$-axis, and return to the $x$-axis. This paper addresses the enumeration of partial ternary paths, ending at a given level $i$, reading the path either from left to right or from right to left. Since the paths are not symmetric w.r.t. left vs. right, as classical Dyck paths, this leads to different results. The right to left enumeration is quite challenging, but leads at the end to very satisfying results. The methods are elementary (solving systems of linear equations). In this way, several conjectures left open in Naiomi Cameron's Ph.D. thesis could be successfully settled.

Recommendations

• Dyck path enumeration
• Some statistics on Dyck paths
• Returns and hills on generalized Dyck paths
• Lattice and Schröder paths with periodic boundaries
• scientific article; zbMATH DE number 4137768

Cites work

• Analytic methods
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 1391729 (Why is no real title available?)
• scientific article; zbMATH DE number 3390782 (Why is no real title available?)
• Lattice path enumeration
• On the average depth of a prefix of the Dycklanguage \(D_ 1\).
• On Two Subclasses of Motzkin Paths and Their Relation to Ternary Trees
• Walks confined in a quadrant are not always D-finite

Cited in

(4)

• An elementary approach to solve recursions relative to the enumeration of S-Motzkin paths
• Counting ternary trees according to the number of middle edges and factorizing into (3/2)-ary trees
• On \({k}\)-Dyck paths with a negative boundary
• Generating functions for a lattice path model introduced by Deutsch

This page was built for publication: On some problems about ternary paths: a linear algebra approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1983200)