Lattice and Schroder paths with periodic boundaries
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
We consider paths in the plane with $(1,0),$ $(0,1),$ and $(a,b)$-steps that start at the origin, end at height $n,$ and stay to the left of a given non-decreasing right boundary. We show that if the boundary is periodic and has slope at most $b/a,$ then the ordinary generating function for the number of such paths ending at height $n$ is algebraic. Our argument is in two parts. We use a simple combinatorial decomposition to obtain an Appell relation or ``umbral'' generating function, in which the power $z^n$ is replaced by a power series of the form $z^n ϕ_n(z),$ where $ϕ_n(0) = 1.$ Then we convert (in an explicit way) the umbral generating function to an ordinary generating function by solving a system of linear equations and a polynomial equation. This conversion implies that the ordinary generating function is algebraic.
22 pages, 1 figure; Revised version, references added and corrected typos
22 pages, 1 figure; Revised version, references added and corrected typos