n-Dimensional Lattice Path Enumeration

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.

Keywords

• Lattice paths
• Biinary paths
• enumeration in n dimensions
• forbidden paths

References

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.