篇名 | Enumeration of 2D Lattice Paths with a Given Number of Turns |
---|---|
卷期 | 26:4 |
作者 | Kuo,Ting |
頁次 | 001-007 |
關鍵字 | lattice paths 、 enumeration 、 multiset permutation 、 scheduling 、 turn 、 EI 、 MEDLINE 、 Scopus |
出刊日期 | 201601 |
In this study, we address a lattice path enumeration problem. We derive a precise formula of unrestricted lattice paths, in a 2D integer rectangular lattice L(n1, n2) under the step set {<1, 0>, <0, 1>}, with a given number of turns totally but not NE-turns only. We give a combinatorial proof of the proposed formula, present results on some cases L(n1, n2) that are confirmed by an algorithm that deals with the generation of a two-item multiset {0^n1, 1^n2} permutation, and show a graphical demonstration for a simple case L(3, 4). The proposed formula can be applied to a scheduling problem that deals with setup time between two types of machines, and can be extended to a 3D integer rectangular lattice under the step set {<1, 0, 0>, <0, 1, 0>, <0, 0, 1>}.