# 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
```
1 Unrank_S(\(r,n\)) begin
2 if\(n=0\)then\(v:=()\)
3 else
4 if\(r<S_{n-1}\)then
5\(l:=-1\)
6\(v_{1}:=\)Unrank_S(\(r,n-1\))
7\(v:=(I,v_{1})\)
8 end if
9 else
10\(r:=r-S_{n-1}\)
11\(sum:=0\)
12 for\(i:=0\)to\(n-1\)do
13\(s:=S_{i}S_{n-1-i}\)
14 if\(sum+s>r\)then
15\(r:=r-sum\)
16\(l:=i\)
17 break
18
19 end if
20\(sum:=sum+s\)
21
22 end for
23\(w_{1}:=S(I)\)
24\(l_{1}:=r\mod w_{1}\)
25\(l_{2}:=\left\lfloor\frac{r}{w_{1}}\right\rfloor\)
26\(v_{1}:=\)Unrank_S(\(l_{1}\), \(I\))
27\(v_{2}:=\)Unrank_S(\(l_{2}\), \(n-1-I\))
28\(v:=(I,v_{1},v_{2})\)
29 end if
30
31 end for
32 return\(v\)
33 end for
```

**Algorithm 8**An algorithm for unranking a variant of the AND/OR tree for \(S_{n}\). Table 4 presents an example of ranking the combinatorial set of all Schroder paths beginning at \((0,0)\) and ending at \((3,3)\). ### Combinatorial Generation Algorithms for Motzkin Paths

#### 3.5.1 Combinatorial Set

A Motzkin \(n\)-path is a lattice path in the plane which begins at \((0,0)\), ends at \((n,n)\), consists of steps \((0,2)\), \((2,0)\) and \((1,1)\), and never rises above the diagonal \(y=x\)[24]. The step \((0,2)\) is the double North-step, the step \((2,0)\) is the double East-step. The set of Motzkin \(n\)-paths is a subset of the Schroder \(n\)-paths. Figure 13 shows all possible 4 variants of the considered Motzkin paths for \(n=3\). The total number of Motzkin \(n\)-paths is defined by the Motzkin number \(M_{n}\) (the sequence \(A001006\) in OEIS [20]):

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

The value of \(M_{n}\) 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}\]5

In addition, the sequence of values of \(M_{n}\) is defined by the generating function

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

#### 3.5.2 AND/OR Tree Structure

Since Equation (10) satisfies the requirements of the applied method, the corresponding AND/OR tree structure for \(M_{n}\) can therefore be constructed (see Figure 14). For this AND/OR tree structure, there is the following initial condition:

* each node labeled \(M_{0}\) or \(M_{1}\) is a leaf node in the AND/OR tree for \(M_{n}\). Figure 15 presents an example of the AND/OR tree structure for \(M_{n}\) where \(n=3\). The total number of its variants is equal to \(M_{3}=4\). \[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}\]7 All Motzkin paths beginning at \((0,0)\) and ending at \((3,3)\). For a compact representation, a variant of the AND/OR tree for \(M_{n}\) is encoded by a sequence \(v\):

1. If the left child of the OR node labeled \(M_{n}\) is selected, then \(v=(I,v_{1})\), where \(\bullet\quad I=-1\); \(\bullet\quad v_{1}\) corresponds to the variant of the subtree of the node labeled \(M_{n-1}\);
2. Otherwise \(v=(I,v_{1},v_{2})\), where \(\bullet\quad I\) corresponds to the selected value of \(i\) in the AND/OR tree for \(M_{n}\); \(\bullet\quad v_{1}\) corresponds to the variant of the subtree of the node labeled \(M_{1}\); \(\bullet\quad v_{2}\) corresponds to the variant of the subtree of the node labeled \(M_{n-2-1}\);
3. An empty sequence \(v=()\) corresponds to the selection of a leaf node labeled \(M_{0}\). **Theorem 5**. : _There is a bijection between the set of Motzkin \(n\)-paths and the set of variants of the AND/OR tree for \(M_{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}\]8 An AND/OR tree for \(M_{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}\]9 An AND/OR tree for \(M_{3}\). Proof. : The total number of Motzkin \(n\)-paths is equal to \(M_{n}\). The total number of variants of the AND/OR tree for \(M_{n}\) presented in Figure 14 is also equal to \(M_{n}\). Therefore, it is possible to associate each such lattice path with one specific variant of the AND/OR tree for \(M_{n}\).