1 Introduction↩︎

A grand Motzkin path with air pockets is a non-empty lattice path in the first and fourth quadrant of \(\mathbb{Z}^2\), starting at the origin \((0,0)\), ending on the \(x\)-axis, and consisting of up-steps \((1, 1)\), horizontal steps \((1, 0)\), and down-steps \((1, -k)\) for \(k \geq 1\), with the condition that no two down-steps are consecutive. As an example, Figure 1 illustrates the ten grand Motzkin paths with air pockets for \(n = 3\). Each grand Motzkin path with air pockets can be represented by a unique tuple \((a_1, a_2, \cdots, a_n)\), where \(a_i\) denotes the step at position \(i\) in the path, with \(a_i = 1\) representing an up-step \((1, 1)\), \(a_i = 0\) representing a horizontal step \((1, 0)\), and \(a_i = -k\) representing a down-step \((1, -k)\) for \(k \geq 1\). The tuples corresponding to the ten grand Motzkin paths with air pockets in Figure 1 for \(n = 3\) are as follows:

A grand Dyck path with air pockets is a grand Motzkin path with air pockets that uses no horizontal steps. As an example, the tuples corresponding to the three grand Dyck paths with air pockets (underlined in Figure 1) for \(n = 3\) are \((-2, 1, 1)\), \((1, -2, 1)\), and \((1, 1, -2)\).

The number of grand Dyck paths with air pockets, also known as Whitney numbers of the second kind, corresponds to sequence A051291 in the Online Encyclopedia of Integer Sequences [1]. Baril et al. [2]–[4] studied enumerative results and derived generating functions for grand Dyck paths with air pockets under various restrictions. For example, the number of grand Dyck paths with air pockets of length \(n\) is given by the following generating function: \[\nonumber G(t) = \frac{1 + 2t^2 - t^3 - (1 - t) \sqrt{1 - 2t - t^2 - 2t^3 + t^4}}{2t \sqrt{1 - 2t - t^2 - 2t^3 + t^4}}.\] The first ten terms of this generating function are 1, 2, 3, 7, 17, 40, 97, 238, 587, and 1458. However, no closed-form formula is known for this sequence, and evaluating the generating function for large \(n\) is computationally expensive due to the complex square root term. The first ten terms for the enumeration sequence of grand Motzkin paths with air pockets are 1, 3, 10, 32, 106, 361, 1247, 4351, 15304, and 54172. More interestingly, the number of grand Motzkin paths with air pockets is not even listed in the Online Encyclopedia of Integer Sequences as of this writing, and no closed-form formula has been established. This paper presents the first known closed-form formulae for the enumeration of both grand Dyck paths and grand Motzkin paths with air pockets.

Dyck paths and Motzkin paths are well-studied combinatorial objects with a wide variety of applications in areas such as geometry, algebra, probability, and computer science. For example, Dyck paths have been extensively studied in Knuth’s The Art of Computer Programming, Volume 4, Fascicle 4 [5], particularly in the contexts of binary trees, parenthesis matchings, and lattice paths. Motzkin paths, which generalize Dyck paths by allowing horizontal steps, appear in diverse applications including RNA secondary structure modeling, non-crossing partitions, and bounded lattice paths [6], [7]. Both Dyck paths and Motzkin paths encode a wide variety of combinatorial objects, including binary trees, balanced parentheses, ballot sequences, and stack-sortable permutations [8]–[15]. An interesting application of grand Motzkin paths or grand Dyck paths with air pockets, as discussed in [4], is to model aviation paths where the “air pockets” represent turbulences with consecutive turbulences are merged into one. Grand Motzkin paths or grand Dyck paths with air pockets also have applications in queue or stack evolution, interpreting paths with resets or “catastrophes” [16], and modeling stock market crashes. For more applications of Motzkin paths, Dyck paths, and related structures, see [6], [7], [17], [18].

One of the most important aspects of combinatorial generation is to list the instances of a combinatorial object so that consecutive instances differ by a specified closeness condition involving a constant amount of change. Lists of this type are called Gray codes. This terminology is due to the eponymous binary reflected Gray code (BRGC) by Frank Gray, which orders the \(2^n\) binary strings of length \(n\) so that consecutive strings differ in one bit. For example, when \(n = 5\) the order is \[\begin{tabular}{l} \label{comb95order95n5}00000, 00001, 00011, 00010, 00110, 00111, 00101, 00100,\\ 01100, 01101, 01111, 01110, 01010, 01011, 01001, 01000,\\ 11000, 11001, 11011, 11010, 11110, 11111, 11101, 11100,\\ 10100, 10101, 10111, 10110, 10010, 10011, 10001, 10000. \end{tabular}\tag{1}\] The BRGC listing is a 1-Gray code since consecutive strings differ by one bit change. In this paper, we are focusing on 2-Gray code, where consecutive strings differ by at most two symbol changes.

An interesting related problem is thus to discover Gray codes for grand Motzkin paths and grand Dyck paths with air pockets and their relatives. It is worth noting that there is no 1-Gray code for grand Dyck paths or grand Motzkin paths with air pockets. For example, in such a path, changing an up-step would require at least a compensating change to a down-step or a horizontal step to preserve the ending point on the \(x\)-axis. The same holds when updating a down-step or a horizontal step. Thus, at least two symbol changes are needed to reach another valid path. For simple grand Dyck paths with downstep restricted to \(k=1\), each such path can be represented by a combination with \(n\) 1s (representing up-steps) and \(n\) 0s (representing down-steps) among \(2n\) total steps. Several algorithms have been proposed to generate combinations [17], [19]–[24]. The weight of a binary string \(\alpha\), denoted by \(|\alpha|\), is defined as the number of 1s it contains. The BRGC listing can be used to create a 2-Gray code for combinations. The Gray code is created by filtering the BRGC, which retains only strings in the listing with weight \(k\), and is referred to as the revolving door Gray code for combinations. For example, filtering the BRGC listing in (1 ) gives the following 2-Gray code for combinations with \(n=5\) and \(k=2\): \[\label{eq:RevolvingDoor42}\nonumber \begin{align} 00011, 00110, 00101, 01100, 01010, 01001, 11000, 10100, 10010, 10001. \end{align}\tag{2}\] For more information about Gray codes induced by the BRGC, see [25] and [26]. Several algorithms have also been proposed to generate grand Motzkin paths with downstep restricted to \(k=1\), with constructions based on ECO methods or recursive decompositions [27], [28]. Baril et al. [2]–[4] first introduced grand Dyck paths with air pockets and provided generating functions of grand Dyck paths under various constraints [4], [29]–[32]. Subsequent work by Baril and Kirgizov [31] established bijections to pattern avoiding Dyck paths, and Baril et al. explored several variants of grand Motzkin paths [29], [31], [33]–[40], but no Gray codes have been discovered for them. This paper thus provides the first known 2-Gray code for both grand Motzkin paths and grand Dyck paths with air pockets. Since there is no 1-Gray code for grand Motzkin paths or grand Dyck paths with air pockets, our Gray codes are optimal.

The rest of the paper is outlined as follows. In Section 2, we describe a three-stage algorithm for generating a 2-Gray code for grand Motzkin paths with air pockets. Then in Section 3, we extend our algorithm to generate a 2-Gray code for grand Dyck paths with air pockets. We present enumeration formulae for grand Motzkin paths and grand Dyck paths with air pockets and prove their correctness in Section 4.

2 Generating grand Motzkin paths with air pockets↩︎

In this section, we describe a three-stage algorithm for generating a 2-Gray code for grand Motzkin paths with air pockets. We will discuss extending this algorithm to generate a 2-Gray code for grand Dyck paths with air pockets in the next section. The construction of the Gray code for grand Motzkin paths with air pockets involves the following three stages:

1. For a grand Motzkin path with \(d\) down-steps, first generate a Gray code for binary strings \(q = q_1 q_2 \cdots q_n\) of length \(n\) and weight \(d\). Here, \(q_i = 1\) indicates that position \(i\) is a down-step, and \(q_i = 0\) indicates that position \(i\) is an up-step or a horizontal step;

2. Given a string \(q = q_1 q_2 \cdots q_n\) with weight \(d\) from the first stage, generate a Gray code for binary strings \(r = r_1 r_2 \cdots r_{n-d}\), where \(r_i = 1\) indicates that the \(i\)-th position in \(q\) with \(q_j = 0\) corresponds to an up-step, and \(r_i = 0\) indicates a horizontal step;

3. Given the strings \(q\) and \(r\) from the first and second stages, compute the total number of up-steps, denoted by \(s\), which is equal to the weight of \(r\). Then, generate a Gray code to distribute the integer \(s\) across the positions where \(q_i = 1\) (i.e., the down-steps). Each down-step receives a positive integer \(t \geq 1\), and the sum of these \(d\) values must equal \(s\).

Finally, we combine these listings to construct a 2-Gray code for grand Motzkin paths with air pockets. For example, consider the grand Motzkin path with air pockets as shown in Figure 2, which can be represented by the tuple \(m = (-2, 1, 1, 1, 0, -2, 1, 1, 1, -1, 0, -1)\). Then, \(q = 100001000101\) and \(r = 11101110\). The total number of up-steps is six, and thus \(s = 6\) which equals the weight of \(r\). We distribute the integer \(s=6\) across the four down-step positions: two to the first and sixth positions of \(m\) (resulting in \(-2\)), and one to the tenth and twelfth positions of \(m\) (resulting in \(-1\)). In the following subsections, we detail the procedure for generating Gray codes for the combinatorial objects in each stage of constructing grand Motzkin paths with air pockets.

2.1 Stage 1: Generating fixed weight Fibonacci words↩︎

Given \(d\) down-steps in a grand Motzkin path with air pockets, the first stage of our algorithm generates a 2-Gray code for binary strings \(q\), where \(q_i = 1\) indicates that position \(i\) is a down-step, and \(q_i = 0\) indicates an up-step or a horizontal step. Since grand Motzkin paths with air pockets have no consecutive down-steps, the string \(q\) contains no consecutive 1s. A Fibonacci word of order \(p\), weight \(k\), and length \(n\) is a binary string of length \(n\) with weight \(k\) that avoids \(p\) consecutive 1s. When \(p = 2\), the set of Fibonacci words of weight \(k\) and length \(n\) corresponds to the set of binary strings of weight \(k\) with no consecutive 1s, which matches the set of strings \(q\) in stage 1 when we set \(k = d\). In [41]–[43], Hassler et al. developed efficient algorithms to generate greedy Gray codes for Fibonacci words of length \(n\), order \(p\), and weight \(k\). Their recursive and greedy implementations generate each Fibonacci word in constant amortized time using \(O(n^2)\) memory. The algorithm can be described recursively as follows when \(p=2\) and \(k=d\):

Start with \((10)^d 0^{n-2d}\). Greedily swap the leftmost possible \(1\) with the leftmost possible \(0\) before the next 1 and after the previous 1 (if there are any) such that the resulting string has not appeared before.

Let \(\mathcal{F}_d(n)\) denote the Gray code listing of Fibonacci words of length \(n\), order \(p=2\), and weight \(k=d\) generated by the algorithm in [41]–[43]. For example, the algorithm generates the following listing \(\mathcal{F}_2(7)\) for Fibonacci words of weight \(k=d=2\), length \(n=7\), and order \(p=2\):

This listing \(\mathcal{F}_2(7)\) corresponds to all possible arrangements of down-steps in a grand Motzkin path with air pockets for \(n = 7\) and \(d = 2\).

We then define \(\mathcal{F}(n)\) as the listing produced by concatenating the listings \(\mathcal{F}_d(n)\) for \(d\) ranging from \(\lfloor \frac{n}{2} \rfloor\) down to 1. However, we reverse each string in \(\mathcal{F}_d(n)\) individually (i.e., take its mirror image) when \(d\) is even. We also use the notation \(\mathcal{S}^{R}\) to refer to the listing obtained by reversing each string in a listing \(\mathcal{S}\). For example, \((001, 200, 010)^R = (100, 002, 010)\). When \(n = 7\), we have \[\begin{align} \mathcal{F}_3(7) &= 1010100, 1010010, 1001010, 0101010, 0101001, 1001001, 1010001, \\ & \;\;\;\; 1000101, 0100101, 0010101;\\ \mathcal{F}_2(7)^{R} &= 0000101, 0001001, 0001010, 0010010, 0010001, 0010100, 0100100, 0100001, \\ &= 0100010, 0101000, 1001000, 1000001, 1000010, 1000100, 1010000;\\ \mathcal{F}_1(7) &= 1000000, 0100000, 0010000, 0001000, 0000100, 0000010, 0000001. \end{align}\] Thus, \(\mathcal{F}(7)\) is as follows:

2.2 Stage 2: Generating binary strings with minimum weight↩︎

In the second stage of our algorithm, we generate a 2-Gray code for the up-steps and horizontal steps, corresponding to the positions in \(q\) where \(q_i = 0\). If a grand Motzkin path has \(d\) down-steps (i.e., \(d\) 1s in \(q\)), it must have at least \(d\) up-steps to return to the \(x\)-axis. Then when we represent an up-step as 1 and a horizontal step as 0, the set of up-steps and horizontal steps in a grand Motzkin path with air pockets and \(d\) down-steps corresponds to the set of binary strings \(r\) of length \(n-d\) with at least \(d\) 1s.

Given \(d\) down-steps from the first stage, the second stage generates a 2-Gray code for the set of binary strings \(r\) with at least \(d\) 1s. There are many algorithms that generate 2-Gray codes for binary strings with at least \(d\) 1s [17], [18], [21], [24]. For example, Sawada et al. [25], [26] extend the binary reflected Gray code algorithm to generate 2-Gray codes for flip-swap languages. A flip-swap language with respect to 0 is a set \(S\) of binary strings of length \(n\) such that \(S \cup {1^n}\) is closed under two operations (when applicable): (1) flipping the leftmost 0, and (2) swapping the leftmost 0 with the bit to its right.

Thus, we can use the binary reflected Gray code algorithm from [25], [26] to generate a 2-Gray code for the set of binary strings \(r\) with at least \(d\) 1s. For example, the algorithm generates the following 2-Gray code for binary strings of length 5 with at least two 1s:

Let \(\mathcal{B}_d(t)\) denote the listing of strings of \(r\) for grand Motzkin path with air pockets of length \(t\) with \(d\) down-steps generated by the algorithm in [25], [26].

2.3 Stage 3: Generating integer compositions↩︎

The last stage of our algorithm involves generating all possible combinations of the \(d\) down-step positions. An integer composition of a positive integer \(s\) is a sequence \(a_1, a_2, \ldots, a_k\) of positive integers such that \(a_1 + a_2 + \cdots + a_k = s\). In other words, an integer composition can be considered as an ordered collection of positive integers that sum to \(s\). Each term \(a_i\) in the sequence is called a part. For example, the eight integer compositions of \(s = 4\) are: \[\label{list:composition} 4, \;\;1 +3, \;\;2 +2, \;\;3 +1, \;\;1 +1 +2, \;\;1 +2 +1, \;\;2 +1+1, \;\;1 +1 +1 +1.\tag{3}\] Suppose that in stages one and two of our algorithm, we are given \(d\) down-steps and \(u\) up-steps. Then, in order for the grand Motzkin path to land on the \(x\)-axis, the \(d\) down-steps must add up to \(u\), which corresponds to all possible integer compositions of \(u\) with \(d\) parts.

We adopt a similar idea proposed in [44] and introduce a shorthand binary representation to represent integer compositions. In our proposed shorthand binary representation for integer compositions, each integer composition of \(s\) is represented by a binary string of length \(s-1\). Each part \(a_k\) of an integer composition is represented by the substring \(0^{|a_k|-1}1\), except for the last part, which is represented by \(0^{|a_k|-1}\), and we concatenate all parts together to represent the integer composition. As an example, the eight integer compositions of the integer \(s=4\) in (3 ) can be represented by the following binary strings under our shorthand binary representation:

Integer compositions of \(s\) with \(k\) parts can thus be represented by binary strings of length \(s-1\) with weight \(k-1\).

A Gray code is said to be homogeneous when the bits between the swapped 0 and 1 are all 0s. We now prove that a homogeneous 2-Gray code for integer compositions under our shorthand binary representation corresponds to a 2-Gray code for integer compositions under the standard integer representation.

There are many algorithms that generate homogeneous 2-Gray codes for binary strings of length \(n\) with \(k\) 1s. We again adopt the algorithm in [41]–[43] to generate a homogeneous 2-Gray code for shorthand binary representations of integer compositions. For example, the algorithm generates the following listing when \(n=7\) and \(k=2\).

The corresponding 2-Gray code for integer compositions are

The changes on each consecutive integer partitions has been underlined. Let \(\mathcal{I}_d(s)\) denote the listing of integer compositions of \(s\) with \(d\) parts under the standard integer representation, generated by the algorithm in [41]–[43].

2.4 Assembling the listings↩︎

In previous subsections, we discussed efficient constructions for 2-Gray codes for the sequences \(\mathcal{F}(n)\), \(\mathcal{B}_d(t)\), and \(\mathcal{I}_d(s)\). This subsection describes how to concatenate these listings to produce a 2-Gray code for grand Motzkin paths with air pockets. The rank of a string is its position in the generated sequence, starting from 1. We also use the notation \(\mathcal{S}^{-1}\) to refer to the listing obtained by reversing a listing \(\mathcal{S}\). Similarly, \(\mathcal{S}^{-k}\) represents the listing obtained by reversing the listing \(\mathcal{S}\) for \(k\) times. Thus, when \(k\) is even \(\mathcal{S}^{-k} = \mathcal{S}\), and when \(k\) is odd \(\mathcal{S}^{-k}=\mathcal{S}^{-1}\). The construction involves the following steps:

1. Generate the strings in \(\mathcal{F}(n)\);

2. For each string \(w\) in \(\mathcal{F}(n)\), let \(d\) be the number of 1s in \(w\). Generate the strings in \(\mathcal{B}_d(n-d)\). If the rank of \(w\) in \(\mathcal{F}(n)\) is odd, for each \(v\) in \(\mathcal{B}_d(n-d)\), produce a string \(\ell\) by replacing the 0s in \(w\) with the bits in \(v\) and the 1s in \(w\) with the symbol D. If the rank of \(w\) in \(\mathcal{F}(n)\) is even, reverse the whole listing \(\mathcal{B}_d(n-d)\), that is \(\mathcal{B}_d(n-d)^{-1}\); then produce \(\ell\) similarly. For the even-rank case, permute the symbols of each string in the same way in the listing so that the first string of \(\mathcal{B}_d(n-d)^{-1}\) matches the last string generated in the previous sublisting;

3. For each \(\ell\) produced, let \(s\) be the number of 1s in \(v\). Generate the listing \(\mathcal{I}_d(s)\). If the rank of \(\ell\) is odd, replace the Ds in \(\ell\) with the integer compositions from \(\mathcal{I}_d(s)\). If the rank of \(\ell\) is even, reverse each integer composition in \(\mathcal{I}_d(s)\) individually, that is \(\mathcal{I}_d(s)^R\), and replace Ds with the integer compositions from \(\mathcal{I}_d(s)^R\).

As an example, suppose we want to generate a Gray code for grand Motzkin paths with air pockets with \(n=5\). We first generate the strings in \(\mathcal{F}(5)\): \[\begin{align} \mathcal{F}(5) &= \mathcal{F}_2(5) \cdot \mathcal{F}_1(5)^{R} \\ &= 10100, 10010, 01010, 01001, 10001, 00101, 00001, 00010, 00100, 01000, 10000. \end{align}\] Then, in the second step, for each string \(w\) in \(\mathcal{F}(5)\), we replace the 1s with Ds and the 0s with strings from \(\mathcal{B}_d(n-d)\) or its reverse, depending on the parity of its rank. \[\begin{align} \mathcal{B}_2(3) &= 111, 011, 101, 110;\\ \mathcal{B}_1(4) &= 1111 ,0111 ,0011 ,1011 ,1001 ,0001 ,0101 ,1101 ,1100 ,0100 ,1000, 1010,\\ & \;\;\;\; 0010 ,0110 ,1110;\\ \mathcal{B}_2(3)^{-1} &= 110, 101, 011, 111;\\ \mathcal{B}_1(4)^{-1} &= 1110 ,0110 ,0010 ,1010 ,1000 ,0100 ,1100 ,1101 ,0101 ,0001 ,1001 ,1011, \\ & \;\;\;\; 0011 ,0111 ,1111. \end{align}\]

There are many ways to permute the symbols of each string in the listing to ensure that the first string of \(\mathcal{B}_d(n-d)^{-1}\) matches the last string generated in the previous sublisting. We maintain a linked list \(m\) that serves as an index mapping for non-down-step positions in the string \(w\) during step two of the Gray code concatenation for grand Motzkin paths. It is initialized as the sorted list of positions where \(w\) has 0s, guiding where bits from \(v\) (in \(\mathcal{B}_d(n-d)\)) are inserted to form \(\ell\), with D placed at 1s in \(w\). When transitioning to the next \(w'\), \(m\) is updated by replacing the entry for the position turning from 0 to 1 with the position turning from 1 to 0; additionally, if a down-step is replaced by an up-step or horizontal step (adding a new non-down-step position), the new position is inserted at the beginning of \(m\), and all subsequent indices are incremented by one. Then each string \(w\) in \(\mathcal{F}(5)\) becomes the following listings: \[\begin{align} 10100, m=\{2, 4, 5\} &= \text{D}1\text{D}11, \text{D}0\text{D}11, \text{D}1\text{D}01, \text{D}1\text{D}10;\\ 10010, m=\{2, 3, 5\} &= \text{D}11\text{D}0, \text{D}10\text{D}1, \text{D}01\text{D}1, \text{D}11\text{D}1;\\ 01010, m=\{1, 3, 5\}&= 1\text{D}1\text{D}1, 0\text{D}1\text{D}1, 1\text{D}0\text{D}1, 1\text{D}1\text{D}0;\\ 01001, m=\{1, 3, 4\} &= 1\text{D}10\text{D}, 1\text{D}01\text{D}, 0\text{D}11\text{D}, 1\text{D}11\text{D};\\ 10001, m=\{2, 3, 4\} &= \text{D}111\text{D}, \text{D}011\text{D}, \text{D}101\text{D}, \text{D}110\text{D};\\ 00101, m=\{2, 1, 4\} &= 11\text{D}0\text{D}, 01\text{D}1\text{D}, 10\text{D}1\text{D}, 11\text{D}1\text{D};\\ 00001, m=\{3, 2, 1, 4\} &= 1111\text{D}, 1101\text{D}, 1001\text{D}, 1011\text{D}, 0011\text{D}, 0001\text{D}, 0101\text{D}, 0111\text{D}, \\& \;\;\;\;0110\text{D}, 0100\text{D}, 0010\text{D}, 1010\text{D}, 1000\text{D}, 1100\text{D}, 1110\text{D};\\ 00010, m=\{3, 2, 1, 5\} &= 111\text{D}0, 110\text{D}0, 100\text{D}0, 101\text{D}0, 001\text{D}0, 010\text{D}0, 011\text{D}0, 011\text{D}1, \\& \;\;\;\; 010\text{D}1, 000\text{D}1, 001\text{D}1, 101\text{D}1, 100\text{D}1, 110\text{D}1, 111\text{D}1;\\ 00100, m=\{4, 2, 1, 5\} &= 11\text{D}11, 11\text{D}01, 10\text{D}01, 10\text{D}11, 00\text{D}11, 00\text{D}01, 01\text{D}01, 01\text{D}11, \\& \;\;\;\; 01\text{D}10, 01\text{D}00, 00\text{D}10, 10\text{D}10, 10\text{D}00, 11\text{D}00, 11\text{D}10;\\ 01000, m=\{4, 3, 1, 5\} &= 1\text{D}110, 1\text{D}100, 1\text{D}000, 1\text{D}010, 0\text{D}010, 0\text{D}100, 0\text{D}110, 0\text{D}111, \\& \;\;\;\; 0\text{D}101, 0\text{D}001, 0\text{D}011, 1\text{D}011, 1\text{D}001, 1\text{D}101, 1\text{D}111;\\ 10000, m=\{4, 3, 2, 5\} &= \text{D}1111, \text{D}1101, \text{D}1001, \text{D}1011, \text{D}0011, \text{D}0001, \text{D}0101, \text{D}0111, \\& \;\;\;\; \text{D}0110, \text{D}0100, \text{D}0010, \text{D}1010, \text{D}1000, \text{D}1100, \text{D}1110. \end{align}\]

In the third step, for each string generated in the second step, we replace the Ds with the parts obtained from the integer compositions in \(\mathcal{I}_d(s)\) or its mirror image, depending on the parity of its rank. For example, \(\mathcal{I}_2(3) = (1+2, 2+1)\) and its mirror image is \((2+1, 1+2)\). Note that \(\mathcal{I}_1(s)\) and its mirror image are identical (both contain only \(s\)), and \(\mathcal{I}_2(2)\) and its mirror image are both \((1+1)\). We also add the special string \((0, 0, \ldots, 0)\) between the first pair of consecutive strings that both have only one single up-step to ensure the listing includes all grand Motzkin paths with air pockets. Each grand Motzkin path is represented using a compact representation, where a path \((a_1, a_2, \dots, a_n)\) is encoded as a string \(b_1 b_2 \cdots b_n\) of length \(n\) with \(b_i = a_i\) if \(a_i \geq 0\) (up-step or horizontal step), and \(b_i\) represented as \(\overline{|a_i|}\) if \(a_i < 0\) (down-step).

Pseudocode of the algorithm is given by Algorithm 3. It follows our three-stage algorithm using three nested loops to enumerate strings in \(\mathcal{F}(n)\), \(\mathcal{B}_d(n-d)\), and \(\mathcal{I}_d(s)\), which encode the positions of down-steps, the assignments of up-steps and horizontal steps, and the magnitudes of down-steps, respectively. The algorithm maintains a linked list \(m\), which serves as an index mapping for non-down-step positions during the second stage to ensure Gray code properties in the concatenation of \(\mathcal{B}_d(n-d)\) listings. It also tracks the last generated string \(\alpha'\) and identifies the positions \(x\) and \(y\) where the current string \(\alpha\) differs from \(\alpha'\) (i.e., \(\alpha_x \neq \alpha'_x\) and \(\alpha_y \neq \alpha'_y\)) to update \(m\) by swapping these indices. When reducing the number of down-steps, the algorithm updates \(m\) by prepending the position of the removed down-step position as the first element. The function DecodeMotzkin is then used to decode the grand Motzkin path with air pockets when given \(\alpha \in \mathcal{F}(n)\), \(\beta \in \mathcal{B}_d(n-d)\), the linked list \(m\), and \(\gamma \in \mathcal{I}_d(s)\). For simplicity, the pseudocode does not include details on handling the special string \((0, 0, \dots, 0)\). A complete Python implementation of the algorithm is given in Appendix A.

3 Generating grand Dyck paths with air pockets↩︎

A grand Dyck path with air pockets is a grand Motzkin path with air pockets that uses no horizontal steps. To generate grand Dyck paths with air pockets, we simplify Algorithm 3 by omitting the second stage, which assigns horizontal steps. After selecting \(d\) down-step positions, the remaining \(n-d\) positions are assigned up-steps, and the value \(n-d\) (the number of up-steps) is distributed into the \(d\) down-step magnitudes. Pseudocode of the algorithm for grand Dyck paths with air pockets is given by Algorithm 4. It eliminates the nested loop for enumerating strings in \(\mathcal{B}_d(n-d)\) and the linked list \(m\) for index mapping. The function DecodeDyck constructs the grand Dyck path with air pockets from inputs \(\alpha \in \mathcal{F}_{d}(n)\), representing down-step positions, and \(\gamma \in \mathcal{I}_{d}(s)\), representing down-step magnitudes. For example, Algorithm 4 generates the following grand Dyck paths with air pockets for \(n = 5\):

A complete Python implementation is provided in Appendix A.

4 Enumeration↩︎

This section provides the enumeration formulae for grand Motzkin paths with air pockets and grand Dyck paths with air pockets.

A complete Python implementation to compute the closed-form formula for the number of grand Motzkin paths and grand Dyck paths with air pockets is given in Appendix B.

Acknowledgments.↩︎

This research is supported by the Macao Polytechnic University research grant (RP/FCA-02/2022 and fca.6a16.fe65.7). The research of Lin Chen is supported by the National Natural Science Foundation of China under Grant No. 62172455.

5 Python code to generate grand Motzkin paths and grand Dyck paths with air pockets↩︎

from math import ceil

class IntComp:
    def __init__(self, n, k, no_consecutive=False):
        self.n = n
        self.k = k
        self.nc = no_consecutive

        if not no_consecutive:
            self.s = [i for i in range(k+1)]
            self.c = [1 for _ in range(k+1)]
            self.d = [0 for _ in range(k+1)]
            self.p = [[0 for _ in range(n+1)] for _ in range(k+1)]
            for i in range(1, k+1):
                self.p[i][i] = 1
            self.s += [n+1]

        else:
            self.s = [2*i-1 for i in range(k+1)]
            self.c = [1 for _ in range(k+1)]
            self.d = [0 for _ in range(k+1)]
            self.p = [[0 for _ in range(n+1)] for _ in range(2*k+1)]
            for i in range(1, k+1):
                self.p[2*i-1][2*i-1] = 1
            self.s[0] = -1
            self.s += [n+2]

        self.idx = []

    def next(self):
        for i in range(1, self.k+1):
            if self.d[i]:
                if self.s[i] == i and not self.nc or self.s[i] == 2*i-1 and self.nc:
                    self.d[i] = 0
                else:
                    j = max(self.s[i-1]+1, i) if not self.nc else max(self.s[i-1]+2, 2*i-1)

                    self.idx = [self.s[i]-1, j-1]
                    self.s[i] = j
                    self.p[i][j] = self.c[i]
                    for t in range(1, i):
                        self.d[t] = 1
                        self.c[t] += 1
                        self.p[t][self.s[t]] = self.c[t]
                    return True

            for j in range(self.s[i]+1, self.s[i+1] - (0 if not self.nc else 1)):
                if self.p[i][j] != self.c[i]:

                    self.idx = [self.s[i]-1, j-1]
                    self.s[i] = j
                    self.p[i][j] = self.c[i]
                    for t in range(1, i):
                        self.d[t] = 1
                        self.c[t] += 1
                        self.p[t][self.s[t]] = self.c[t]
                    return True
        return False

    def output(self):
        res = []
        j = 1
        for i in range(1, self.n+1):
            if self.s[j] != i:
                res += [0]
            else:
                res += [1]
                j += 1
        return res

def brgc_k(n, k, d):
    a = [0]*(n+1)
    a[n] = 1
    # m = 1

    def Gen(t, z, w):
        if t < 1 or t + w <= k:
            if t < 1:
                yield a[1:n+1], w
            else:
                yield [1]*t+a[t+1:n+1], w+t

        else:
            if not (z                 a[t] = 1
                yield from Gen(t - 1, 0, w + 1)
                a[t] = 0
                yield from Gen(t - 1, 1, w)
            else:
                a[t] = 0
                yield from Gen(t - 1, 0, w)
                a[t] = 1
                yield from Gen(t - 1, 1, w + 1)
                a[t] = 0

    yield from Gen(n, 1 - d, 0)

def grand_dyck(n):
    d1, d2 = 1, 1
    for u in range(n-1, ceil(n/2)-1, -1):
        ic1 = IntComp(n, n-u, True)
        while True:
            a = ic1.output()
            ic2 = IntComp(u-1, n-u-1)
            while True:
                b = ic2.output()
                yield a, d1, b, d2
                if not ic2.next():
                    break
            d2 = 1 - d2
            if not ic1.next():
                break
        d1 = 1 - d1

def decode_gd(a, d1, b, d2):
    res = []
    down_list = []
    if d2:
        down = 0
        for i in b:
            down -= 1
            if i == 1:
                down_list.append(down)
                down = 0
        down -= 1
        down_list.append(down)
    else:
        down = -1
        for i in reversed(b):
            if i == 1:
                down_list.append(down)
                down = 0
            down -= 1
        down_list.append(down)

    idx = 0
    for i in a if d1 else reversed(a):
        if i == 0:
            res += [1]
        else:
            res += [down_list[idx]]
            idx += 1
    return res

def grand_motzkin(n):
    du = 1
    dd = 1
    di = 1
    u_ = 0
    s_uh = None

    for uh in range(ceil(n/2), n):
        d = n - uh
        d_dist_ic = IntComp(n, d, True)
        while True:
            d_dist = d_dist_ic.output()

            if s_uh is None:
                s_uh = []
                for i in range(len(d_dist)):
                    if d_dist[i] == 0:
                        s_uh.append(i)
            elif len(d_dist_ic.idx) > 0:
                for i in range(len(s_uh)):
                    if s_uh[i] == d_dist_ic.idx[1] and dd == 1 or s_uh[i] == n-d_dist_ic.idx[1]-1 and dd == 0:
                        s_uh[i] = d_dist_ic.idx[0] if dd else n-d_dist_ic.idx[0]-1

            uh_dist_brgc = brgc_k(uh, d, du)

            for uh_dist, u in uh_dist_brgc:

                # insert 0*n
                if u_ == 1 and u == 1:
                    yield -1, n, -1, -1, -1, -1
                    u_ = -1
                u_ = u if u_ != -1 else u_

                d_comp_ic = IntComp(u-1, d-1)
                while True:
                    d_comp = d_comp_ic.output()
                    yield d_dist, dd, uh_dist, s_uh, d_comp, di

                    if not d_comp_ic.next():
                        break
                di = 1 - di

            du = uh_dist[-1]

            if not d_dist_ic.next():
                break
        dd = 1 - dd
        s_uh = [2*d - 2 if dd == 1 else n - 2*d + 1] + s_uh

def decode_gm(d_dist, dd, uh_dist, s_uh, d_comp, di):
    if d_dist == -1:
        return [0]*dd
    res = []
    down_list = []
    if di:
        down = 0
        for i in d_comp:
            down -= 1
            if i == 1:
                down_list.append(down)
                down = 0
        down -= 1
        down_list.append(down)
    else:
        down = -1
        for i in reversed(d_comp):
            if i == 1:
                down_list.append(down)
                down = 0
            down -= 1
        down_list.append(down)

    idx_i = 0
    d_dist = d_dist if dd else list(reversed(d_dist))

    for i in range(len(d_dist)):
        if d_dist[i] == 0:
            res += [uh_dist[s_uh.index(i)]]
        else:
            res += [down_list[idx_i]]
            idx_i += 1
    return res

if __name__ == '__main__':
    print('Input n: ')
    n = int(input())
    print('allow horizontal-steps? 1 yes, 0 no')
    is_gmp = int(input())

    is_gmp = True if is_gmp == 1 else False
    gen_func = grand_motzkin if is_gmp else grand_dyck
    decode_func = decode_gm if is_gmp else decode_gd

    cnt = 0
    for ap in gen_func(n):
        cnt += 1
        curr = decode_func(*ap)
        print('
    print('Total: 

6 Python code to enumerate the numbers of grand Motzkin paths and grand Dyck paths with air pockets↩︎

import math

def comb(n, k):
    try:
        return math.comb(n, k)
    except ValueError:
        return 0

gdp = lambda n: sum([comb(n - k + 1, k) * comb(n - k - 1, k - 1) for k in range(1, n // 2 + 1)])
gmp = lambda n: sum(
    [comb(n - k + 1, k) * sum([comb(n - k, n - k - i) * comb(n - k - i - 1, k - 1) for i in range(n - 2 + 1)]) for k in range(1, n // 2 + 1)]) + 1

if __name__ == "__main__":
    print("Grand Dyck paths or Grand Motzkin paths with air pockets? (1/2)")
    this_type = input()
    assert this_type in ["1", "2"]
    if this_type == "1":
        func = gdp
        path_type = "grand Dyck paths"
    else:
        func = gmp
        path_type = "grand Motzkin paths"

    print("Enter n:")
    n = int(input())
    result = func(n)
    print(f"the number of {path_type} with air pockets is: {result}")

7 Proofs of Lemma 11 and Theorems 1, 3 and 6↩︎

References↩︎