рус eng
«ИЗВЕСТИЯ ИРКУТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА». СЕРИЯ «МАТЕМАТИКА»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

Список выпусков > Серия «Математика». 2023. Том 44

Подсчет путей решетки с использованием разностных уравнений с непостоянными коэффициентами

Автор(ы)
Ш. Чандрагири1

1Институт математики им. С. Л. Соболева СО РАН, Новосибирск, Российская Федерация

Аннотация
Траектории решетки могут быть подсчитаны благодаря их шаговым векторам, которые выровнены по положительному октанту. Путь может проходить от одной точки к бесконечному количеству других, если не применяется ограничение, так что каждая точка имеет только конечное число предшественников. Линейные разностные уравнения с непостоянными коэффициентами будут использоваться для учета этого ограничения при изучении траекторий решетки, которые лежат на линии с рациональным наклоном или над ней. Получены генерирующие функции, основанные на разработке конкретного метода вычисления числа ограниченных путей решетки.
Об авторах
Чандрагири Шрилата, научный сотрудник, постдокторант, Институт математики им. С. Л. Соболева СО РАН, Новосибирск, 630090, Российская Федерация, srilathasami@math.nsc.ru
Ссылка для цитирования
Chandragiri S. Counting Lattice Paths by Using Difference Equations with Non-constant Coefficients // Известия Иркутского государственного университета. Серия Математика. 2023. Т. 44. C. 55–70. https://doi.org/10.26516/1997-7670.2023.44.55
Ключевые слова
производящая функция, разностное уравнение, функциональное уравнение, решеточный путь
УДК
517.55+517.96
MSC
05A15, 39A05, 39A06, 39A27
DOI
https://doi.org/10.26516/1997-7670.2023.44.55
Литература
  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.

Полная версия (english)