Abstract
The main purpose of this paper is to derive generating functions for the numbers of lattice paths running from (0, 0) to any (n, k) in \({\mathbb{Z} \times \mathbb{N}}\) consisting of four types of steps: horizontal H = (1, 0), vertical V = (0, 1), diagonal D = (1, 1), and sloping L = (–1, 1). These paths generalize the well-known Delannoy paths which consist of steps H, V, and D. Several restrictions are considered. However, we mainly treat with those which will be needed to get the generating function for the numbers R(n, k) of these lattice paths whose points lie in the integer rectangle \({\{(x, y) \in \mathbb{N}^2 : 0 \leq x \leq n, 0 \leq y \leq k\}}\). Recurrence relation, generating functions and explicit formulas are given. We show that most of considered numbers define Riordan arrays.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Banderier C., Schwer S.: Why Delannoy numbers. J. Stat. Plan. Inference 135(1), 40–54 (2005)
Chen W.Y.C., Li N.Y., Shapiro L.W., Yan S.H.F.: Matrix identities on weighted partial Motzkin paths. Eur. J. Comb. 28, 1196–1207 (2007)
Comtet, L.: Advanced Combinatorics: The Art of Finite and Infinite Expansions. D. Reidel Publishing Company, Boston (1974)
Drake B.: Limits of areas under lattice paths. Discret. Math. 309(12), 3936–3953 (2009)
Dziemiańczuk, M.: A bijection between weighted free (3,3)-Motzking paths and generalized Delannoy paths with four types of steps (2012). Preprint, submitted for publication
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)
Krattenthaler C.: Advanced determinant calculus: a complement. Linear Algebra Appl. 411, 68–166 (2005)
Kruchinin, V.: Compositae and their properties Preprint arXiv:1103.2582 (14 Mar 2011)
Lehner F.: Cumulants, lattice paths, and orthogonal polynomials. Discret. Math. 270(1-3), 177–191 (2003)
Merlini D., Sprugnoli R., Verri M.C.: Lagrange inversion: when and how. Acta Appl. Math. 94, 233–249 (2006)
Merlini D., Sprugnoli R., Verri M.C.: The method of coefficients. Am. Math. Mon. 114(1), 24–57 (2007)
Shapiro L.W., Getu S., Woan W.J., Woodson L.: The Riordan group. Discret. Appl. Math. 34, 229–239 (1991)
Sloane, N.J.A.: The on-line encyclopedia of integer sequences. Published electronically at http://oeis.org/
Sprugnoli R.: Riordan arrays and combinatorial sums. Discret. Math. 32, 267–290 (1994)
Sprugnoli, R.: A bibliography on Riordan arrays. Published electronically at http://www.dsi.unifi.it/~resp/BibRioMio.pdf. (2008)
Stanley, R.P.: Enumerative Combinatorics, vol. II. Cambridge University Press, Cambridge (1999)
Wall, H.S.: Analytic Theory of Continued Fractions. AMS Chelsea Publishing, New York (2000)
Wilf, H.S.: Generatingfunctionology. Academic Press, Boston (1994)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
About this article
Cite this article
Dziemiańczuk, M. Counting Lattice Paths With Four Types of Steps. Graphs and Combinatorics 30, 1427–1452 (2014). https://doi.org/10.1007/s00373-013-1357-1
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-013-1357-1