Lattice and Schrder paths with periodic boundaries Academic Article uri icon

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 strictly 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 zn is replaced by a power series of the form zn 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. We give several concrete examples, including an alternative way to solve the tennis ball problem. 2008 Elsevier B.V. All rights reserved.

published proceedings

  • Journal of Statistical Planning and Inference

author list (cited authors)

  • Kung, J., de Mier, A., Sun, X., & Yan, C.

citation count

  • 3

complete list of authors

  • Kung, Joseph PS||de Mier, Anna||Sun, Xinyu||Yan, Catherine

publication date

  • January 2009