# 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  
Applying the general approach described in [17], we developed algorithms for ranking (Algorithm 3) and unranking (Algorithm 4) the variants of the AND/OR tree for \(C_{n}\). The developed algorithms have the following the computational complexity:  
* Algorithm 3 has at most \(n\) recursive calls, where each such recursive call requires calculations of \(C_{n}\) maximum \((2n-1)\) times. Applying Equation (3), the calculation of \(C_{n}\) has linear time complexity \(O(n)\). Hence, Algorithm 3 has polynomial time complexity \(O(n^{3})\);
* Algorithm 4 has at most \(n\) recursive calls, where each such recursive call requires calculations of \(C_{n}\) maximum \((2n+1)\) times. Hence, Algorithm 4 has polynomial time complexity \(O(n^{3})\). Table 2 presents an example of ranking the combinatorial set of all Dyck paths beginning at \((0,0)\) and ending at \((3,3)\). \begin{table}
\begin{tabular}{c c c} \hline \hline
**Lattice Path** & **Variant of AND/OR Tree** & **Rank** \\ \hline \(E,E,N,N,N\) & \((0,(),(0,(),()))\) & 0 \\ \(E,E,N,E,N,N\) & \((0,(),(1,(0,(),()),()))\) & 1 \\ \(E,N,E,E,N,N\) & \((1,(0,(),()),(0,()))\) & 2 \\ \(E,E,N,N,E,N\) & \((2,(0,(),(0,())),())\) & 3 \\ \(E,N,E,N,E,N\)```
1 Rank_C(\(v=(I,v_{1},v_{2})\), \(n\))
2 begin
3 if\(n=0\)then\(r:=0\)
4 else
5\(sum:=\sum\limits_{i=0}^{I-1}C_{i}C_{n-1-i}\)
6\(w_{1}:=C(I)\)
7\(l_{1}:=\text{Rank\_C}\)(\(v_{1}\), \(I\))
8\(l_{2}:=\text{Rank\_C}\)(\(v_{2}\), \(n-1-I\))
9\(r:=sum+l_{1}+w_{1}l_{2}\)
10 end if
11 return\(r\)
12
13 end if
```

**Algorithm 3**An algorithm for ranking a variant of the AND/OR tree for \(C_{n}\). ```
1 Unrank_C(\(r,n\))
2 begin
3 if\(n=0\)then\(v:=()\)
4 else
5\(sum:=0\)
6 for\(i:=0\)to\(n-1\)do
7\(s:=\text{C}_{i}C_{n-1-i}\)
8 if\(sum+s>r\)then
9\(r:=r-sum\)
10\(l:=i\)
11 break
12
13 end if
14\(sum:=sum+s\)
15 end for
16\(w_{1}:=C(I)\)
17\(l_{1}:=r\mod w_{1}\)
18\(l_{2}:=\left\lfloor\frac{r}{w_{1}}\right\rfloor\)
19\(v_{1}:=\text{Unrank\_C}\)(\(l_{1}\), \(I\))
20\(v_{2}:=\text{Unrank\_C}\)(\(l_{2}\), \(n-1-I\))
21\(v:=(I,v_{1},v_{2})\)
22
23 end if
24 return\(v\)
25 end if
```

**Algorithm 4**An algorithm for unranking a variant of the AND/OR tree for \(C_{n}\). ### Combinatorial Generation Algorithms for Delannoy Paths

#### 3.3.1 Combinatorial Set

A Delannoy path is a lattice path in the plane which begins at \((0,0)\), ends at \((n,m)\), and consists of steps \((0,1)\), \((1,0)\) and \((1,1)\)[22]. The step \((1,1)\) is called the North-East-step and denoted by \(NE\). Thus, the set of Delannoy paths is a generalization of the North-East lattice paths beginning at \((0,0)\) and ending at \((n,m)\) by adding the North-East-steps. Figure 7 shows all possible 25 variants of the considered Delannoy paths for \(n=3\) and \(m=2\). The total number of Delannoy paths is defined by the Delannoy number \(D_{n}^{m}\) (the sequence \(A008288\) in OEIS [20]):

\[D_{n}^{m}=\sum_{i=1}^{\min(n,m)}\binom{n}{i}\binom{m}{i}2^{i}. \tag{5}\]

The value of \(D_{n}^{m}\) can also be calculated using the following recurrence that belongs to the required algebra \(\{\mathbb{N},+,\times,R\}\):

\[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}\]

In addition, the sequence of values of \(D_{n}^{m}\) is defined by the bivariate generating function

\[\sum_{n\geq 0}\sum_{m\geq 0}D_{n}^{m}x^{n}y^{m}=\frac{1}{1-x-y-xy}.\]

#### 3.3.2 AND/OR Tree Structure

Since Equation (6) satisfies the requirements of the applied method, the corresponding AND/OR tree structure for \(D_{n}^{m}\) can therefore be constructed (see Figure 8). Figure 7: All Delannoy paths beginning at \((0,0)\) and ending at \((3,2)\). For this AND/OR tree structure, there are the following initial conditions:

* Each node labeled \(D_{n}^{0}\) is a leaf node in the AND/OR tree for \(D_{n}^{m}\);
* Each node labeled \(D_{0}^{m}\) is a leaf node in the AND/OR tree for \(D_{n}^{m}\). Figure 9 presents an example of the AND/OR tree structure for \(D_{n}^{m}\) where \(n=3\) and \(m=2\).