Journals / Fundamentals of Contemporary Mathematical Sciences / 2026 / Volume: 6 Issue: 1

n-Dimensional Lattice Path Enumeration

Alper Vural(BOGAZICI UNIVERSITY)0000-0001-9985-3932
Cemil Karaçam(YILDIZ TECHNICAL UNIVERSITY)0000-0001-7186-5114
Pages
—
Publication Date
2025-01-31
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

The crucial part of our algorithm is that it doesn't rely on finding all paths and checking each path for usage of restricted points.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:Let V_n be a set of integer vectors.
📊
Key Findings & Data:We enumerate lattice paths that only uses vectors in V_n.
💡
Conclusion & Impact:The crucial part of our algorithm is that it doesn't rely on finding all paths and checking each path for usage of restricted points.
🔬Design:Research Article
📍Scope:Comprehensive Sample
⚙️Variables:Lattice paths · Biinary paths · enumeration in n dimensions

Abstract

Let V_n be a set of integer vectors. We enumerate lattice paths that only uses vectors in V_n. Unlike most lattice path enumeration problems, the number of dimensions isn't fixed and the vector set is dependent on the dimension. This requires us to follow a different approach in explicitly expressing the number of lattice paths from origin to any point in $n$-dimensional space. We notice that a special case of this problem corresponds to Fubini numbers, which count the number of weak orderings of a set consisting of $n$ elements. Then, we find the recursive relation of this sequence. Finally, we develop an algorithm that can be used to find the number of paths between any two points that do not touch the lattice points in R. The crucial part of our algorithm is that it doesn't rely on finding all paths and checking each path for usage of restricted points.

🔖

Cite This Article

Vural, A., Karaçam, C. (2025). n-Dimensional Lattice Path Enumeration. Fundamentals of Contemporary Mathematical Sciences, Volume: 6 Issue: 1. https://doi.org/10.54974/fcmathsci.1433118

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (11)

  1. Autebert J.M., Latapy M., Schwer S.R., Le treillis des chemins de Delannoy, Discrete Mathematics, 258(1-3), 225-234, 2002.
  2. Autebert J.M., Schwer S.R., On generalized Delannoy paths, SIAM Journal on Discrete Mathematics, 16(2), 208-223, 2003.
  3. Goodman E., Narayana T.V., Lattice paths with diagonal steps, Canadian Mathematical Bulletin, 12(6), 847-855, 1969.
  4. Handa B.R., Mohanty S.G., Higher dimensional lattice paths with diagonal steps, Discrete Mathematics, 15(2), 137-140, 1976.
  5. Humphreys K., A history and a survey of lattice path enumeration, Journal of Statistical Planning and Inference, 140(8), 2237-2254, 2010.
  6. Itai A., Papadimitriou C.H., Szwarcfiter J.L., Hamilton paths in grid graphs, SIAM Journal on Computing, 11(4), 676-686, 1982.
  7. Krattenthaler C., Lattice path enumeration, arXiv:1503.05930, 2015.
  8. Krattenthaler C., Mohanty S.G., On lattice path counting by major index and descents, European Journal of Combinatorics, 14(1), 43-51, 1993.
  9. Mohanty G., Lattice Path Counting and Applications, Academic Press, 2014.
  10. Simmons G.J., Almost all n-dimensional rectangular lattices are Hamiltonlaceable, 9th Southeastern Conference on Combinatoric Graph Theory and Computing, USA, 1977.
  11. Sulanke R.A., A determinant for q-counting n-dimensional lattice paths, Discrete Mathematics, 81(1), 91-96, 1990.