рус eng
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2023. Vol 44

Counting Lattice Paths by Using Difference Equations with Non-constant Coefficients

Author(s)
Sreelatha Chandragiri1

1Sobolev Institute of Mathematics SB RAS, Novosibirsk, Russian Federation

Abstract
The lattice paths can be counted by the virtue of their step vectors that are aligned to the positive octant. A path can go from one point to an infinite others if there is no restriction applied such that each point only has finitely many predecessors. The linear difference equations with non-constant coefficients will be utilised to incorporate this restriction to study lattice paths that lie on or over a line having a rational slope. The generating functions are obtained and is based on developing a specific method to compute the number of restricted lattice paths.
About the Authors
Sreelatha Chandragiri, Research Scientist, Postdoctoral researcher, Sobolev Institute of Mathematics SB RAS, Novosibirsk, 630090, Russian Federation, srilathasami@math.nsc.ru
For citation
Chandragiri S. Counting Lattice Paths by Using Difference Equations with Non-constant Coefficients. The Bulletin of Irkutsk State University. Series Mathematics, 2023, vol. 44, pp. 55–70. https://doi.org/10.26516/1997-7670.2023.44.55
Keywords
generating function, difference equation, functional equation, lattice path
UDC
517.55+517.96
MSC
05A15, 39A05, 39A06, 39A27
DOI
https://doi.org/10.26516/1997-7670.2023.44.55
References
  1. Abramov S.A., Barkatou M.A, Van Hoeij M., Petkovsek M. Subanalytic solutions of linear difference equations and multidimensional hypergeometric sequences. Journal of Symbolic Computation, 2011, vol. 46, no. 11, pp. 1205–1228. https://doi.org/10.1016/j.jsc.2011.08.003
  2. Banderier C., Flajolet P. Basic analytic combinatorics of directed lattice paths Theoretical Computer Science, 2002, vol. 281, pp. 37–80. https://doi.org/10.1016/S0304-3975(02)00007-5
  3. Bloom D.M. Singles in a sequence of coin tosses. The College Mathematics Journal, 1998, vol. 29, no. 2, pp. 120–127. https://doi.org/10.2307/2687703
  4. Bousquet-M´𝑒lou M., Petkovˇ𝑠ek M. Linear recurrences with constant coefficients: the multivariate case. Discrete Mathematics, 2000, vol. 225, pp. 51–75. https://doi.org/10.1016/S0012-365X(00)00147-3
  5. Chandragiri S. Difference Equations and Generating Functions for Some Lattice Path Problems. Journal of Siberian Federal University. Mathematics & Physics, 2019, vol. 12, no. 5, pp. 551–559. https://doi.org/10.17516/1997-1397-2019-12-5-551-559
  6. Duchon P. On the Enumeration and Generation of Generalized Dyck Words. Discrete Mathematics, 2000, vol. 225, pp. 121–135. https://doi.org/10.1016/S0012-365X(00)00150-3
  7. Gelfond A.O. The calculus of finite differences. Moscow, KomKniga Publ., 2006. (in Russian)
  8. Gessel I.M. A Factorization for Formal Laurent Series and Lattice Path Enumeration. Journal of Combinatorial Theory, Series A, 1980, vol. 28, no. 3, pp. 321–337. https://doi.org/10.1016/0097-3165(80)90074-6
  9. Labelle J., Yeh Y.N. Generalized Dyck paths. Discrete Mathematics, 1990, vol. 82, no. 1, pp. 1–6. https://doi.org/10.1016/0012-365X(90)90039-K
  10. Leinartas E.K. Multiple Laurent series and fundamental solutions of linear difference equations. Siberian Mathematical Journal, 2007, vol. 48, no. 2, pp. 268–272. https://doi.org/10.1007/s11202-007-0026-0
  11. Lyapin A.P., Chandragiri S. Generating Functions for Vector Partitions and a Basic Recurrence Relation. Journal of Difference Equations and Applications, 2019, vol. 25, no. 7, pp. 1052–1061. https://doi.org/10.1080/10236198.2019.1649396
  12. Lyapin A.P., Chandragiri S. The Cauchy Problem for Multidimensional Difference Equations in Lattice Cones. Journal of Siberian Federal University. Mathematics & Physics, 2020, vol. 13, no. 2, pp. 187-196. https://doi.org/10.17516/1997-1397-2020-13-2-187-196
  13. de Moivre A. De Fractionibus Algebraicis Radicalitate Immunibus ad FractionesSimpliciores Reducendis, Deque Summandis Terminis Quarumdam Serierum Aequali Intervallo a Se Distantibus. Philosophical Transactions, 1722, vol. 32, no. 373,pp. 162–178. https://doi.org/10.1098/rstl.1722.0029
  14. Stanley R. Enumerative Combinatorics. Cambridge University Press, 1990, vol. 1.

Full text (english)