Keywords: lattice path, multiset permutation, open shop scheduling, turns

Article Content:-


We derive a precise formula of the maximum turns of unrestricted paths in a 3D lattice L(n1, n2, n3) under the step set {<1, 0, 0>, <0, 1, 0>, <0, 0, 1>}. The contribution of this study is threefold. First, the proposed formula should play a critical role in the work that derive a precise formula of unrestricted lattice paths in 3D lattices L(n1, n2, n3) with a given number of turns. Second, the result is identically a permutation statistics called maximum turns of three-item multiset permutation. Third, the proposed formula can be applied to an open shop scheduling problem that deals with setup time among three types of machines.



I. M. Gessel, A probabilistic method for lattice path enumeration, Journal of statistical planning and

inference, 14 (1986) 49–58.

K. Humphreys, A history and a survey of lattice path enumeration, Journal of statistical planning and

inference, 140(8) (2010) 2237-2254.

T. Kuo, Multiset Permutations in Lexicographic Order, International Journal of Emerging Technology

and Advanced Engineering, Volume 4, Issue 1, pp. 442-448, 2014.J. Labelle, Paths in the Cartesian, triangular, and hexagonal lattices, Bull. Inst. Combin. Appl, 17 (1996)


G. Mohanty, Lattice path counting and applications, Academic Press, New York, 1979.

M. L. Pinedo, Scheduling: theory, algorithms, and systems. Springer, 2012.

R. Sulanke, Counting lattice paths by Narayana polynomials, Electon. J. Combin. 7, 9 R40 (2000).


Citation Tools

How to Cite
Kuo, T. (2014). On The Maximum Turns of 3D Lattice Paths. International Journal Of Mathematics And Computer Research, 2(08), 574-580. Retrieved from