Keywords:-
Article Content:-
Abstract
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.
References:-
References
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)
–61.
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).