# 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 developed algorithms have the following computational complexity:

* Algorithm 5 has at most \(m\) recursive calls where \(v_{1}=1\) (each such recursive call requires one assignment), has at most \(n\) recursive calls where \(v_{1}=2\) (each such recursive call requires calculations of \(D_{n}^{m-1}\)), and has at most \(\min(n,m)\) recursive calls where \(v_{1}=3\) (each such recursive call requires calculations of \(D_{n}^{m-1}\) and \(D_{n-1}^{m}\)). Applying Equation (5), the calculation of \(D_{n}^{m}\) has polynomial time complexity \(O(m^{2})\) for \(m<n\) and \(O(n^{2})\) for \(m>n\). Hence, Algorithm 5 has polynomial time complexity \(O(m^{2}(n+m))\) for \(m<n\) and \(O(m+n^{3})\) for \(m>n\);
* Algorithm 6 has at most \((n+m)\) recursive calls where each such recursive call requires calculations of \(D_{n}^{m-1}\) or \(D_{n-1}^{m}\). Hence, Algorithm 2 has polynomial time complexity \(O(m^{2}(n+m))\) for \(m<n\) and \(O(n^{2}(n+m))\) for \(m>n\). Table 3 presents an example of ranking the combinatorial set of all Delannoy paths beginning at \((0,0)\) and ending at \((3,2)\). ### Combinatorial Generation Algorithms for Schroder Paths

#### 3.4.1 Combinatorial Set

A Schroder \(n\)-path is a lattice path in the plane which begins at \((0,0)\), ends at \((n,n)\), consists of steps \((0,1)\), \((1,0)\), and \((1,1)\), and never rises above the diagonal \(y=x\)[23]. The set of Schroder \(n\)-paths is a subset of the Delannoy paths beginning at \((0,0)\) and ending at \((n,n)\). Figure 10 shows all possible 22 variants of the considered Schroder paths for \(n=3\). The total number of Schroder \(n\)-paths is defined by the Schroder number \(S_{n}\) (the sequence \(A006318\) in OEIS [20]):

\[S_{n}=\sum_{i=0}^{n}\frac{1}{i+1}\binom{n+i}{i}\binom{n}{i}. \tag{7}\]

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

\[S_{n}=S_{n-1}+\sum_{i=0}^{n-1}S_{i}S_{n-1-i},\quad S_{0}=1. \tag{8}\]

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

\[\sum_{n\geq 0}S_{n}x^{n}=\frac{1-x-\sqrt{1-6x+x^{2}}}{2x}.\]

#### 3.4.2 AND/OR Tree Structure

Since Equation (8) satisfies the requirements of the applied method, the corresponding AND/OR tree structure for \(S_{n}\) can therefore be constructed (see Figure 11). \[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}\]0 All Schroder paths beginning at \((0,0)\) and ending at \((3,3)\). For this AND/OR tree structure, there is the following initial condition:

* Each node labeled \(S_{0}\) is a leaf node in the AND/OR tree for \(S_{n}\). Figure 12 presents an example of the AND/OR tree structure for \(S_{n}\) where \(n=3\). The total number of its variants is equal to \(S_{3}=22\). For a compact representation, a variant of the AND/OR tree for \(S_{n}\) is encoded by a sequence \(v\): 1. If the left child of the OR node labeled \(S_{n}\) is selected, then \(v=(I,v_{1})\), where
* \(v_{1}\) corresponds to the variant of the subtree of the node labeled \(S_{n-1}\); 2. Otherwise \(v=(I,v_{1},v_{2})\), where
* \(I\) corresponds to the selected value of \(i\) in the AND/OR tree for \(S_{n}\);
* \(v_{1}\) corresponds to the variant of the subtree of the node labeled \(S_{1}\);
* \(v_{2}\) corresponds to the variant of the subtree of the node labeled \(S_{n-1-i}\); 3. An empty sequence \(v=()\) corresponds to the selection of a leaf node labeled \(S_{0}\). **Theorem 4**. : _There is a bijection between the set of Schroder \(n\)-paths and the set of variants of the AND/OR tree for \(S_{n}\)._

Proof. : The total number of Schroder \(n\)-paths is equal to \(S_{n}\). The total number of variants of the AND/OR tree for \(S_{n}\) presented in Figure 11 is also equal to \(S_{n}\). Therefore, it is possible to associate each such lattice path with one specific variant of the AND/OR tree for \(S_{n}\).