# Combinatorial Generation Algorithms for Some Lattice Paths Using the Method Based on AND/OR Trees +
## 3 Results
### Combinatorial Generation Algorithms for North-East Lattice Paths
#### 3.1.2 AND/OR Tree Structure  
Since Equation (2) satisfies the requirements of the applied method, the corresponding AND/OR tree structure for \(L_{n}^{m}\) can therefore be constructed (see Figure 2).  
For this AND/OR tree structure, there are the following initial conditions:  
* Each node labeled \(L_{n}^{0}\) is a leaf node in the AND/OR tree for \(L_{n}^{m}\);
* Each node labeled \(L_{0}^{m}\) is a leaf node in the AND/OR tree for \(L_{n}^{m}\).  
Figure 3 presents an example of the AND/OR tree structure for \(L_{n}^{m}\) where \(n=3\) and \(m=3\). The total number of its variants is equal to \(L_{3}^{3}=20\). Since the obtained AND/OR tree structure does not contain AND nodes, each variant of such a tree is a path from the root to a leaf.  
For a compact representation, a variant of the AND/OR tree for \(L_{n}^{m}\) is encoded by a sequence \(v=(v_{1},v_{2},\ldots)\) of the selected children of the OR nodes in this tree (the left child corresponds to \(v_{i}=1\) and the right child corresponds to \(v_{i}=2\)).  
**Theorem 1**.: _There is a bijection between the set of North-East lattice paths beginning at \((0,0)\) and ending at \((n,m)\) and the set of variants of the AND/OR tree for \(L_{n}^{m}\)._  
Proof.: The total number of North-East lattice paths beginning at \((0,0)\) and ending at \((n,m)\) is equal to \(L_{n}^{m}\). The total number of variants of the AND/OR tree for \(L_{n}^{m}\) presented in Figure 2 is also equal to \(L_{n}^{m}\). Therefore, it is possible to associate each such lattice path with one specific variant of the AND/OR tree for \(L_{n}^{m}\). A bijection between the set of North-East lattice paths beginning at \((0,0)\) and ending at \((n,m)\) and the set of variants of the AND/OR tree for \(L_{n}^{m}\) is defined by the following rules:  
Figure 3: An AND/OR tree for \(L_{3}^{3}\).  
Figure 2: An AND/OR tree for \(L_{n}^{m}\).  
* Each selected left child of the OR node labeled \(L_{n}^{m}\) determines the addition of one North-step to the North-East lattice path obtained by the subtree of the node labeled \(L_{n}^{m-1}\): the resulting lattice path is \((s_{1},\ldots,s_{n+m-1},N)\);
* Each selected right child of the OR node labeled \(L_{n}^{m}\) determines the addition of one East-step to the North-East lattice path obtained by the subtree of the node labeled \(L_{n-1}^{m}\): the resulting lattice path is \((s_{1},\ldots,s_{n+m-1},E)\);
* Each leaf node labeled \(L_{n}^{0}\) determines the lattice path from \((0,0)\) to \((n,0)\) that consists of \(n\) East-steps: the resulting lattice path is \((s_{1},\ldots,s_{n})=(E,\ldots,E)\);
* Each leaf node labeled \(L_{0}^{m}\) determines the lattice path from \((0,0)\) to \((0,m)\) that consists of \(m\) North-steps: the resulting lattice path is \((s_{1},\ldots,s_{m})=(N,\ldots,N)\).  
The algorithms that implement the developed bijection rules have linear time complexity \(O(n+m)\), since they require one pass to fill a sequence of \((n+m)\) elements. An example of applying these bijection rules is presented in Table 1.