ENUMERATION OF UNRESTRICTED 3D LATTICE L (n_1, n_2, 2) PATHS WITH A GIVEN NUMBER OF TURNS

摘要

For 3D lattices L(n_1, n_2, 2), under the step set {<1, 0, 0>, <0, 1, 0>, <0, 0, 1>}, we derive and prove a formula of unrestricted paths with a given number of turns. The result identically is a multiset permutation statistics called turns of a three-item {A~(n1), B~(n2), C~2} multiset permutation. Two potential applications are described: open shop scheduling and cryptosystem. Two concomitant problems are proposed for future works. First, for extending the result to a general case L(n_1, n_2, n_3), it is needed to know that how to partition an integer r into at most n_3 parts where each part can be 0, 1, or 2, and r = 1, 2,…, 2n_3. Second, how to design an efficient algorithm for generating 3D lattice L(n_1, n_2, 2) paths, equivalently three-item multiset {A~(n1), B~(n2), C~2} permutations, with a given number of turns.