文章詳目資料

Journal of Computers EIMEDLINEScopus

  • 加入收藏
  • 下載文章
篇名 Enumeration of 2D Lattice Paths with a Given Number of Turns
卷期 26:4
作者 Kuo,Ting
頁次 001-007
關鍵字 lattice pathsenumerationmultiset permutationschedulingturnEIMEDLINEScopus
出刊日期 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>}.

相關文獻