Lattice and Schröder paths with periodic boundaries

DOI10.1016/J.JSPI.2008.09.002MaRDI QIDQ1011541zbMATH OpenOpenAlexFDO

Authors Joseph P. S. Kung, Anna de Mier, Xinyu Sun, Catherine Yan

Publication date 8 April 2009

Published in Journal of Statistical Planning and Inference (Search for Journal in Brave)

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

zbMATH Keywords

algebraic generating functionAppell relationlattice pathparking functionSchröder pathtennis ball problem

Mathematics Subject Classification ID

Factorials, binomial coefficients, combinatorial functions (05A10) Exact enumeration problems, generating functions (05A15) Umbral calculus (05A40)

Abstract: 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}ph{i}_n(z),$ where $ph{i}_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.

Recommendations

• Lattice paths not touching a given boundary
• scientific article; zbMATH DE number 727680
• The number of lattice paths below a cyclically shifting boundary
• scientific article; zbMATH DE number 4137768
• Generalized Dyck paths

Cites work

• A probabilistic method for lattice path enumeration
• A solution to the tennis ball problem
• Advanced determinant calculus: a complement
• An Occupancy Discipline and Applications
• Gončarov polynomials and parking functions
• scientific article; zbMATH DE number 3712896 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1156613 (Why is no real title available?)
• scientific article; zbMATH DE number 872231 (Why is no real title available?)
• Lattice paths not touching a given boundary
• Rectangular Scott-type permanents
• Sheffer polynomials for computing exact Kolmogorov-Smirnov and Renyi type distributions
• Simple Random Walk and Rank Order Statistics
• Some \(q\)-analogues of the Schröder numbers arising from combinatorial statistics on lattice paths
• Some Generalizations of Vandermonde's Convolution
• The tennis ball problem
• Two-boundary lattice paths and parking functions

Cited in

(6)

• Lattice paths between diagonal boundaries
• On some problems about ternary paths: a linear algebra approach
• Quarter-plane lattice paths with interacting boundaries: the Kreweras and reverse Kreweras models
• Vector parking functions with periodic boundaries and rational parking functions
• Parking distributions on trees
• scientific article; zbMATH DE number 7058738 (Why is no real title available?)

This page was built for publication: Lattice and Schröder paths with periodic boundaries

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