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

* Each selected left child of the OR node labeled \(S_{n}\) determines the addition of one North-East-step to the Schroder \((n-1)\)-path obtained by the subtree of the node labeled \(S_{n-1}\) and consisting of \(k\) steps: the resulting Schroder \(n\)-path is \((s_{1},\ldots,s_{k},NE)\);

\[D_{n}^{m}=D_{n}^{m-1}+D_{n-1}^{m}+D_{n-1}^{m-1},\quad D_{n}^{0}=D_{0}^{m}=1. \tag{6}\]1 An AND/OR tree for \(S_{n}\). \[D_{n}^{m}=D_{n}^{m-1}+D_{n-1}^{m}+D_{n-1}^{m-1},\quad D_{n}^{0}=D_{0}^{m}=1. \tag{6}\]2 An AND/OR tree for \(S_{3}\). * Each selected child of the OR node labeled \(S_{n}\) determines the addition of one East-step and one North-step to the Schroder \((n-1)\)-path that merges the Schroder \(I\)-path obtained by the subtree of the node labeled \(S_{I}\) and consisting of \(k_{1}\) steps and the Schroder \((n-1-I)\)-path obtained by the subtree of the node labeled \(S_{n-1-I}\) and consisting of \(k_{2}\) steps: the resulting Schroder \(n\)-path is \(\big{(}s_{1},\ldots,s_{k_{1}},E,s_{k_{1}+2},\ldots,s_{k_{1}+1+k_{2}},N\big{)}\);
* The subtree of the node labeled \(S_{I}\) (the left subtree) determines the Schroder \(I\)-path of the form \(\big{(}s_{1},\ldots,s_{k_{1}}\big{)}\);
* The subtree of the node labeled \(S_{n-1-I}\) (the right subtree) determines the Schroder \((n-1-I)\)-path of the form \(\big{(}s_{k_{1}+2},\ldots,s_{k_{1}+1+k_{2}}\big{)}\);
* Each leaf node labeled \(S_{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 \[D_{n}^{m}=D_{n}^{m-1}+D_{n-1}^{m}+D_{n-1}^{m-1},\quad D_{n}^{0}=D_{0}^{m}=1. \tag{6}\]3

#### 3.4.3. Ranking and Unranking Algorithms

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

* Algorithm 7 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 \(S_{n}\) maximum \(2n\) times). Applying Equation (7), the calculation of \(S_{n}\) has polynomial time complexity \(O(n^{2})\). Hence, Algorithm 7 has polynomial time complexity \(O(n^{4})\);
* Algorithm 8 has at most \(n\) recursive calls where \(I=-1\) (each such recursive call requires calculations of \(S_{n}\)) and has at most \(n\) recursive calls where \(I\
eq-1\) (each such recursive call requires calculations of \(S_{n}\) maximum \((2n+2)\) times). Hence, Algorithm 8 has polynomial time complexity \(O(n^{4})\). \begin{table}
\begin{tabular}{c c c} \hline
**Lattice Path** & **Variant of AND/OR Tree** & **Rank** \\ \hline \(NE,NE,NE\) & \((-1,(-1,(-1,(0))))\) & 0 \\ \(E,N,NE,NE\) & \((-1,(-1,(0,())))\) & 1 \\ \(E,NE,N,NE\) & \((-1,(0,(),(-1,())))\) & 2 \\ \(E,E,N,N,NE\) & \((-1,(0,(),(0,())))\) & 3 \\ \(NE,E,N,NE\) &



```
1 Rank_S(\(v=(I,v_{1},\ldots)\), \(n\)) begin
2 if\(n=0\)then\(r:=0\)
3 else
4 if\(I=-1\)then\(r:=\)Rank_S(\(v_{1}\), \(n-1\))
5 else
6\(sum:=S(n-1)+\sum\limits_{i=0}^{I-1}S_{i}S_{n-1-i}\)
7\(w_{1}:=S(I)\)
8\(l_{1}:=\)Rank_S(\(v_{1}\), \(I\))
9\(l_{2}:=\)Rank_S(\(v_{2}\), \(n-1-I\))
10\(r:=sum+l_{1}+w_{1}l_{2}\)
11
12 end if
13
14 end for
15 return\(r\)
16
17 end for
```

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