# Combinatorial Generation Algorithms for Some Lattice Paths Using the Method Based on AND/OR Trees +
## 3 Results
### Combinatorial Generation Algorithms for Dyck Paths
#### 3.2.3 Ranking and Unranking Algorithms
The total number of its variants is equal to \(D_{3}^{2}=25\). 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 \(D_{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\), the middle child corresponds to \(v_{i}=2\) and the right child corresponds to \(v_{i}=3\)). Theorem 3.2: _There is a bijection between the set of Delannoy paths beginning at \((0,0)\) and ending at \((n,m)\) and the set of variants of the AND/OR tree for \(D_{n}^{m}\)._

Proof. : The total number of Delannoy paths beginning at \((0,0)\) and ending at \((n,m)\) is equal to \(D_{n}^{m}\). The total number of variants of the AND/OR tree for \(D_{n}^{m}\) presented in Figure 8 is also equal to \(D_{n}^{m}\). Therefore, it is possible to associate each such lattice path with one specific variant of the AND/OR tree for \(D_{n}^{m}\). A bijection between the set of Delannoy paths beginning at \((0,0)\) and ending at \((n,m)\) and the set of variants of the AND/OR tree for \(D_{n}^{m}\) is defined by the following rules:

* Each selected left child of the OR node labeled \(D_{n}^{m}\) determines the addition of one North-step to the Delannoy path obtained by the subtree of the node labeled \(D_{n}^{m-1}\) and consisting of \(k\) steps: the resulting lattice path is \((s_{1},\ldots,s_{k},N)\);

Figure 8: An AND/OR tree for \(D_{n}^{m}\). Figure 9: An AND/OR tree for \(D_{3}^{2}\). Each selected middle child of the OR node labeled \(D_{n}^{m}\) determines the addition of one East-step to the Delannoy path obtained by the subtree of the node labeled \(D_{n-1}^{m}\) and consisting of \(k\) steps: the resulting lattice path is \((s_{1},\ldots,s_{k},E)\);
* Each selected right child of the OR node labeled \(D_{n}^{m}\) determines the addition of one North-East-step to the Delannoy path obtained by the subtree of the node labeled \(D_{n-1}^{m-1}\) and consisting of \(k\) steps: the resulting lattice path is \((s_{1},\ldots,s_{k},NE)\);
* Each leaf node labeled \(D_{n}^{0}\) determines the Delannoy 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 \(D_{0}^{m}\) determines the Delannoy 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 maximum \((n+m)\) elements. An example of applying these bijection rules is presented in Table 3.

#### 3.3.3 Ranking and Unranking Algorithms

Applying the general approach described in [17], we develop algorithms for ranking (Algorithm 5) and unranking (Algorithm 6) the variants of the AND/OR tree for \(D_{n}^{m}\). \begin{table}
\begin{tabular}{c c c} \hline \hline
**Lattice Path** & **Variant of AND/OR Tree** & **Rank** \\ \hline \(E,E,E,N,N\) & \((1,1)\) & 0 \\ \(E,E,N,E,N\) & \((1,2,1)\) & 1 \\ \(E,N,E,E,N\) & \((1,2,2,1)\) & 2 \\ \(N,E,E,E,N\) & \((1,2,2,2)\) & 3 \\ \(NE,E,



```
1\(\text{\rm{Unrank\_D}}(r,n,m)\)
2 begin
3 if\(n=0\) or \(m=0\)then\(r:=0\)
4 else
5 if\(v_{1}=1\)then\(r:=\text{\rm{Rank\_D}}((v_{2},\ldots),\,n,\,m-1)\)
6 elseif\(v_{1}=2\)then\(r:=D_{n}^{m-1}+\text{\rm{Rank\_D}}((v_{2},\ldots),\,n-1,\,m)\)
7 else\(r:=D_{n}^{m-1}+D_{n-1}^{m}+\text{\rm{Rank\_D}}((v_{2},\ldots),\,n-1,\,m-1)\)
8
9 end if
10 return\(r\)
11 end while
```

**Algorithm 5**An algorithm for ranking a variant of the AND/OR tree for \(D_{n}^{m}\).