Geodesic
Difference equations and generating functions for some lattice path problems
Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 12 (2019) no. 5, pp. 551-559.

Voir la notice de l'article provenant de la source Math-Net.Ru

An identity for generating functions is proved in this paper. A novel method to compute the number of restricted lattice paths is developed on the basis of this identity. The method employs a difference equation with non-constant coefficients. Dyck paths, Schröder paths, Motzkins path and other paths are computed to illustrate this method.
Keywords: difference equation, generating function, lattice path. 
@article{JSFU_2019_12_5_a2,
     author = {Sreelatha Chandragiri},
     title = {Difference equations and generating functions for some lattice path problems},
     journal = {\v{Z}urnal Sibirskogo federalʹnogo universiteta. Matematika i fizika},
     pages = {551--559},
     publisher = {mathdoc},
     volume = {12},
     number = {5},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JSFU_2019_12_5_a2/}
}
TY  - JOUR
AU  - Sreelatha Chandragiri
TI  - Difference equations and generating functions for some lattice path problems
JO  - Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
PY  - 2019
SP  - 551
EP  - 559
VL  - 12
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JSFU_2019_12_5_a2/
LA  - en
ID  - JSFU_2019_12_5_a2
ER  - 
%0 Journal Article
%A Sreelatha Chandragiri
%T Difference equations and generating functions for some lattice path problems
%J Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika
%D 2019
%P 551-559
%V 12
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JSFU_2019_12_5_a2/
%G en
%F JSFU_2019_12_5_a2
Sreelatha Chandragiri. Difference equations and generating functions for some lattice path problems. Žurnal Sibirskogo federalʹnogo universiteta. Matematika i fizika, Tome 12 (2019) no. 5, pp. 551-559. http://geodesic.mathdoc.fr/item/JSFU_2019_12_5_a2/

[1] A.P. Lyapin, S. Chandragiri, “Generating functions for vector partitions and a basic recurrence relation”, Journal of Difference Equations and Applications, 25 (2019), 1052–1061 | DOI | MR | Zbl

[2] M. Bousquet-Mélou, M. Petkovšek, “Linear recurrences with constant coefficients: the multivariate case”, Discrete Mathematics, 225 (2000), 51–75 | DOI | MR | Zbl

[3] E.K. Leinartas, A.P. Lyapin, “On the rationality of multidimensional recursive series”, J. Sib. Fed. Univ. Math. Phys., 4:2 (2009), 449–455

[4] E.K. Leinartas, “Multiple Laurent series and fundamental solutions of linear difference equations”, Siberian Mathematical Journal, 48:2 (2007), 268–272 | DOI | MR | Zbl

[5] J. Labelle, Y.N. Yeh, “Generalized Dyck paths”, Discrete Math., 82 (1990), 1–6 | DOI | MR | Zbl

[6] D. Merlini, R. Sprugnoli, M.C. Verri, “The area determined by underdiagonal lattice paths”, Trees in Algebra and Programming — CAAP, 1996, 59–71 | DOI | MR

[7] I.M. Gessel, “A factorization for formal Laurent series and lattice path enumeration”, J. Combin. Theory. Ser. A, 28 (1980), 321–337 | DOI | MR

[8] A. Dvoretzky, Th. Motzkin, “A problem of arrangements”, Duke Math. J., 14 (1947), 305–313 | DOI | MR | Zbl

[9] P. Duchon, “On the enumeration and generation of generalized Dyck words”, Discrete Math., 225 (2000), 121–135 | DOI | MR | Zbl

[10] R. Stanley, Enumerative Combinatorics, v. 1, 1990 | MR

[11] A.A. Kytmanov, A.P. Lyapin, T.M. Sadykov, “Evaluating the rational generating function for the solution of the Cauchy problem for a two-dimensional difference equation with constant coefficients”, Programming and computer software, 43:2 (2017), 105–111 | DOI | MR

[12] D. Merlini, D.G. Rogers, R. Sprugnoli, M.C. Verri, “Underdiagonal lattice paths with unrestricted steps”, Discrete Applied Mathematics, 91 (1999), 197–213 | DOI | MR | Zbl