×

An elementary approach to solve recursions relative to the enumeration of S-Motzkin paths. (English) Zbl 1475.05011

Motzkin paths are certain lattice paths with the property that the length \(n\) of such paths is the \(n\)th Motzkin number. This is a variant of enumeration of Dyck paths that gives Catalan numbers. In the article under review, the author considers S-Motzkin paths, a variant of Motzkin paths counted by the Fuß-Catalan number \(\frac{1}{2n+1} \binom{3n}{n}\). He also considers prefixes of such paths, which can be used to write down some linear recursions for the associated counting problem.
In a previous work [PU.M.A., Pure Math. Appl. 29, No. 1, 28–38 (2020; Zbl 1474.05012)], the author computed the numbers of prefixes of S-Motzkin paths via the analysis of a generating function. The goal of the present article is to provide an elementary method to solve these linear recursions, via some computations of determinants. The determinants satisfy a linear recursion such that the characteristic equation has degree 3, but they can be solved explicitly via an appropriate parametrization.

MSC:

05A15 Exact enumeration problems, generating functions
05A05 Permutations, words, matrices

Citations:

Zbl 1474.05012

Software:

gfun; OEIS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] The online encyclopedia of integer sequences. http://oeis.org. · Zbl 1494.68308
[2] Gould, H., The Girard-Waring power sum formulas for symmetric functions and Fibonacci sequences, Fibonacci Q., 37, 2, 135-140 (1999) · Zbl 0944.05007
[3] Gu, N.S.S. and Prodinger, H., A bijection between two subfamilies of Motzkin paths. submitted, 2020
[4] Mularczyk, H., Lattice paths and pattern-avoiding uniquely sorted permutations, preprint. Available at arXiv:1908.04025
[5] Prodinger, H., Enumeration of S-Motzkin paths from left to right and from right to left – a kernel method approach, Pure Math. Appl., 29, 1, 29-38 (2020) · Zbl 1474.05012
[6] Prodinger, H., On some questions about ternary paths – a linear algebra approach, Rocky Mountains J. Math. (2021) · Zbl 1472.05008
[7] Prodinger, H. and Selkirk, S.J., A bijection between ternary trees and a subclass of Motzkin paths, preprint. Available at https://arxiv.org/abs/1808.01907. · Zbl 07293169
[8] Salvy, B.; Zimmermann, P., Gfun: A maple package for the manipulation of generating and holonomic functions in one variable, ACM Trans. Math. Softw., 20, 2, 163-177 (1994) · Zbl 0888.65010
[9] Prodinger, H., Selkirk, S.J., and Wagner, S., On two subclasses of Motzkin paths and their relation to ternary trees. in Algorithmic Combinatorics - Enumerative Combinatorics, Special Functions and Computer Algebra, V. Pillwein and C. Schneider, eds., Springer, 2020, pp. 297-316. · Zbl 07293169
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.