# 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
A bijection between the set of Motzkin \(n\)-paths and the set of variants of the AND/OR tree for \(M_{n}\) is defined by the following rules:

* each selected left child of the OR node labeled \(M_{n}\) determines the addition of one North-East-step to the Motzkin \((n-1)\)-path obtained by the subtree of the node labeled \(M_{n-1}\) and consisting of \(k\) steps: the resulting Motzkin \(n\)-path is \((s_{1},\ldots,s_{k},NE)\);
* each selected child of the OR node labeled \(M_{n}\) determines the addition of two East-steps and North-steps to the Motzkin \((n-2)\)-path that merges the Motzkin \(I\)-path obtained by the subtree of the node labeled \(M_{I}\) and consisting of \(k_{1}\) steps and the Motzkin \((n-2-I)\)-path obtained by the subtree of the node labeled \(M_{n-2-I}\) and consisting of \(k_{2}\) steps: the resulting Motzkin \(n\)-path is \(\left(s_{1},\ldots,s_{k_{1}},E,E,s_{k_{1}+3},\ldots,s_{k_{1}+2+k_{2}},N,N\right)\);
* the subtree of the node labeled \(M_{I}\) (the left subtree) determines the Motzkin \(I\)-path of the form \(\left(s_{1},\ldots,s_{k_{1}}\right)\);
* the subtree of the node labeled \(M_{n-2-I}\) (the right subtree) determines the Motzkin \((n-2-I)\)-path of the form \(\left(s_{k_{1}+3},\ldots,s_{k_{1}+2+k_{2}}\right)\);
* each leaf node labeled \(M_{1}\) determines the lattice path from \((0,0)\) to \((1,1)\) that consists of one North-East-step: the resulting lattice path is \((s_{1})=(NE)\);
* each leaf node labeled \(M_{0}\) determines the empty lattice path \(()\). The algorithms that implement the developed bijection rules have polynomial time complexity \(O(n^{2})\), since they make \(n\) recursive calls where each such recursive call requires one pass to fill a sequence of maximum \(2n\) elements. An example of applying these bijection rules is presented in \[\sum_{n\geq 0}\sum_{m\geq 0}D_{n}^{m}x^{n}y^{m}=\frac{1}{1-x-y-xy}.\]0

#### 3.5.3 Ranking and Unranking Algorithms

Applying the general approach described in [17], we develop algorithms for ranking (Algorithm 9) and unranking (Algorithm 10) the variants of the AND/OR tree for \(M_{n}\). The developed algorithms have the following the computational complexity:

* Algorithm 9 has at most \(n\) recursive calls where \(I=-1\) (each such recursive call requires one assignment) and has at most \(n\) recursive calls where \(I\
eq-1\) (each such recursive call requires calculations of \(M_{n}\) maximum \((2n-2)\) times). Applying Equation (9), the calculation of \(M_{n}\) has polynomial time complexity \(O(n^{2})\). Hence, Algorithm 9 has polynomial time complexity \(O(n^{4})\);
* Algorithm 10 has at most \(n\) recursive calls where \(I=-1\) (each such recursive call requires calculations of \(M_{n}\)) and has at most \(n\) recursive calls where \(I\
eq-1\) (each such recursive call requires calculations of \(M_{n}\) maximum \(2n\) times). Hence, Algorithm 10 has polynomial time complexity \(O(n^{4})\). \begin{table}
\begin{tabular}{c c c} \hline \hline
**Lattice path** & **Variant of AND/OR tree** & **Rank** \\ \hline \(NE,NE,NE\) & \((-1,(-1,(-1,())))\) & 0 \\ \(E,E,N,N,NE\) & \((-1,(0,(),()))\) & 1 \\ \(E,E,NE,N,N\) & \((0,(),(-1,()))\) & 2 \\ \(NE,E,E,N,N\) & \((1,(-1,()),())\) & 3 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Ranking the set of Motzkin paths beginning at \((0,0)\) and ending at \((3,3)\). ```
1 Rank_M(\(v=(I,v_{1},\ldots)\), \(n\)) begin
2 if\(n=0\)then\(r:=0\)
3 else
4 if\(I=-1\)then\(r:=\)Rank_M(\(v_{1}\), \(n-1\))
5 else
6\(sum:=M(n-1)+\sum\limits_{i=0}^{I-1}M_{i}M_{n-2-i}\)
7\(w_{1}:=M(I)\)
8\(l_{1}:=\)Rank_M(\(v_{1}\), \(I\))
9\(l_{2}:=\)Rank_M(\(v_{2}\), \(n-2-I\))
10\(r:=sum+l_{1}+w_{1}l_{2}\)
11
12 end if
13
14 end for
15
16 return\(r\)
17
18 end for
```

**Algorithm 9**An algorithm for ranking a variant of the AND/OR tree for \(M_{n}\).