## 2 Algorithms  
In this Section, we propose an optimal algorithm for generating 2D lattice _L(n_1, \(n\)2) paths according to a given number of _turns_. For completeness, the following results are introduced without proof [3]. Note that, throughout the paper, all variables are positive integers. **Definition 1. ** Let \(t\) denote the number of _turns_ of a path that has \(a\) EN-_turns_ and \(b\) NE-_turns_, that is, \(t=a+b\). **Lemma 1. **\(\left|a-b\right|=0\) or \(\left|a-b\right|=1\). **Lemma 2. ** If \(t\) is even \(\left(2k\right)\), then \(\,a=b=k\). If \(t\) is odd \(\left(2k-1\right)\), then \(\,a=k\) and \(\,b=k-1\) when first step is eastward, or \(\,a=k-1\) and \(\,b=k\) when first step is northward. **Lemma 3. ** For a 2D integer rectangular lattice \(L(n_{1},\,n_{2}),\,n_{1}>0\) and \(\,n_{2}>0\), assume that \(\,n_{1}\leq n_{2}\) the minimum number of _turns_ of a path is one and the maximum number of _turns_ of a path is \(\,2n_{1}-1\) if \(\,n_{1}=n_{2}\) or \(\,2n_{1}\) if \(\,n_{1}<n_{2}\). **Theorem 1. ** Let \(\,P(n_{1},n_{2},t)\) denote the number of paths with a given number of _turns_\(t\), then:  
\[P(n_{1},\,n_{2},\,2k)=\binom{n_{1}-1}{k}\binom{n_{2}-1}{k-1}+\binom{n_{2}-1}{ k}\binom{n_{1}-1}{k-1}, \tag{1}\]  
and  
\[P(n_{1},\,n_{2},\,2k-1)=2\binom{n_{1}-1}{k-1}\binom{n_{2}-1}{k-1}. \tag{2}\]  
In the identity (1), the term of \(\binom{n_{1}-1}{k}\binom{n_{2}-1}{k-1}\) stands for the number of paths that their first step is eastward, and the term of \(\binom{n_{2}-1}{k}\binom{n_{1}-1}{k-1}\) stands for the number of paths that their first step is northward. The reason is explained as follows. For a path with even \(\left(2k\right)\)_turns_, by Definition 1 and Lemma 2, we know that it must be composed of \(k\) EN-_turns_ and \(k\) NE-_turns_. Thus, when the first step is eastward, what we need to do in the whole route is choose \(k\) points from \(n_{\mathrm{i}}-1\) points and choose \(k-1\) points from \(n_{\mathrm{2}}-1\) points; when the first step is northward, what we need to do in the whole route is choose \(k\) points from \(n_{\mathrm{2}}-1\) points and choose \(k-1\) points from \(n_{\mathrm{i}}-1\) points. Since the first step is either eastward or northward, we have the identity (1). Similarly, for a path with odd (\(2k-1\)) _turns_, by Definition 1 and Lemma 2, we know that it must be composed of \(k\) NE-_turns_ and \(k-1\) EN-_turns_ when first step is northward, or that it must be composed of \(k\) EN-_turns_ and \(k-1\) NE-_turns_ when first step is eastward. Thus, when the first step is northward, what we need to do in the whole route are choose \(k-1\) points from \(n_{\mathrm{2}}-1\) points and choose \(k-1\) points from \(n_{\mathrm{1}}-1\) points; when the first step is eastward, what we need to do in the whole path are choose \(k-1\) points from \(n_{\mathrm{i}}-1\) points and choose \(k-1\) points from \(n_{\mathrm{2}}-1\) points. Since the first step is either northward or eastward, we have the identity (2). Based on Theorem 1, we propose the Algorithm **G2 DLP** where two Algorithms H and L, borrowed from others with some amendments and additions to meet the purpose of this study, are embedded respectively in Algorithms **Partition** and **Permute**. (The Algorithm **G2 DLP** is put in Appendix) Algorithm **Partition** is based on an Algorithm H that generates all partitions of an integer [18] (p. 38). Since Algorithm H treats, for example partitioning integer 11 into 4 parts, a partition of 8111 as same as another partition of 1811, we need to call Algorithm **Permute** to permute the partitions produced by Algorithm H. On the other hand, Algorithm **Permute** is based on an Algorithm L that generates all permutations of a multiset in lexicographic order [1] (pp. 39-40). Since Algorithm L assumes that the initial elements are in a non-decreasing order but Algorithm H produces partitions of an integer in a _colex_ order (That is, lexicographic order of the reflected sequence.