### 3. THE SIGNED AREA ENUMERATION

It is known (see e.g. William Chambers' book [3]) that the determinant of the matrix $I_q - zH_q$ satisfies

$$ \det(I_q - zH_q) = \left( \sum_{n=0}^{[q/2]} (-1)^n Z(n) z^{2n} \right) - 2(\cos(qk_x) + \cos(qk_y))z^q, $$

where the $Z(n)$'s are independent of $k_x$ and $k_y$ and $Z(0) = 1$. Christian Kreft [12] was able to rewrite $Z(n)$ in a closed form as trigonometric multiple nested sums

$$ Z(n) = \sum_{k_1=1}^{q-2n+2} \sum_{k_2=1}^{k_1} \cdots \sum_{k_n=1}^{k_{n-1}} \prod_{j=1}^{n} s_{k_j+2n-2j}, \qquad (3.1) $$

where

$$ s_k = 4 \sin^2(\pi k p / q) = 2 - Q^k - Q^{-k}. \qquad (3.2) $$

We call $s_k$ the spectral function of the model. This is the starting point for the signed area enumeration. We give here a summary of the procedure, more details can be found in [14, 16]. First introduce the coefficients $b(n)$ via

$$ -\log \left( \sum_{n=0}^{[q/2]} (-1)^n Z(n) z^{2n} \right) = \sum_{n=1}^{\infty} b(n) z^{2n}. \qquad (3.3) $$

The $b(n)$ are related to the desired traces. Start by noting that

$$ \mathbf{Tr} H_q^{2n} = \frac{1}{q} \mathrm{tr} H_q^{2n} \text{ for } n < q. $$

Indeed, one has $\mathrm{tr} u^i v^j = q \delta_{i,0} \delta_{j,0}$ for $i, j < q$ and so the values of the Casimir $k_x, k_y$ do not appear, making the integration over them in (2.3) trivial. Then the identity

$$ -\log \det(I_q - zH_q) = -\mathrm{tr} \log(I_q - zH_q) = \sum_{n=1}^{\infty} \frac{z^n}{n} \mathrm{tr} H_q^n = \sum_{n=1}^{[q/2]} b(n)z^{2n} + O(z^q) $$

implies that the quantum trace (2.3) is proportional to $b(n)$ for $n < q$

$$ \mathbf{Tr} H_q^{2n} = \frac{2n}{q} b(n). $$

Now, by keeping $q$ as a free parameter and extending it to arbitrarily big values, the quantum trace can be calculated for all $n$.

Note that the term of order $z^n$ in $\det(I_q - zH_q)$ is $-(z^n/n)\mathrm{tr} H_q^n$ plus terms involving products of traces, $\mathrm{tr} H_q^{n_1} \mathrm{tr} H_q^{n_2} \cdots$ with $n_1+n_2+\cdots=n$. As each trace $\mathrm{tr} H_q^{n_i}$ contributes an overall factor $q$, $b(n)$ can also be obtained as the order $q$ term in $Z(n)$, ignoring terms of higher order $q^2, \dots, q^n$. Since each sum in Formula (3.1) contributes a factor of $q$, we get the following explicit expression for $b(n)$:

$$ b(n) = \sum_{j=1}^{n} \sum_{\substack{l_1, l_2, \dots, l_j \\ \text{composition of } n}} c(l_1, l_2, \dots, l_j) \sum_{k=1}^{q-j+1} s_{k+j-1}^{l_j} \cdots s_{k+1}^{l_2} s_k^{l_1}, \qquad (3.4) $$

$$ \text{where } c(l_1, l_2, \dots, l_j) := \frac{\binom{l_1+l_2}{l_1}}{l_1+l_2} \binom{l_2+l_3}{l_2} \cdots \binom{l_{j-1}+l_j}{l_{j-1}} \frac{\binom{l_{j-1}+l_j}{l_{j-1}}}{l_{j-1}+l_j}. $$
Here, the coefficients $c(l_1, l_2, \dots, l_j)$ are labelled by the compositions $l_1, l_2, \dots, l_j$ of $n$, i.e. the ordered partitions of $n$ (thus, there are $2^{n-1}$ compositions of $n$, for example $3 = 3, 2 + 1, 1 + 2, 1 + 1 + 1$). Note that the expression for $c(l_1, l_2, \dots, l_j)$ is closely related to the enumeration of Dyck paths (up to a factor $l_1$); see Christian Krattenthaler's article [11, p. 516]. We have further elaborated on this relation in [6].

Putting everything together, we get

$$ \mathrm{Tr} H_q^{2n} = \sum_{j=1}^{n} \sum_{\substack{l_1, l_2, \dots, l_j \\ \text{composition of } n}} c(l_1, l_2, \dots, l_j) \frac{2n}{q} \sum_{k=1}^{q-j+1} s_{k+j-1}^{l_j} \cdots s_{k+1}^{l_2} s_k^{l_1}. $$

What is more, the trigonometric sums involved in this formula can be computed, keeping $q$ as a free parameter. Finally, returning to (2.4) (with $N = 2n$) the desired number of closed walks of given area is given by the following theorem.

**Theorem 3.1.** The number of closed walks of length $2n$ enclosing a given signed area $A$ is

$$ C_{2n}(A) = 2n \times \sum_{j=1}^{n} \sum_{\substack{l_1, l_2, \dots, l_j \\ \text{composition of } n}} \frac{\binom{l_1+l_2}{l_1}}{l_1+l_2} \binom{l_2+l_3}{l_2} \binom{l_2+l_3}{l_2+l_3} \cdots \binom{l_{j-1}+l_j}{l_{j-1}} \binom{l_{j-1}+l_j}{l_{j-1}} \times \\ \sum_{k_3=0}^{2l_3} \sum_{k_4=0}^{2l_4} \cdots \sum_{k_j=0}^{2l_j} \prod_{i=3}^{j} \binom{2l_i}{k_i} \left( l_1 + A + \sum_{i=3}^{j} (i-2)(k_i-l_i) \right) \left( l_2 - A - \sum_{i=3}^{j} (i-1)(k_i-l_i) \right). $$

This formula grows quickly in complexity since one has to sum over $2^n - 1$ compositions. Its complexity is analysed in more detail in the following proposition.

**Proposition 3.2.** The formula for $C_{2n}(A)$ in Theorem 3.1 involves asymptotically, up to some polynomial factor, $(4/(5 - \sqrt{17}))^n \approx 4.56^n$ summands.

*Proof.* This number of summands is given by

$$ r(n) := \sum_{j=1}^{n} \sum_{\substack{l_1, l_2, \dots, l_j \\ \text{composition of } n}} (2l_3 + 1)(2l_4 + 1) \cdots (2l_j + 1). $$

The sequence starts like $(r(n))_{n \ge 1} = (1, 2, 6, 24, 106, 480, 2186, 9968, 45466, \dots)$. Thus, $r(n)$ counts compositions of $n$ where each summand $l_i$ (for $i \ge 3$) can have $2l_i + 1$ colours. Let us consider first compositions of $n$ where each summand $l_i$ (for $i \ge 1$) can have $2l_i + 1$ colours; their generating function is

$$ S(z) = \frac{1}{1 - \sum_{i \ge 1} (2i + 1)z^i} = \frac{(z - 1)^2}{2z^2 - 5z + 1}. $$

This corresponds to the sequence A060801 in the On-line Encyclopedia of Integer Sequences. In our case, the $i \ge 3$ constraint modifies a little bit the generating function and one has to sum the compositions having 1 or 2 parts and those having 3 parts or more; one gets the following generating function

$$ R(z) = \sum_{n \ge 1} r_n z^n = \frac{z}{1-z} + \left(\frac{z}{1-z}\right)^2 + \left(\frac{z}{1-z}\right)^2 (S(z) - 1) \\ = \frac{z^2 - 4z + 1}{2z^2 - 5z + 1} \frac{z}{1-z}. $$
It entails $r(n) = 5r(n-1) - 2r(n-2) - 2$ (with $r(1) = 1$ and $r(2) = 2$); accordingly, $r(n)$ grows like $\phi^n$ with $\phi = 4/(5 - \sqrt{17})$, which is coherent with the fact that $1/\phi$ is the dominant pole of $R(z)$. In conclusion, our formula for $C_{2n}(A)$ involves in total asymptotically $\phi^n \approx 4.56^n$ summands (each leading additionally to a polynomial cost in $n$ for the product of all the binomials), which is still much less<fnref n="2" /> than the naive generation of all $\binom{2n}{n}^2$ closed walks of length $2n$, which would be of cost > $16^n/(\pi n)$. □

Note that it is in fact possible to compute $C_{2n}$ in polynomial time: Using the non-commutative relations (1.2), the expansion of $(u+v+u^{-1}+v^{-1})^{2n}$ simplifies a lot and in fact has $O(n^4)$ monomials $u^i v^j Q^k$. This gives an algorithm of complexity $O(n^6)$ to compute $C_{2n}(A)$. Thus, our formula (of exponential cost) in Theorem 3.1 is not the fastest way to compute $C_{2n}(A)$, but it has the benefit of being the first explicit formula (as far as we are aware of!).

Let us end this section with a probabilistic remark. In the limit of the elementary lattice size $a \to 0$ and the walk length $2n \to \infty$ with the scaling $na^2 = t$, walks converge to Brownian motion curves and we recover the continuum limit of a particle moving on the plane in a constant magnetic field. To implement this limit, we rescale the lattice cell area to $a^2$, which amounts to setting $A \to A/a^2$ in $C_{2n}(A)$. Numerical simulations then suggest the following conjecture.

**Conjecture 3.3.** The signed area of closed walks of length $2n$ converges, after rescaling, to the following distribution (for any $\alpha > 0$)

$$ \frac{2n C_{2n}(\alpha n)}{\binom{2n}{n}^2} \to \frac{\pi}{\cosh^2(\alpha \pi)}. $$

<figure><img src="image_74.png" /><figcaption>FIGURE 2. We conjecture that the distribution of the signed area asymptotically follows... not a Gaussian limit law (as it may be thought at first glance), but the $1/\cosh^2$ distribution of Paul Lévy. For small values of $A$, and $n$ up to 70, we checked numerically that the convergence gets better when $n$ increases.</figcaption></figure>

This conjecture is consistent with the law for the distribution of the signed area enclosed by a Brownian curve after a time $t$ (obtained by Paul Lévy in 1950; see [10, 13]). It can also be obtained directly in the continuum limit by considering the partition function of a quantum particle in a magnetic field with a Landau level energy spectrum.

<footnote n="2">²We thank one of the referees for drawing our attention to this point.</footnote>
4. EXCLUSION STATISTICS

The quantities $Z(n)$ and $b(n)$ introduced previously admit a statistical mechanical interpretation. Let us write the spectral function $s_k$ in (3.2) as $s_k = e^{-\beta\epsilon_k}$ ($\beta$ is the inverse temperature) and interpret is as the Boltzmann factor for a quantum 1-body spectrum $\epsilon_k$ labelled by an integer $k$. The structure of $Z(n)$ in (3.1) then precisely corresponds to an $n$-body partition function for a gas of particles with 1-body spectrum $\epsilon_k$ and exclusion statistics $g = 2$: The +2 shifts in the spectral function arguments ensure that no two particles can occupy adjacent quantum states. Exclusion statistics is, again, a purely quantum concept which describes the statistical mechanical properties of identical particles. Ordinary particles are either bosons ($g = 0$), which can occupy the same quantum state, or fermions ($g = 1$), which cannot occupy the same quantum state. We see that square-lattice walks map to systems with statistics beyond Fermi exclusion, in which particles can occupy neither the same state nor adjacent states. In a sense, each particle excludes two quantum states, thus $g = 2$. In general, for $g$-exclusion particles the $n$-body partition function (3.1) would become

$$Z(n) = \sum_{k_1=1}^{q-gn+g} \sum_{k_2=1}^{k_1} \cdots \sum_{k_n=1}^{k_{n-1}} s_{k_1+gn-g} s_{k_2+gn-2g} \cdots s_{k_{n-1}+g} s_{k_n}, \quad (4.1)$$

where one observes a shift $g$ instead of 2 in the arguments of the spectral function. In line with (3.3), (3.4) the associated $n$-th cluster coefficient can be shown to take the form

$$b(n) = \sum_{j=1}^{n} \sum_{\substack{l_1, l_2, \dots, l_j \\ g\text{-composition of } n}} c_g(l_1, l_2, \dots, l_j) \sum_{k=1}^{q-j+1} s_{k+j-1}^{l_j} \cdots s_{k+1}^{l_2} s_k^{l_1}, \quad (4.2)$$

where

$$c_g(l_1, l_2, \dots, l_j) := \frac{(l_1 + \dots + l_{g-1} - 1)!}{l_1! \dots l_{g-1}!} \prod_{i=1}^{j-g+1} \binom{l_i + \dots + l_{i+g-1} - 1}{l_{i+g-1}}.$$

In (4.2) one sums over all $g$-compositions of the integer $n$, obtained by inserting at will inside the usual compositions (i.e., the 2-compositions) no more than $g-2$ zeroes in succession. For example, for $n = 3$ and $g = 3$ one has 9 such 3-compositions:

$$3, 2 + 1, 1 + 2, 1 + 1 + 1, 2 + 0 + 1, 1 + 0 + 2, 1 + 0 + 1 + 1, 1 + 1 + 0 + 1, 1 + 0 + 1 + 0 + 1.$$

For general $g$ there are $g^{n-1}$ such $g$-compositions of the integer $n$ (see [9] for an analysis of these extended compositions, also called multicompositions).

One has reached the conclusion that the signed area enumeration for walks on the square lattice is described by a quantum gas of particles with statistical exclusion $g = 2$. To relate this explicitly to properties of the Hofstadter Hamiltonian itself, let us perform on the hopping lattice operators $u$ and $v$ the transformation

$$u \rightarrow -u \ v, \ v \rightarrow v,$$

which leave their own commutation relation invariant to get the new Hamiltonian

$$H = -u v - v^{-1}u^{-1} + v + v^{-1} \quad (4.3)$$

still describing the same walks but on a deformed lattice.
This new Hamiltonian (if one compares it with the initial Hamiltonian operator (2.1) of the Hofstadter model) has the advantage to lead to simpler matrix

$$ I_q - zH_q = \begin{pmatrix} 1 & -(1-Q)z & 0 & \cdots & 0 & 0 \\ -(1-\frac{1}{Q})z & 1 & -(1-Q^2)z & \cdots & 0 & 0 \\ 0 & -(1-\frac{1}{Q^2})z & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & -(1-Q^{q-1})z \\ 0 & 0 & 0 & \cdots & -(1-\frac{1}{Q^{q-1}})z & 1 \end{pmatrix}, \quad (4.4) $$

where we set $k_x = k_y = 0$ for simplicity (since, as we explained in Section 3, $k_x$ and $k_y$ do not appear in the counting formula). The Hofstadter spectral function (3.2) becomes

$$ s_k = (1 - Q^k)(1 - \frac{1}{Q^k}). $$

The matrix (4.4) is a particular case of the more general class of matrices having the following shape<fnref n="3" />

$$ I_q - zH_q = \begin{pmatrix} 1 & -f(1)z & 0 & \cdots & 0 & -g(q)z \\ -g(1)z & 1 & -f(2)z & \cdots & 0 & 0 \\ 0 & -g(2)z & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & -f(q-1)z \\ -f(q)z & 0 & 0 & \cdots & -g(q-1)z & 1 \end{pmatrix} \quad (4.5) $$

and associated spectral functions

$$ s_k = f(k)g(k), $$

which become the building blocks of the $Z(n)$'s in (3.1) (up to spurious “umklapp” terms, a name deriving from momentum periodicity effects on lattice quantum models, which disappear if $f(q)$ and $g(q)$ both vanish).

For statistics $g = 3$, the matrix (4.5) generalizes in a natural way to

$$ I_q - zH_q = \begin{pmatrix} 1 & -f(1)z & 0 & 0 & \cdots & 0 & -g(q-1)z & 0 \\ 0 & 1 & -f(2)z & 0 & \cdots & 0 & 0 & -g(q)z \\ -g(1)z & 0 & 1 & -f(3)z & \cdots & 0 & 0 & 0 \\ 0 & -g(2)z & 0 & 1 & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \cdots & 1 & -f(q-2)z & 0 \\ 0 & 0 & 0 & 0 & \cdots & 0 & 1 & -f(q-1)z \\ -f(q)z & 0 & 0 & 0 & \cdots & -g(q-2)z & 0 & 1 \end{pmatrix}, \quad (4.6) $$

that is, with an extra vanishing paradiagonal below the unity main diagonal, which is the manifestation of the stronger $g = 3$ exclusion.

<footnote n="3">³We hope that the reader will easily distinguish between too similar (but unrelated!) notations: the function $g(k)$ for the entries of the matrix $I_q - zH_q$, and the integer $g$ (the parameter of the exclusion model, a standard notation in the literature).</footnote>
The spectral function corresponding to this matrix is

$$s_k = g(k)f(k)f(k+1)$$

and the determinant det($I_q - zH_q$) assumes the form (4.1) with $g = 3$. For g-exclusion the generalization of (4.6) amounts to a Hamiltonian of the form

$$H = F(u)v + v^{1-g}G(u), \quad (4.7)$$

and $I - zH$ is then a matrix with $g-2$ vanishing paradiagonals below the main diagonal (here $q$ is left arbitrary but always understood to be larger than $g$). The spectral parameters of this matrix are

$$F(Q^k) = f(k), \quad G(Q^k) = g(k),$$

and the spectral function is

$$s_k = g(k)f(k)f(k+1)\dots f(k+g-2).$$

Clearly the Hofstadter Hamiltonian (4.3), which rewrites as $H = (1-u)v + v^{1-2}(1-u^{-1})$, is a particular case of (4.7) with $g=2$ and $F(u) = 1-u$, $G(u) = 1-u^{-1}$.

### 5. CHIRAL WALKS ON THE TRIANGULAR LATTICE

Let us illustrate this mechanism in the case of $g=3$ exclusion with the specific example of chiral walks on a triangular lattice. The three hopping operators $U, V$ and $W = QU^{-1}V^{-1}$ described in Figure 3 are such that $VU = Q^2UV$.

<figure><img src="image_75.png" /><figcaption>FIGURE 3. The three hopping operators $U, V$ and $W$ on the triangular lattice.</figcaption></figure>

The triangular lattice Hamiltonian is

$$H = U + V + W.$$

It generates walks composed of triangles either pointing up and winding in the counterclockwise direction, or pointing down and winding in the negative direction. In this sense, the walks are chiral. The factor $Q$ in the definition of $W$ and the factor $Q^2$ in the commutation of $U, V$ are chosen so that up-pointing (positive) triangles are assigned area +1. Figure 4 depicts some examples of chiral walks on the triangular lattice.
<figure><img src="image_76.png" /><figcaption>FIGURE 4. Examples of closed chiral walks on the triangular lattice.</figcaption></figure>

To bring $H$ to the exclusion form (4.7) one chooses the representation $U = -iuv$ and $V = iu^{-1}v$, with $u$ and $v$ as before, in which case $H$ rewrites as

$$H = i(-u + u^{-1})v + v^{-2}.$$

In this form, $H$ is indeed a Hamiltonian of the type (4.7) for $g = 3$ exclusion, with $F(u) = i(-u + u^{-1})$, $G(u) = 1$, spectral parameters

$$f(k) = -i(Q^k - \frac{1}{Q^k}), \quad g(k) = 1,$$

spectral function

$$s_k = g(k)f(k)f(k+1) = 4 \sin(2\pi pk/q) \sin\left(\frac{2\pi p(k+1)}{q}\right), \quad (5.1)$$

and matrix

$$I_q - zH_q = \begin{pmatrix}
1 & i(Q - \frac{1}{Q})z & 0 & 0 & \cdots & 0 & -z & 0 \\
0 & 1 & i(Q^2 - \frac{1}{Q^2})z & 0 & \cdots & 0 & 0 & -z \\
-z & 0 & 1 & i(Q^3 - \frac{1}{Q^3})z & \cdots & 0 & 0 & 0 \\
0 & -z & 0 & 1 & \cdots & 0 & 0 & 0 \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\
0 & 0 & 0 & 0 & \cdots & 1 & i(Q^{q-2} - \frac{1}{Q^{q-2}})z & 0 \\
0 & 0 & 0 & 0 & \cdots & 0 & 1 & i(Q^{q-1} - \frac{1}{Q^{q-1}})z \\
0 & 0 & 0 & 0 & \cdots & -z & 0 & 1
\end{pmatrix},$$

which is of the type (4.6) with a vanishing bottom-left entry. The non-Hermiticity of the triangular Hamiltonian, and thus of $I_q - zH_q$, is a consequence of the chiral nature of the walks.

The triangular signed area enumeration follows [14], yielding an expression similar to Theorem 3.1 with the trigonometric single sums appearing in (4.2) involving the triangular spectral function (5.1) and the sum done over all 3-compositions of the length of the triangular walks.
## 6. CONCLUSION

In conclusion, we have shown how tools from quantum and statistical physics allow for an explicit enumeration of closed walks of fixed length and signed area on planar lattices.

The enumeration formulae rely on an explicit sum over compositions, and their number of terms grows quickly with the length of the walk (although much less quickly than a brute-force counting formula). It would certainly be rewarding to rewrite it as a sum with a smaller number of terms. The use of symmetry on the lattice or alternative ways to write the generator of walks (Hamiltonian) may offer promise towards this goal. We leave this issue as well as other questions of interest to the lattice walk combinatorics community.

**Acknowledgments.** We thank the referees for their useful comments and suggestions, and Li Gan for a careful reading of the manuscript.

**Funding.** A.P. thanks the National Science Foundation for its support under grant NSF- PHY-2112729 and PSC-CUNY for its support under grants 65109-00 53 and 6D136-00 03.

## REFERENCES

[1] Jean Bellissard, Carlos J. Camacho, Armelle Barelli, and Francisco Claro. Exact random walk distributions using noncommutative geometry. *J. Phys. A, Math. Gen.*, 30(21):1707-1709, 1997.

[2] Timothy Budd. Winding of simple walks on the square lattice. *J. Comb. Theory Ser. A*, 172:105191, 2020.

[3] Williams G. Chambers. Linear-network model for magnetic breakdown in two dimensions. *Phys. Rev.*, 140(1A):A135, 1965.

[4] Alain Comtet, Jean Desbois, and Stéphane Ouvry. Winding of planar Brownian curves. *J. Phys. A: Math. Gen.*, 23(15):3563, 1990.

[5] Li Gan, Stéphane Ouvry, and Alexios P. Polychronakos. Algebraic area enumeration of random walks on the honeycomb lattice. *Phys. Rev. E*, 105(1):014112, 2022.

[6] Li Gan, Stéphane Ouvry, and Alexios P. Polychronakos. Combinatorics of generalized Dyck and Motzkin paths. *Phys. Rev. E*, 106(4):044123, 2022.

[7] Christophe Garban and José A Trujillo Ferreras. The expected area of the filled planar Brownian loop is $\pi/5$. *Comm. Math. Phys.*, 264(3):797-810, 2006.

[8] Douglas R. Hofstadter. Energy levels and wave functions of Bloch electrons in rational and irrational magnetic fields. *Phys. Rev. B*, 14(6):2239, 1976.

[9] Brian Hopkins and Stéphane Ouvry. Combinatorics of multicompositions. In *Combinatorial and Additive Number Theory, New York Number Theory Seminar*, pages 307-321. Springer, 2020.

[10] Dinkar C. Khandekar and Frederik W. Wiegel. Distribution of the area enclosed by a plane random walk. *J. Phys. A, Math. Gen.*, 21(10):1563-1566, 1988.

[11] Christian Krattenthaler. Permutations with restricted patterns and Dyck paths. *Adv. in Appl. Math.*, 27(2-3):510-530, 2001.

[12] Christian Kreft. Explicit computation of the discriminant for the Harper equation with rational flux. *TU Berlin Preprints Archive*, Sonderforschungsbereich 288: Differential Geometry and Quantum Physics, preprint # 89, 1993.

[13] Paul Lévy. Sur l'aire comprise entre un arc de la courbe du mouvement brownien plan et sa corde. *C. R. Acad. Sci.*, Paris, 230:432-434, 1950. (+Erratum on page 689).

[14] Stéphane Ouvry and Alexios P. Polychronakos. Exclusion statistics and lattice random walks. *Nucl. Phys. B*, 948:114731, 2019.

[15] Stéphane Ouvry and Alexios P. Polychronakos. Lattice walk area combinatorics, some remarkable trigonometric sums and Apéry-like numbers. *Nucl. Phys. B*, 960:115174, 2020.

[16] Stéphane Ouvry and Shuang Wu. The algebraic area of closed lattice random walks. *J. Phys. A: Math. Theor.*, 52(25):255201, 2019.
LEFT-TO-RIGHT MAXIMA IN DYCK PATHS

AUBREY BLECHER<fnref n="1" /> ID AND ARNOLD KNOPFMACHER<fnref n="2" /> ID

**Abstract.** In a Dyck path a peak which is (weakly) higher than all the preceding peaks is called a strict (weak) left-to-right maximum. We obtain explicit generating functions for both weak and strict left-to-right maxima in Dyck paths. The proofs of the associated asymptotics make use of analytic techniques such as Mellin transforms, singularity analysis and formal residue calculus.

**Keywords:** Dyck paths, generating functions, asymptotics, left-to-right maxima.

# 1. GENERAL INTRODUCTION

A Dyck path is a lattice path in the first quadrant, that starts at the origin (0,0) with an up step ($u = (1,1)$) and thereafter only up and down ($d = (1,-1)$) steps are allowed under the conditions that it may not go below the x-axis and that it may terminate only if the end point is on the x-axis. A Dyck path with $n$ up steps must end at the point $(2n, 0)$; see the definition in [16]. Such a Dyck path is said to have length $2n$. For a detailed study of properties of Dyck paths see [7]. For further recent work on Dyck paths; see [1–4, 6, 9, 15].

Given an arbitrary Dyck path, we mean by a *strict left-to-right maximum*, any peak (successive pair of the form *ud*) in the Dyck path which is greater than the height all peaks to its left. A *weak left-to-right maximum* is a peak which is greater than or equal to the height of all peaks to its left. From here on, by left-to-right maxima we mean strict left-to-right maxima unless otherwise stated.

A standard combinatorial problem is the accounting for the number of left-to-right maxima in combinatorial structures such as permutations and words over a fixed alphabet. In this paper we focus on obtaining a generating function for the number of left-to-right maxima in Dyck paths. This is a bivariate generating function which tracks the number of up steps by $z$ and the number of left-to-right maxima by $x$. We also obtain a generating function for the total number of left-to-right maxima in Dyck paths with $n$ up steps.

<footnote n="1">¹UNIVERSITY OF THE WITWATERSRAND, JOHANNESBURG, SOUTH AFRICA;
https://independent.academia.edu/AubreyBlecher</footnote>

<footnote n="2">²UNIVERSITY OF THE WITWATERSRAND, JOHANNESBURG, SOUTH AFRICA;
https://scholar.google.com/citations?user=v8k5QLUAAAAJ</footnote>
<figure><img src="image_77.png" /><figcaption>FIGURE 1. Two Dyck paths of length 14 and height 3</figcaption></figure>

As an introduction to the method we will use for the construction of the first generating function above, here follows a sketch (Figure 1) of two Dyck paths of height 3. The left-to-right maxima are marked in the left case by A and P and in the right case by E and P. P also marks the first maximum height attained by the Dyck paths. We begin at the origin with a u step tracked in the generating function by z which leaves us at the point E. This single up step is followed by a possibly empty upside-down Dyck path of maximum height 1.

In the left example in Figure 1, this part is indeed empty (and therefore not requiring $x$) but not in the right example where the path between $E$ and $B$ is an upside-down Dyck path of height 1 which gives rise to a left-to-right maximum thus requiring an $x$ tracker. Then we have another single $u$ step and we proceed recursively in this way leaving us eventually at the next left-to-right maximum which is point $A$ in the left example and $P$ in the right. In the left example, right of $A$ is again a possibly empty upside-down Dyck path, this time of maximum height 2 where the non empty case is tracked again by $x$. We are referring to the path between $A$ and $B$ which is actually of height 1. Once $P$ is reached, it is followed by the rest of the path which is conceived as a right to left portion of a Dyck path. In the section dealing with this, the generating function for these latter Dyck paths ending at height $r$ will be given and used, as will the generating function for Dyck paths of a fixed height $h$, which is used as indicated above for the possibly empty upside-down Dyck paths that occur sequentially before the point $P$ is attained.

## 2. LEFT-TO-RIGHT MAXIMA IN DYCK PATHS

We start this section by referring to the paper [14] by Prodinger on the first sojourn in Dyck paths. Using the notation from [14], we let $C(h)$ be the number of paths of height $\le h$ with steps which follow all rules of Dyck paths except that they terminate at height $h$, and we let $A(h)$ be the number of Dyck paths of height $\le h$ (which by definition end at height zero). It is shown in [14] that

$$C(h) := \frac{z^h \sqrt{1 - 4z^2}}{\lambda_1^{h+2} - \lambda_2^{h+2}}$$

and

$$A(h) := \frac{\lambda_1^{h+1} - \lambda_2^{h+1}}{\lambda_1^{h+2} - \lambda_2^{h+2}}, \qquad (2.1)$$

where $\lambda_1$ and $\lambda_2$, are given by

$$\lambda_1 = \frac{1 + \sqrt{1 - 4z^2}}{2}; \quad \lambda_2 = \frac{1 - \sqrt{1 - 4z^2}}{2}.$$
As explained in the introductory section, we consider a sequence of possibly empty Dyck paths of height $\le h$ for $h = 1, 2, \dots$. At the end of each path in the sequence, we have a single up step that leads to the next left-to-right maximum and eventually to the first overall maximum of the entire Dyck path. We let $x$ count the number of left-to-right maxima attained by the Dyck path. This leads to our first theorem:

**Theorem 2.1.** The generating function for the number of left-to-right maxima tracked by $x$, for Dyck paths of maximum height $r$ and length tracked by $z$ is

$$F(x, z, r) := z^r x C(r) \prod_{h=1}^{r-1} (1 + x(A(h) - 1)).$$

So, the total number of left-to-right maxima for Dyck paths of fixed height $r$ is found by differentiating the above function with respect to $x$ and setting $x = 1$. The derivative at this point is given by

$$\begin{aligned}
\left. \frac{\partial}{\partial x} F(x, z, r) \right|_{x=1} &= z^r C(r) \prod_{h=1}^{r-1} A(h) + z^r C(r) \prod_{h=1}^{r-1} A(h) \sum_{i=1}^{r-1} \frac{A(i) - 1}{A(i)} \\
&= z^r C(r) \prod_{h=1}^{r-1} A(h) \left( 1 + \sum_{i=1}^{r-1} \frac{A(i) - 1}{A(i)} \right) \\
&= z^r C(r) \prod_{h=1}^{r-1} A(h) \left( r - \sum_{i=1}^{r-1} \frac{1}{A(i)} \right)
\end{aligned}
\qquad (2.2)$$

Note that $z^r C(r) \prod_{h=1}^{r-1} A(h)$ telescopes to become

$$\frac{z^{2r} (1 - 4z^2)}{(-\lambda_2^{1+r} + \lambda_1^{1+r}) (-\lambda_2^{2+r} + \lambda_1^{2+r})}$$

but the full generating function becomes very complicated as a function of $z$.

To simplify this generating function, we substitute

$$z^2 = \frac{u}{(1 + u)^2}$$

in (2.2) which implies

$$\lambda_1 = \frac{1}{1+u}; \quad \lambda_2 = \frac{u}{1+u}; \quad C(r) = \frac{(1-u)(1+u)^{1+r}z^r}{1-u^{2+r}}; \quad A(r) = \frac{(1+u)(1-u^{1+r})}{1-u^{2+r}}$$

and obtain

$$T(r) := \left. \frac{\partial}{\partial x} F(x, z, r) \right|_{x=1} = \frac{(1-u)^2 u^r (1+u)}{(1-u^{1+r})(1-u^{2+r})} \left( r - \sum_{i=1}^{r-1} \frac{1-u^{2+i}}{(1+u)(1-u^{1+i})} \right).$$

The full generating function for the total number of left-to-right maxima in all Dyck paths of length $n$ is

$$\mathrm{Tot}(u) := \sum_{r=1}^{\infty} T(r).$$
Consequently, we have the following proposition:

**Proposition 2.2.** The generating function Tot(u) for the total number of left-to-right maxima in Dyck paths of length n tracked by z is given by (using $z^2 = \frac{u}{(1+u)^2}$):

$$ \text{Tot}(u) = \sum_{r=1}^{\infty} \frac{(1-u)^2 u^r (1+u)}{(1-u^{1+r})(1-u^{2+r})} \left( r - \sum_{i=1}^{r-1} \frac{1-u^{2+i}}{(1+u)(1-u^{1+i})} \right). \quad (2.3) $$

In order to obtain the series expansion for this, we use the equivalent inverse substitution for u, namely

$$ u = \frac{1 - 2z^2 - \sqrt{1 - 4z^2}}{2z^2}, \quad (2.4) $$

and obtain in terms of z,

$$ \text{Tot}(u) = z^2 + 2z^4 + 6z^6 + \mathbf{19}z^8 + 63z^{10} + 216z^{12} + 758z^{14} + 2705z^{16} + 9777z^{18} + 35698z^{20} + O(z^{21}). $$

We illustrate the bold term of the series by means of the black dots in Figure 2.

<figure><img src="image_78.png" /><figcaption>FIGURE 2. All 14 Dyck paths of length 8: they have 19 strict left-to-right maxima (indicated by black dots) and 10 weak left-to-right maxima (indicated by circles).</figcaption></figure>
The type of series expansion for Tot($u$) in Proposition 2.2 involves what is called Lambert series. There are currently no computer algebra packages that can automatically simplify expressions like Equation (2.3). Instead, it is therefore necessary to make the following lengthy calculations in order to derive Theorem 2.3.

To simplify Equation (2.3) we swap the order of the summations in the double sum, and thereafter use partial fractions on the $r$-indexed sum (which then telescopes as in line (2.5)) to obtain

$$ 
\begin{aligned}
& \sum_{r=1}^{\infty} \frac{(1-u)^2 u^r (1+u)}{(1-u^{1+r})(1-u^{2+r})} \sum_{i=1}^{r-1} \frac{1-u^{2+i}}{(1+u)(1-u^{1+i})} \\
&= (1-u)^2 \sum_{i=1}^{\infty} \frac{1-u^{2+i}}{(1-u^{1+i})} \sum_{r=i+1}^{\infty} \frac{u^r}{(1-u^{1+r})(1-u^{2+r})} \\
&= (1-u)^2 \sum_{i=1}^{\infty} \frac{1-u^{2+i}}{(1-u^{1+i})} \frac{u^{1+i}}{(1-u)(1-u^{2+i})}.
\end{aligned} 
\quad (2.5) $$

Now changing the index of summation from $i$ to $r$,

$$ (1-u) \sum_{i=1}^{\infty} \frac{1-u^{2+i}}{(1-u^{1+i})} \frac{u^{1+i}}{(1-u^{2+i})} = (1-u) \sum_{r=1}^{\infty} \frac{u^{1+r}}{(1-u^{1+r})}. $$

Altogether,

$$ 
\begin{aligned}
\mathrm{Tot}(u) &= \sum_{r=1}^{\infty} \frac{(1-u)^2 u^r (1+u)r}{(1-u^{1+r})(1-u^{2+r})} - (1-u) \sum_{r=1}^{\infty} \frac{u^{1+r}}{(1-u^{1+r})} \\
&= \sum_{r=1}^{\infty} \frac{(1-u)u^r (r-u-r u^2 + u^{3+r})}{(1-u^{1+r})(1-u^{2+r})} \\
&= \sum_{r=1}^{\infty} \frac{r u^r - u^{1+r} - r u^{1+r} + u^{2+r} - r u^{2+r} + r u^{3+r} + u^{3+2r} - u^{4+2r}}{(1-u^{1+r})(1-u^{2+r})}.
\end{aligned} $$

Drop the first term $ru^r$ in the numerator above and apply partial fractions to the rest of the summand which simplifies to

$$ 1 - u + \frac{-1 - r + 2u - ru - u^2 + ru^2}{(1 - u)(1 - u^{1+r})} + \frac{r + ru - ru^2}{(1 - u)(1 - u^{2+r})}. $$

The separated first term with numerator $ru^r$ after partial fractions leads to

$$ \frac{ru^r}{(1-u)(1-u^{1+r})} - \frac{ru^{r+1}}{(1-u)(1-u^{2+r})}. $$

Altogether,

$$ 
\begin{aligned}
\mathrm{Tot}(u) &= \sum_{r=1}^{\infty} \left( 1 - u + \frac{-1 - r + 2u - ru - u^2 + ru^2}{(1-u)(1-u^{1+r})} + \frac{r + ru - ru^2}{(1-u)(1-u^{2+r})} \right) \\
&\quad + \sum_{r=1}^{\infty} \frac{ru^r}{(1-u)(1-u^{1+r})} - \sum_{r=1}^{\infty} \frac{ru^{r+1}}{(1-u)(1-u^{2+r})}.
\end{aligned} $$
To facilitate the evaluation of the infinite sums, we define a new function (where $\infty$ is replaced temporarily by finite $M$ in $\text{Tot}(u)$), namely:

$$ \text{Tot2}(u) := \sum_{r=1}^{M} \left( 1 - u + \frac{-1 - r + 2u - ru - u^2 + ru^2}{(1-u)(1-u^{1+r})} + \frac{r + ru - ru^2}{(1-u)(1-u^{2+r})} \right) \\ + \sum_{r=1}^{M} \frac{ru^r}{(1-u)(1-u^{1+r})} - \sum_{r=1}^{M} \frac{ru^{r+1}}{(1-u)(1-u^{2+r})}. $$

We now separate this into disjoint sums and shift the index of summation in the third and last sums:

$$ \begin{aligned} \text{Tot2}(u) &= \sum_{r=1}^{M} (1-u) + \sum_{r=1}^{M} \frac{-1-r+2u-ru-u^2+ru^2}{(1-u)(1-u^{1+r})} + \sum_{r=2}^{M+1} \frac{(r-1)(1+u-u^2)}{(1-u)(1-u^{1+r})} \\ &\quad + \sum_{r=1}^{M} \frac{ru^r}{(1-u)(1-u^{1+r})} - \sum_{r=2}^{M+1} \frac{(r-1)u^r}{(1-u)(1-u^{1+r})} \\ &= \sum_{r=1}^{M} (1-u) + \frac{-2+u}{(1-u)(1-u^2)} + \sum_{r=2}^{M} \frac{-1-r+2u-ru-u^2+ru^2}{(1-u)(1-u^{1+r})} \\ &\quad + \sum_{r=2}^{M} \frac{(r-1)(1+u-u^2)}{(1-u)(1-u^{1+r})} + \frac{M(1+u-u^2)}{(1-u)(1-u^{2+M})} + \frac{u}{(1-u)(1-u^2)} \\ &\quad + \sum_{r=2}^{M} \frac{ru^r}{(1-u)(1-u^{1+r})} - \sum_{r=2}^{M} \frac{(r-1)u^r}{(1-u)(1-u^{1+r})} - \frac{Mu^{1+M}}{(1-u)(1-u^{2+M})}. \end{aligned} \quad (2.6) $$

We combine the terms in the sums from $r$ equals 2 to $M$ in (2.6) to get

$$ \frac{-2+u+u^r}{(1-u)(1-u^{1+r})}. $$

Then we simplify the rest to get

$$ \text{Tot2}(u) = \sum_{r=2}^{M} \frac{-2+u+u^r}{(1-u)(1-u^{1+r})} - \frac{2}{1-u^2} \\ - \frac{M(-2+u+u^{1+M}+u^{2+M}-2u^{3+M}+u^{4+M})}{(1-u)(1-u^{2+M})}. $$

Note that $\text{Tot2}(u)$ and $\text{Tot}(u)$ match at least for terms up to $[u^M]$. Since for the present we are only interested in the terms up to $[u^M]$, we may set all higher power terms equal to zero, to produce

$$ \text{Tot2b}(u) = \sum_{r=2}^{M} \frac{-2+u+u^r}{(1-u)(1-u^{1+r})} - \frac{2}{1-u^2} + M \frac{(2-u)}{(1-u)}. $$
Noting that $M = 1 + \sum_{r=2}^{M} 1$,

$$ \begin{aligned} \text{Tot2b}(u) &= \sum_{r=2}^{M} \frac{-2+u+u^r}{(1-u)(1-u^{1+r})} - \frac{2}{1-u^2} + \frac{(2-u)}{(1-u)} + \sum_{r=2}^{M} \frac{(2-u)}{(1-u)} \\ &= \sum_{r=2}^{M} \frac{-2+u+u^r}{(1-u)(1-u^{1+r})} + \frac{u}{1+u} + \sum_{r=2}^{M} \frac{(2-u)}{(1-u)}. \end{aligned} $$

Combine the summands in $\sum_{r=2}^{M}$. We may now allow $M \to \infty$ to finally obtain the simplified generating function as per the next theorem:

**Theorem 2.3.** The simplified generating function for the total number of left-to-right maxima in Dyck paths is

$$ \text{Tot}(u) = \sum_{r=1}^{\infty} \frac{(1-u)u^r}{1-u^{1+r}}. \qquad (2.7) $$

2.1. **Formula for total number of left-to-right maxima.** In this section, we will obtain an exact formula for the total number of left-to-right maxima in terms of a well-known arithmetic function, namely the divisor function $d(r)$. Compare with [5]. Note that

$$ \sum_{r=1}^{\infty} \frac{u^r}{1-u^r} = \sum_{r=1}^{\infty} d(r) u^r. $$

To read off coefficients from equation (2.7), we observe that for any formal power series $f(z)$

$$ [z^{2n}] f(z) = [u^n](1-u)(1+u)^{2n-1} f(z(u)). $$

This can be justified by using formal residue calculus; see for example [12]. Therefore

$$ \begin{aligned} [z^{2n}] \text{Tot}(z) &= [u^n](1-u)(1+u)^{2n-1} \sum_{r=1}^{\infty} \frac{(1-u)u^r}{1-u^{1+r}} \\ &= [u^n](1-u)(1+u)^{2n-1} \sum_{r=1}^{\infty} (d(r+1)-d(r))u^r \\ &= \sum_{r=1}^{n} (d(r+1)-d(r)) \left( \binom{2n-1}{n-r} - \binom{2n-1}{n-r-1} \right). \end{aligned} $$

Thus we have shown:

**Theorem 2.4.** The total number of left-to-right maxima in Dyck paths of semi-length $n$ is given by

$$ \sum_{r=1}^{n} (d(r+1) - d(r)) \left( \binom{2n-1}{n-r} - \binom{2n-1}{n-r-1} \right). $$
### 3. ASYMPTOTICS FOR STRICT LEFT-TO-RIGHT MAXIMA

In this section we find the asymptotic expression for the total number of strict left-to-right maxima in Dyck paths. We will follow the approach used to study the height of planted plane trees by Prodinger in [12]. For related asymptotic calculations concerning the height of trees and lattice paths; see [10, 11, 13] and the seminal article by de Bruijn, Knuth and Rice [5].

First, we extract coefficients of $z^n$ in $\text{Tot}(u)$. That is we find

$$[z^n] \frac{1-u}{u} \sum_{r=2}^{\infty} \frac{u^r}{1-u^r}.$$

When $u$ is in terms of $z^2$, by (2.4) the function $\text{Tot}(u)$ has its dominant singularity at $z = 1/2$ which is mapped to $u = 1$. To study this further we set $u = e^{-t}$ and let $t \to 0$. Thus

$$\frac{1-u}{u} = e^t(1-e^{-t}) = t + \frac{t^2}{2} + \frac{t^3}{6} + \dots \quad (3.1)$$

To estimate the harmonic sum $f_1(t) := \sum_{r=2}^{\infty} \frac{e^{-rt}}{1-e^{-rt}}$ as $t \to 0$, we take the Mellin transform of $f_1(t)$, see [8], which is $f_1^*(s) := \int_0^\infty f_1(t) t^{s-1} dt$. Thus

$$f_1^*(s) = \Gamma(s)\zeta(s)(\zeta(s)-1), \text{ for } \Re(s) > 1.$$

By using the Mellin inversion formula, we have $f_1(t) = \frac{1}{2\pi i} \int_{2-i\infty}^{2+i\infty} f_1^*(s) t^{-s} ds$ (again see [8]). By computing residues this yields

$$f_1(t) \sim \frac{-1 + \gamma - \log(t)}{t} + \frac{3}{4} - \frac{13t}{144} + \dots, \quad (3.2)$$

where $\gamma$ is Euler's constant.

Let

$$g_1(t) := e^t(1 - e^{-t}) f_1(t).$$

From (3.1) and (3.2)

$$g_1(t) \sim -\log(t) - 1 + \gamma + \left(\frac{3}{4} + \frac{1}{2}(-1 + \gamma - \log(t))\right)t + \dots$$

Let $y = \sqrt{1-4z^2}$ and writing $e^{-t} = u = \frac{1-y}{1+y}$, we find $t = -\log \frac{1-y}{1+y} = 2y + \frac{2y^3}{3} + \dots$.

In terms of the $y$ variable, we therefore need to compute $g_1(2y + \frac{2y^3}{3} + \dots)$.

$$g_1\left(2y + \frac{2y^3}{3} + \dots\right) \sim (-1 + \gamma - \log(2) - \log(y)) + \frac{1}{2}(1 + 2\gamma - 2\log(2) - 2\log(y))y \\ - \frac{y^2}{3} + \dots$$

Replacing $y$ by $\sqrt{1-4z^2}$ gives

$$-1 + \gamma - \log(2) - \frac{1}{2}\log(1 - 4z^2) + \frac{1}{2}(1 + 2\gamma - 2\log(2) - \log(1 - 4z^2))\sqrt{1 - 4z^2} + \dots$$
To use singularity analysis, see [8], it is convenient to put $z^2 = x$, then we find the coefficient of $x^n$ in the above expression as $n \to \infty$. It is asymptotically equal to

$$2^{2n} \left( \frac{1}{2n} - \frac{\log(n)}{4\sqrt{\pi}n^{3/2}} + \frac{1-3\gamma}{4n^{3/2}\sqrt{\pi}} + \dots \right). \qquad (3.3)$$

To obtain the mean value we must divide by the total number of Dyck paths of semi-length $n$, i.e., as $n \to \infty$

$$\frac{1}{n+1} \binom{2n}{n} = 2^{2n} \left( \frac{1}{n^{3/2}\sqrt{\pi}} - \frac{9}{8 n^{5/2}\sqrt{\pi}} + \frac{145}{128 n^{7/2}\sqrt{\pi}} \right) + \dots . \qquad (3.4)$$

Hence, dividing (3.3) by (3.4) yields

**Theorem 3.1.** The average number of strong left-to-right maxima in Dyck paths of semi-length $n$, as $n \to \infty$ is

$$\frac{\sqrt{\pi n}}{2} - \frac{\log(n)}{4} + \frac{1}{4}(1 - 3\gamma) + O(n^{-1/2}).$$

*Remark 3.2.* The asymptotic formula of Theorem 3.1 when $n = 200$ yields 11.0257 for the average number of strong left-to-right maxima. Using the exact formula of Theorem 2.4 divided by the Catalan number for $n = 200$ yields 11.0503 which is indeed a very good match.

*Remark 3.3.* The number of strong left-to-right maxima is bounded above by the height of the path, which is known to be $\sim \sqrt{\pi n}$ as $n \to \infty$, (see, e.g., [12]). We see that asymptotically the average number is half of the height.

### 4. WEAK LEFT-TO-RIGHT MAXIMA IN DYCK PATHS

For this question we first need a generating function for Dyck paths of height $\le h$ which have only a single return to the $x$ axis. So using the formula above from (2.1), we obtain the generating function for these where $h \ge 1$ as

$$D(h, z) = z^2 A(h-1).$$

Now in order to construct the generating function $E(h, x, z)$ for the number of times a Dyck path of height $\le h$ and length $n$ tracked by $z$, returns to 0 where the latter is tracked by a variable $x$ in the generating function, we construct a sequence of such Dyck paths where each term in the generating function for this sequence is multiplied by $x$. Thus we obtain

$$E(h, x, z) = \frac{1}{1 - xD(h, z)}.$$

We now reiterate the construction in Theorem 2.1 to obtain the following theorem.

**Theorem 4.1.** The generating function for the number of weak left-to-right maxima, tracked by $x$, for Dyck paths of maximum height $r$ and length tracked by $z$ is

$$F(x, z, r) := z^{r+1} x C(r-1) \prod_{h=1}^{r} E(h, x, z). \qquad (4.1)$$

To obtain the generating function for the total number of weak left-to-right maxima, we once again differentiate (4.1) with respect to $x$ and evaluate this at $x = 1$. We obtain
**Theorem 4.2.** The generating function for the total number of weak left-to-right maxima for Dyck paths of length n tracked by z is

$$WT_{\text{Tot}}(u) := \sum_{r=1}^{\infty} \frac{(1-u)u^r(1-u^2)}{(1-u^{1+r})(1-u^{2+r})} \left(1-r+(1+u)\sum_{i=1}^{r} \frac{1-u^{1+i}}{1-u^{2+i}}\right),$$

where $z^2 = \frac{u}{(1+u)^2}$.

*Proof.* The derivative of (4.1) is

$$\left. \frac{\partial}{\partial x} F(x, z, r) \right|_{x=1} = z^{r+1} C(r-1) \prod_{h=1}^{r} E(h, 1, z) \left( 1 + \sum_{i=1}^{r} \frac{D(i, z)}{1 - D(i, z)} \right).$$

Putting $z^2 = \frac{u}{(1+u)^2}$ in the formula above we obtain

$$z^{r+1} C(r-1) \prod_{h=1}^{r} \frac{1}{1-z^2 A(h-1)} = \frac{(1-u)u^r(1-u^2)}{(1-u^{1+r})(1-u^{2+r})},$$

while the remaining bracketed part becomes

$$1 - r + (1 + u) \sum_{i=1}^{r} \frac{1 - u^{1+i}}{1 - u^{2+i}}.$$

<figure><img src="image_79.png" /></figure>

Now, we simplify Theorem 4.2. The double sum becomes

$$(1-u^2)^2 \sum_{i=1}^{\infty} \frac{1-u^{1+i}}{1-u^{2+i}} \sum_{r=i}^{\infty} \frac{u^r}{(1-u^{1+r})(1-u^{2+r})}.$$

We use partial fractions on the r-sum and then the double sum telescopes to

$$\frac{(1-u^2)^2}{(1-u)u} \sum_{i=1}^{\infty} \frac{u^{i+1}}{1-u^{i+2}}.$$

This is then combined with the single sum which simplifies to

$$\sum_{r=1}^{\infty} \left( \frac{(1-u)u^r(1-u^2)(1-r)}{(1-u^{1+r})(1-u^{2+r})} + \frac{(1-u^2)^2 u^{1+r}}{(1-u)u(1-u^{2+r})} \right). \qquad (4.2)$$

In order to further simplify (4.2) we replace $\infty$ by finite M and then apply partial fractions to the summand of the first term which splits up as

$$\frac{(-1+r)(1-u)(1+u)}{u(1-u^{1+r})} - \frac{(-1+r+1)(1-u)(1+u)}{u(1-u^{2+r})} - \frac{(1-u)(1+u)}{u(1-u^{2+r})}.$$

This is telescoping and simplifies to

$$-\frac{(-1 + M + 1)(1 - u)(1 + u)}{u(1 - u^{2+M})} + \sum_{r=1}^{M} \left( \frac{(1 - u^2)^2 u^{1+r}}{(1 - u)u(1 - u^{2+r})} - \frac{(1 - u)(1 + u)}{u(1 - u^{2+r})} \right).$$

Now, replace M by $\sum_{r=1}^{M} 1$. Then, letting M tend to $\infty$, and finally combining all summands, we obtain
**Theorem 4.3.** The simplified generating function for the total number of weak left-to-right maxima for Dyck paths of length $n$ tracked by $z$ is

$$WT_{\text{tot}}(u) = \sum_{r=1}^{\infty} \frac{(1-u^2)u^r}{1-u^{2+r}}.$$

This has series expansion

$$z^2+3z^4+9z^6+\mathbf{29z^8}+98z^{10}+341z^{12}+1210z^{14}+4356z^{16}+15860z^{18}+58276z^{20}+O(z^{21}).$$

This is illustrated in Figure 2, where the dots and circles mark all 29 of the weak left-to-right maxima in Dyck paths of length 8.

**4.1. Formula for total number of weak left-to-right maxima.** In this section, we again obtain an exact formula for the total number of left-to-right maxima in terms of the divisor function $d(r)$. To read off coefficients from Theorem 4.3, as before

$$[z^{2n}]f(z) = [u^n](1-u)(1+u)^{2n-1}f(z(u)).$$

Therefore

$$[z^{2n}]WT_{\text{tot}}(z) = [u^n](1-u)(1+u)^{2n-1} \sum_{r=1}^{\infty} \frac{(1-u^2)u^r}{1-u^{2+r}} \\ = [u^n](1-u)(1+u)^{2n-1} \sum_{r=1}^{\infty} (d(r+2) - d(r))u^r.$$

We thus get the following theorem.

**Theorem 4.4.** The total number of weak left-to-right maxima in Dyck paths of semi-length $n$ is given by

$$\sum_{r=1}^{n} (d(r+2) - d(r)) \left( \binom{2n-1}{n-r} - \binom{2n-1}{n-r-1} \right).$$

## 5. ASYMPTOTICS FOR WEAK LEFT-TO-RIGHT MAXIMA

To find an asymptotic expression for $WT_{\text{tot}}(u)$, we reiterate the approach in Section 3. This yields

**Theorem 5.1.** The average number of weak left-to-right maxima in Dyck paths of semi-length $n$, as $n \to \infty$ is

$$\sqrt{\pi n} - \log(n) + \frac{1}{2}(5 - 6\gamma) + O(n^{-1/2}).$$

*Remark 5.2.* The asymptotic formula of Theorem 5.1 when $n = 200$ yields 20.536 for the average number of weak left-to-right maxima. Using the exact formula of Theorem 4.4 divided by the Catalan number for $n = 200$ yields 20.368. Taking larger $n$ improves the accuracy.
## 6. OPEN PROBLEMS

Theorem 2.4 and Theorem 4.4 are very similar to each other with only a slight change in their respective summands; this suggests that there is an underlying combinatorial proof. Also from Theorems 2.3 and 4.3 we obtain

$$WTot(u) = \frac{1+u}{u} Tot(u) - 1.$$

We think that accounting for these similarities may be an interesting combinatorial problem which we leave to the reader. It might also be possible to derive Theorem 2.3 in a simpler and more direct way instead of using Proposition 2.2.

The statistic left-to-right maximum, ‘lrmax’ is quite important in permutations due to the fact that it is equidistributed with the ‘cycle’ statistic and is counted nicely by Stirling numbers of the first kind. One of the main reasons for studying lrmax in permutations is this equidistribution with the number of cycles. Hence in the current setting one should anticipate a counterpart statistic in Dyck path to be equidistributed with lrmax.

With respect to permutations, there are other statistics equidistributed with lrmax. In the Dyck path context one can also introduce such concepts. This may potentially lead to further interesting research.

## REFERENCES

[1] Axel Bacher, Antonio Bernini, Luca Ferrari, Benjamin Gunby, Renzo Pinzani, and Julian West. The Dyck pattern poset. Discrete Mathematics, 16:123–152, 1970.

[2] Aubrey Blecher, Charlotte Brennan, and Arnold Knopfmacher. Water capacity of Dyck paths. Advances in Applied Mathematics, 112(101945):1–19, 2020.

[3] Éva Czabarka, Rigoberto Flórez, and Leandro Junes. Some enumerations on non-decreasing Dyck paths. Electronic Journal of Combinatorics, 22:1–22, 2015.

[4] Éva Czabarka, Rigoberto Flórez, Leandro Junes, and José L. Ramírez. Enumerations of peaks and valleys on non-decreasing Dyck paths. Discrete Mathematics, 341:2789–2807, 2018.

[5] Nicolaas Govert de Bruijn, Donald E. Knuth, and Stephen O. Rice. The average height of planted plane trees. In R. C. Read, editor, Graph Theory and Computing, pages 15–22. Academic Press, 1972.

[6] Emeric Deutsch. A bijection on Dyck paths and its consequences. Discrete Mathematics, 179:253–256, 1998.

[7] Emeric Deutsch. Dyck path enumeration. Discrete Mathematics, 204:167–202, 1999.

[8] Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009.

[9] Kostas Manes, Aristidis Sapounakis, Ioannis Tasoulas, and Panagiotis Tsikouras. Nonleft peaks in Dyck paths. Discrete Mathematics, 337:97–105, 2014.

[10] Wolfgang Panny and Helmut Prodinger. The expected height of paths for several notions of height. Studia Scientiarum Mathematicarum Hungarica, 20:119–132, 1985.

[11] Helmut Prodinger. A note on a result of R. Kemp on r-tuply rooted planted plane trees. Computing, 20:363–366, 1982.

[12] Helmut Prodinger. Height of planted trees revisited. Ars Combinatoria, 16:8:51–55, 1983.

[13] Helmut Prodinger. Some analytic techniques for the investigation of the asymptotic behaviour of tree parameters. Bulletin of the EATCS, 47:180–199, 1992.

[14] Helmut Prodinger. The location of the first maximum in the first sojourn of a Dyck path. Discrete Mathematics and Theoretical Computer Science, 10:125–134, 2008.

[15] Aristidis Sapounakis, Ioannis Tasoulas, and Panagiotis Tsikouras. Enumeration of strings in Dyck paths: A bijective approach. Discrete Mathematics, 309:3032–3039., 2009.

[16] Richard P. Stanley. Enumerative Combinatorics. Cambridge University Press, 1999.
RESTRICTED DYCK PATHS ON VALLEYS SEQUENCE

RIGOBERTO FLÓREZ¹ ID, TOUFIK MANSOUR² ID, JOSÉ L. RAMÍREZ³ ID,
FABIO A. VELANDIA⁴ ID, AND DIEGO VILLAMIZAR⁵ ID

¹DEPARTMENT OF MATHEMATICAL SCIENCES, THE CITADEL, CHARLESTON, SC, U.S.A.;
https://www.rigoflorez.com/

²DEPARTMENT OF MATHEMATICS, UNIVERSITY OF HAIFA, 3498838 HAIFA, ISRAEL;
https://math.haifa.ac.il/toufik/

³DEPARTAMENTO DE MATEMÁTICAS, UNIVERSIDAD NACIONAL DE COLOMBIA, BOGOTÁ, COLOMBIA;
https://sites.google.com/site/ramirezrj1/

⁴DEPARTAMENTO DE MATEMÁTICAS, UNIVERSIDAD NACIONAL DE COLOMBIA, BOGOTÁ, COLOMBIA;
https://orcid.org/0000-0002-9542-0782

⁵ESCUELA DE CIENCIAS EXACTAS E INGENIERÍA, UNIVERSIDAD SERGIO ARBOLEDA, BOGOTÁ,
COLOMBIA; https://sites.google.com/view/dvillami/

**Abstract.** In this paper we study a subfamily of a classic lattice path, the *Dyck paths*, called *restricted *d*-Dyck paths*, in short *d*-Dyck. A valley of a Dyck path *P* is a local minimum of *P*; if the difference between the heights of two consecutive valleys (from left to right) is at least *d*, we say that *P* is a restricted *d*-Dyck path. The *area* of a Dyck path is the sum of the absolute values of *y*-components of all points in the path. We find the number of peaks and the area of all paths of a given length in the set of *d*-Dyck paths. We give a bivariate generating function to count the number of the *d*-Dyck paths with respect to the semi-length and number of peaks. After that, we analyze in detail the case *d* = -1. Among other things, we give both the generating function and a recursive relation for the total area.

**Keywords:** Dyck path, *d*-Dyck path, generating function.

# 1. INTRODUCTION

A classic concept, the *Dyck paths*, has been widely studied. Recently, a subfamily of
these paths, non-decreasing Dyck paths, has received a certain level of interest. It is
because of some statistics are given by linear combinations of Fibonacci numbers and
Lucas numbers. In this paper we keep studying a generalization of the non-decreasing
Dyck paths. Other generalizations of non-decreasing Dyck paths have been given for
Motzkin paths and for Łukasiewicz paths [14, 15].

We now give some definitions that we use in this paper. A Dyck path is a lattice path in the first quadrant of the *xy*-plane that starts at the origin, ends on the *x*-axis, and consists of (the same number of) North-East steps *U* := (1, 1) and South-East steps *D* := (1, −1). The *semi-length* of a path is the total number of *U*'s that the path has.
A *valley (peak)* is a subpath of the form *DU (UD)* and the *valley vertex of DU* is the lowest point (a local minimum) of *DU*. The *level* of a valley is the *y*-component of its valley vertex. Following [16, 17] we define the *valley vertices vector* of a Dyck path *P* as the vector $\nu = (\nu_1, \nu_2, \dots, \nu_k)$ formed by all *y*-coordinates (listed from left to right) of all valley vertices of *P*.

For a fixed $d \in \mathbb{Z}$, a Dyck path $P$ is called *restricted $d$-Dyck* or *$d$-Dyck* (for simplicity), if either $P$ has at most one valley, or if its valley vertex vector $\nu$ satisfies that $\nu_{i+1} - \nu_i \ge d$, where $1 \le i < k$. The set of all $d$-Dyck paths of semi-length $n$ is denoted $\mathcal{D}_d(n)$, where $r_d(n)$ denotes its cardinality, and the set of all $d$-Dyck paths is denoted by $\mathcal{D}_d$.

The first well-known example of these paths is the set of 0-Dyck paths; in the literature, see [4, 6, 7, 9, 10, 12], this family is known as non-decreasing Dyck paths. The whole family of Dyck paths can be seen as a limit of $d$-Dyck and it occurs when $d \to -\infty$. Another example, from Figure 1 we observe that $\nu = (0, 1, 0, 3, 4, 3, 2)$ and that $\nu_{i+1} - \nu_i \ge -1$, for $i = 1, \dots, 6$, so the figure depicts a (-1)-Dyck path of length 28 (or semi-length 14).

<figure><img src="image_80.png" /><figcaption>FIGURE 1. A (-1)-Dyck path of length 28.</figcaption></figure>

The recurrence relations and/or the generating functions for $d$-Dyck when $d \ge 0$ have different behavior than the case $d < 0$. For example, generating functions accounting for the number of valleys, the number of peaks, and the area, for $d$-Dyck when $d \ge 0$, are all rational for all variables (see [4, 6, 7, 10, 12, 16, 17]). However, when we analyze in this paper several aspects for $d < 0$ (the number of paths, the area of the paths, and the number of peaks) we find that the generating functions are all algebraic (non-rational).

In this paper we give a bivariate generating function to count the number of paths in $\mathcal{D}_d(n)$, for $d \le 0$, with respect to the number of peaks and semi-length. We also give a relationship between the total number of $d$-Dyck paths and the Catalan numbers. Additionally, we give an explicit symbolic expression for the generating function with respect to the semi-length. For the particular case $d = -1$ we give a combinatorial expression and a recursive relation for the total number of paths. We also analyze the asymptotic behavior for the sequence $r_{-1}(n)$.

It is well known that there are many bijections between Dyck paths and other combinatorial objects, we are wondering if there are other bijections between $d$-Dyck paths for $d < -1$ and other object of combinatorics.

The *area* of a Dyck path *P* is the sum of the values of *y*-components of all points in the path. That is, the area of *P*, denoted by $\text{area}(P)$, corresponds to the surface area under *P* and above of the *x*-axis. For example, if *P* is the path in Figure 1, then $\text{area}(P) = 70$. We use generating functions and recursive relations to analyze the distribution of the area of all paths in $\mathcal{D}_{-1}(n)$.
The problem of enumerating the area in directed lattice paths, in a general setting, was solved by Banderier and Gittenberger [3], building on the enumerative and asymptotics results from [2], where Dyck, Motzkin, and Łukasiewicz paths are particular cases.

A summary of notation used throughout the paper appears in Table 1 in the appendix.

## 2. NUMBER OF d-DYCK PATHS AND PEAKS STATISTIC

Given a family of lattice paths, a classic question is how many lattice paths are there of certain length, and a second classic question is how many peaks are there depending on the length of the path. These questions have been completely answered, for instance, for Dyck paths [8], d-Dyck paths for $d \ge 0$ [4, 17], and Motzkin paths [20] among others. In this section we give a bivariate generating function according to the semi-length and the number of peaks of the d-Dyck paths with $d < 0$.

Given a d-Dyck path P, we denote the semi-length of P by $\ell(P)$ and denote the number of peaks of P by $\rho(P)$. So, the bivariate generating function to count the number of paths and peaks of d-Dyck paths is defined by

$$L_d(x, y) := \sum_{P \in \mathcal{D}_d} x^{\ell(P)} y^{\rho(P)}.$$

### 2.1. Some facts known when $d \ge 0$. These results can be found in [17].

* If $d \ge 0$, then the generating function $F_d(x, y)$ is given by

$$L_d(x, y) = 1 + \frac{xy(1 - 2x + x^2 + xy - x^{d+1}y)}{(1 - x)(1 - 2x + x^2 - x^{d+1}y)}.$$

* If $d \ge 1$,

$$r_d(n) = \sum_{k=0}^{\lfloor \frac{n+d-2}{d} \rfloor} \binom{n - (d-1)(k-1)}{2k}.$$

* If $n > d$, then we have the recursive relation

$$r_d(n) = 2r_d(n-1) - r_d(n-2) + r_d(n-d-1),$$

with the initial values $r_d(n) = \binom{n}{2} + 1$, for $0 \le n \le d$.

* Let $p_d(n, k)$ be the number of d-Dyck paths of semi-length $n$, having exactly $k$ peaks. If $d \ge 0$, then

$$p_d(n, k) = \binom{n + k - d(k - 2) - 2}{2(k - 1)}.$$

For the whole set of Dyck paths, the number $p_{-\infty}(n, k)$, is given by the Narayana numbers $N(n, k) = \frac{1}{n} \binom{n}{k} \binom{n}{k-1}$.

### 2.2. Peaks statistic for $d$ a negative integer.
For the remaining part of the paper we consider only the case $d < 0$ and use $e$ to denote $|d|$. A *pyramid* of semi-length $h \ge 1$ is a subpath of the form $X^h Y^h$; it is *maximal*, denote by $\Delta_h$, if it can not be extended to a pyramid $X^{h+1}Y^{h+1}$.
**Theorem 2.1.** If $d$ is a negative integer and $e := |d|$, then the generating function $L_e(x, y)$ satisfies the functional equation

$$L_e(x, y) = xy + xL_e(x, y) + xS_e(x, y)L_e(x, y), \qquad (2.1)$$

where $S_e(x)$ satisfies the algebraic equation

$$(1 - xS_e(x, y))^e (y + (1 - y)xS_e(x, y)) - S_e(x, y)(1 - xS_e(x, y))^{e+1} - \frac{x^{e+2}y}{1-x}S_e(x, y) = 0.$$

*Proof.* We start this proof by introducing some notation. The set $Q_{d,i} \subseteq D_d$ denotes the family of non-empty paths where the last valley is at level $i$. We consider the generating function

$$Q_i^{(e)}(x, y) := \sum_{P \in Q_{d,i}} x^{\ell(P)} y^{\rho(P)}.$$

It is convenient to consider the sum over the $Q_i^{(e)}(x, y)$. We also consider the generating function, with respect to the lengths and peaks, that counts the $d$-Dyck paths that have either no valleys or the last valley is at level less than $e$. That is,

$$S_e(x, y) = \frac{y}{1-x} + \sum_{j=0}^{e-1} Q_j^{(e)}(x, y). \qquad (2.2)$$

A path $P$ can be uniquely decomposed as either $UD, UTD$, or $UQDT$ (by considering the first return decomposition), where $T \in D_d$ and $Q$ is either a pyramid or is a path in $\cup_{i=0}^{e-1} Q_{d,i}$ (see Figure 2, for a graphical representation of this decomposition). Notice that $\nu_{i+1} - \nu_i \ge d$ and the decomposition $UQDT$ ensures that $Q$ holds as in the former line.

<figure><img src="image_81.png" /><figcaption>FIGURE 2. Decomposition of a $d$-Dyck path.</figcaption></figure>

From the symbolic method we obtain the functional equation

$$L_e(x, y) = xy + xL_e(x, y) + xS_e(x, y)L_e(x, y).$$

Now we are going to obtain a system of equations for the generating functions $Q_i(x, y)$. Let $Q$ be a path in the set $Q_{d,i}$. If $i = 0$, then the path $Q$ can be decomposed uniquely as either $UQ'D\Delta$ or $UQ'DR$, where $\Delta$ is a pyramid, $R$ is a path in $Q_{d,0}$, and $Q'$ is either a pyramid or $Q' \in \cup_{i=0}^{e-1} Q_{d,i}$. Therefore, we have the functional equation

$$Q_0^{(e)}(x, y) = xS_e(x, y) \frac{xy}{1-x} + xS_e(x, y)Q_0^{(e)}(x, y).$$

For $i > 0$, any path $Q$ can be decomposed uniquely in one of these two forms $UR_1D$ or $UQDR_2$, where $R_1 \in Q_{d,i-1}$, $R_2 \in Q_{d,i}$, and $Q$ is either a pyramid or $Q \in \cup_{i=0}^{e-1} Q_{d,i}$. So, we have the functional equation

$$Q_i^{(e)}(x, y) = xQ_{i-1}^{(e)}(x, y) + xS_e(x, y)Q_i^{(e)}(x, y). \qquad (2.3)$$
Summarizing the discussion above, we obtain the system of equations:

$$ \left\{ \begin{array}{l} Q_0^{(e)}(x, y) = xS_e(x, y) \frac{xy}{1-x} + xS_e(x, y)Q_0^{(e)}(x, y) \\ Q_1^{(e)}(x, y) = xQ_0^{(e)}(x, y) + xS_e(x, y)Q_1^{(e)}(x, y) \\ \vdots \\ Q_i^{(e)}(x, y) = xQ_{i-1}^{(e)}(x, y) + xS_e(x, y)Q_i^{(e)}(x, y) \\ \vdots \\ Q_{e-1}^{(e)}(x, y) = xQ_{e-2}^{(e)}(x, y) + xS_e(x, y)Q_{e-1}^{(e)}(x, y). \end{array} \right. \qquad (2.4) $$

Summing up the equations in (2.4), we obtain that

$$ \sum_{j=0}^{e-1} Q_j^{(e)}(x, y) = xS_e(x, y) \left( \sum_{j=0}^{e-1} Q_j^{(e)}(x, y) + \frac{xy}{1-x} \right) + x \sum_{j=0}^{e-2} Q_j^{(e)}(x, y). $$

From this and (2.2) we have

$$ S_e(x, y) - \frac{y}{1-x} = x \left( S_e(x, y) - \frac{y}{1-x} - Q_{e-1}^{(e)}(x, y) \right) + xS_e(x, y) \left( S_e(x, y) - \frac{y}{1-x} \right) + \frac{x^2 y}{1-x} S_e(x, y). \quad (2.5) $$

Iterating (2.3), we have $Q_i^{(e)}(x, y)$, with $i \ge 0$, can be expressed as

$$ Q_i^{(e)}(x, y) = \frac{x^{i+2}yS_e(x, y)}{(1-x)(1-xS_e(x, y))^{i+1}}. \qquad (2.6) $$

Substituting (2.6) into (2.5) we obtain the desired functional equation. □

Solving (2.5) for $S_e(x, y)$ we have

$$ S_e(x, y) = \frac{1 - x + xy - \sqrt{1 - 2x + x^2 - 2xy - 2x^2y + x^2y^2 + 4x^2Q_{e-1}^{(e)}(x, y)}}{2x}. \quad (2.7) $$

We observe that substituting (2.7) into (2.1), we have

$$ \begin{aligned} L_e(x, y) &= \frac{xy}{1 - x - xS_e(x, y)} \\ &= \frac{xy}{1 - x - \frac{1 - x + xy - \sqrt{1 - 2x + x^2 - 2xy - 2x^2y + x^2y^2 + 4x^2Q_{e-1}^{(e)}(x, y)}}{2}}. \end{aligned} $$

Since $S_e(x, y)$ is a power series and by (2.6), we obtain that $Q_{e-1}^{(e)}(x, y) \to 0$ as $e \to \infty$, where here we assumed that $|x| < 1$ (for details on convergence of generating functions; see [11, p. 731]). Therefore,

$$ \lim_{e \to \infty} L_e(x, y) = \frac{1 - x - xy - \sqrt{1 - 2x + x^2 - 2xy - 2x^2y + x^2y^2}}{2x}. $$

This last generating function is the distribution of the Narayana sequence. This corroborates with the fact that the restricted $(-\infty)$-Dyck paths coincide with the non-empty Dyck paths.
**Theorem 2.2.** If $1 \le k \le |d| + 3$, then the k-th coefficient of the generating function $L_e(x, 1)$ coincides with the Catalan number $C_k = \frac{1}{k+1} \binom{2k}{k}$.

*Proof.* We first observe that the shortest Dyck path that contains a forbidden sequence of valleys is $P = U^{e+2}DUD^{e+2}UD$ (clearly, $\ell(P) = e + 4$) with $e = |d|$. Therefore, if $d < 0$, then $r_d(n) = C_n$, for $n = 1, 2, \dots, |d| + 3$. □

The first few values for the sequence $r_d(n)$, for $d \in \{-1, -2, -3, -4\}$ are

$$ \{r_{-1}(n)\}_{n \ge 1} = \{1, 2, 5, 14, 41, 123, 375, 1157, 3603, \dots\}, $$

$$ \{r_{-2}(n)\}_{n \ge 1} = \{1, 2, 5, 14, 42, 131, 419, 1365, 4511, \dots\}, $$

$$ \{r_{-3}(n)\}_{n \ge 1} = \{1, 2, 5, 14, 42, 132, 428, 1419, 4785, \dots\}, $$

$$ \{r_{-4}(n)\}_{n \ge 1} = \{1, 2, 5, 14, 42, 132, 429, 1429, 4850, \dots\}. $$

For example, there are 41 (-1)-Dyck paths out of the 42 Dyck paths of length 10. Figure 3 depicts the only Dyck path of length 10 that is not a (-1)-Dyck path.

<figure><img src="image_82.png" /><figcaption>FIGURE 3. The only Dyck path of length 10 that is not a (-1)-Dyck path.</figcaption></figure>

Recall that $d$ is a negative integer and that $e := |d|$. Then by Theorem 2.1, we have

$$ (L_e(x, y) + y)^e (x L_e^2(x, y) + (xy + x - 1)L_e(x, y) + xy) - \frac{x}{1-x}((1-x)L_e(x, y) - xy)(L_e(x, y))^{e+1} = 0. $$

This implies that

$$ \sum_{j=2}^{e+1} x \binom{e}{j-2} y^{e+2-j} (L_e(x, y))^j + \sum_{j=1}^{e+1} (xy + x - 1) \binom{e}{j-1} y^{e+1-j} (L_e(x, y))^j + \sum_{j=0}^{e} x \binom{e}{j} y^{e+1-j} (L_e(x, y))^j + \frac{x^2 y}{1-x} (L_e(x, y))^{e+1} = 0. $$

Hence, by taking $y = 1$ and collecting powers of $L_e(x, 1)$, we have

$$ L_e(x, 1) = Z \left( a_0 + \sum_{j=2}^{e+1} a_j(x) (L_e(x, 1))^j \right), $$
where $Z = 1$, and

$$ 
\begin{aligned}
a_0 &= \frac{x}{1 - (e + 2)x}, \\
a_j &= \frac{1}{1 - (e + 2)x} \left( x \binom{e+2}{j} - \binom{e}{j-1} \right), \quad j = 2, 3, \dots, e, \\
a_{e+1} &= \frac{(e+2)x(1-x) - 1 + x(1+x)}{(1-x)(1-(e+2)x)}.
\end{aligned}
$$

Hence, by the Lagrange inversion formula, we expand the generating function $L_e(x, 1)$ as a power series in $Z$ to obtain

$$ L_e(x, 1) = \sum_{n \ge 1} \frac{[Z^{n-1}]}{n} \sum_{i_0+i_2+i_3+\dots+i_{e+1}=n} \frac{n!}{i_0!i_2!\cdots i_{e+1}!} a_0^{i_0} Z^{2i_2+\cdots+(e+1)i_{e+1}} \prod_{j=2}^{e+1} a_j^{i_j}, $$

that leads to the following result.

**Theorem 2.3.** We have

$$ L_e(x, 1) = \sum_{n \ge 1} \frac{\sum_{2i_2+\cdots+(e+1)i_{e+1}=n-1} \binom{n}{i_2, \dots, i_{e+1}} x^{n-i_2-\cdots-i_{e+1}} t^{i_{e+1}} \prod_{j=2}^{e} \left(x^{\binom{e+2}{j}} - \binom{e}{j-1}\right)^{i_j}}{n(1-(e+2)x)^n}, $$

where

$$ \binom{n}{i_2, \dots, i_{e+1}} = \frac{n!}{i_2! \cdots i_{e+1}! (n - i_2 - \cdots - i_{e+1})!} \quad \text{and} \quad t = \frac{(e+2)x(1-x) - 1 + x(1+x)}{1-x}. $$

For example, Theorem 2.3 with $e = 2$ gives

$$ L_2(x, 1) = \sum_{n \ge 1} \frac{\sum_{2i_2+3i_3=n-1} \binom{n}{i_2, i_3} x^{n-i_2-i_3} (6x-2)^{i_2} \left(\frac{-3x^2+5x-1}{1-x}\right)^{i_3}}{n(1-4x)^n}. $$

Thus,

$$ L_2(x, 1) = \frac{x}{1-4x} + \frac{x^2(6x-2)}{(1-4x)^3} + \frac{x^3t}{(1-4x)^4} + \frac{2x^3(6x-2)^2}{(1-4x)^5} + \frac{5x^4t(6x-2)}{(1-4x)^6} \\ + \frac{5x^4(6x-2)^3 + 3x^5t^2}{(1-4x)^7} + \frac{21x^5(6x-2)^2t}{(1-4x)^8} + \frac{28x^6(-2+6x)t^2 + 14x^5(-2+6x)^4}{(1-4x)^9} + \dots, $$

$$ \text{where } t = \frac{(-3x^2 + 5x - 1)}{(1-x)}. $$

### 3. SOME RESULTS FOR THE CASE $d = -1$

In this section we keep analyzing the bivariate generating function given in the previous section for the particular case $d = -1$. For this case, we provide more detailed results. We denote by $\mathcal{Q}$ the set of all non-empty paths in $\mathcal{D}_{-1}$ having at least one valley, where the last valley is at ground level. We denote by $\mathcal{Q}_n$ the subset of $\mathcal{Q}$ formed by all paths of semi-length $n$ and denote by $q_n$ the cardinality of $\mathcal{Q}_n$. For simplicity, when $d = -1$ (or $e = 1$) we use $L(x, y)$ instead of $L_1(x, y)$. As a consequence of Theorem 2.1, taking $d = -1$, we obtain this theorem.
**Theorem 3.1.** The bivariate generating function $L(x, y)$ is given by

$$L(x, y) = \frac{(x-1)y(1-x(2+y) - \sqrt{(1-x-2xy-2x^2y+x^2y^2-x^3y^2)/(1-x)})}{2(1-2x+x^2-2xy+x^2y)}.$$

Notice that a path $Q \in \mathcal{Q}$ can be uniquely decomposed as either $U\Delta DU\Delta'D$, $U\Delta DR$, $UR_1DR_2$, or $URDU\Delta D$, where $\Delta, \Delta'$ are pyramids, and $R, R_1, R_2 \in \mathcal{Q}$ (see Figure 4 for a graphical representation of this decomposition).

<figure><img src="image_83.png" /><figcaption>FIGURE 4. Decomposition of a (-1)-Dyck path in $\mathcal{Q}$.</figcaption></figure>

Therefore, if

$$Q(x, y) := \sum_{Q \in \mathcal{Q}} x^{\ell(Q)} y^{\rho(P)},$$

then

$$Q(x, y) = x^2 \left( \frac{y}{1-x} \right)^2 + x \left( \frac{y}{1-x} \right) Q(x, y) + x(Q(x, y))^2 + x^2 \left( \frac{y}{1-x} \right) Q(x, y).$$

Solving the equation above for $Q(x, y)$, we find that

$$Q(x, y) = \frac{1 - x - xy - x^2y - \sqrt{(1-x)(1-x-2xy-2x^2y+x^2y^2-x^3y^2)}}{2(1-x)x}. \quad (3.1)$$

Expressing $L(x, y)$ as a series expansion we obtain these first few terms:

$$L(x, y) = xy + x^2 (y^2 + y) + x^3 (y^3 + 3y^2 + y) + x^4 (y^4 + 6y^3 + 6y^2 + y) + x^5 (y^5 + 10y^4 + 19y^3 + 10y^2 + y) + x^6 (y^6 + 15y^5 + 46y^4 + 45y^3 + 15y^2 + y) + \dots$$

Figure 5 depicts all six paths in $D_{-1}(4)$ with exactly 3 peaks. Notice that this is the coefficient of $x^4y^3$, in boldface type, in the above series.

The generating function for the (-1)-Dyck paths is given by

$$L(x) := L(x, 1) = \frac{-1 + 4x - 3x^2 + \sqrt{1 - 4x + 2x^2 + x^4}}{2(1 - 4x + 2x^2)}. \quad (3.2)$$

Thus,

$$L(x) = x + 2x^2 + 5x^3 + 14x^4 + 41x^5 + 123x^6 + 375x^7 + 1157x^8 + \dots.$$
<figure><img src="image_84.png" /><figcaption>FIGURE 5. All six paths in $D_{-1}(4)$ with exactly 3 peaks.</figcaption></figure>

For the sake of simplicity, if there is not ambiguity, for the remaining part of the paper we use $r(n)$ instead of $r_{-1}(n)$. Our interest here is to give a combinatorial formula for this sequence. First of all, we give some preliminary results. Let $b(n)$ be the number of $(-1)$-Dyck paths of semi-length $n$ that either have no valleys or the last valley is at ground level. Note that $b(n) - 1$ is the $n$-th coefficient of the generating function $Q(x, 1)$; see (3.1), or equivalently

$$ \sum_{n \ge 0} b(n) x^n = Q(x, 1) + \frac{1}{1-x} = \frac{1 - x^2 - \sqrt{1 - 4x + 2x^2 + x^4}}{2(1-x)x} \\ = 1 + x + 2x^2 + 4x^3 + 9x^4 + 22x^5 + 57x^6 + 154x^7 + 429x^8 + \dots $$

This generating function coincides with the generating function of the number of Dyck paths of semi-length $n$ that avoid the subpath UUDU. From Proposition 5 of [19] and [5, p. 10] we conclude the following proposition.

**Proposition 3.2.** For all $n \ge 0$ we have

$$ b(n) = 1 + \sum_{j=0}^{\lfloor \frac{n-1}{2} \rfloor} \frac{(-1)^j}{n-j} \binom{n-j}{j} \binom{2n-3j}{n-j+1} = \sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} \sum_{j=0}^{n-k} \binom{n-k}{j} N(j, k), $$

where $N(n, k) = \binom{n}{k} \binom{n}{k-1}$ are the Narayana numbers, with $N(0, 0) = 1$.

We tried to find a combinatorial proof of the previous proposition. However, we were not able to do it. This remark summarizes our observations toward a potential proof. It will be interesting to see such a combinatorial proof.

**Remark 3.3.** Let $\mathcal{B}(n) = \mathcal{Q}_n \cup \{\Delta_n\}$ denote the set of $(-1)$-Dyck paths having either no valleys or the last valley is at ground level. That is, $b(n) = |\mathcal{B}(n)|$. A South-East step in $P \in \mathcal{B}(n)$, satisfies one of these two conditions.

* The step belongs to a pyramid.

* The step is part of a valley, say for example, the $m$-th valley, such that $\nu_m - \nu_{m-1} = -1$. In this case, the valley with height $\nu_m$ is called $(-1)$-valley.
We denote by $\mathcal{B}_{j,k}(n)$ the set of paths in $\mathcal{B}(n)$ with exactly $j$ valleys, where $k$ of them are $(-1)$-valley. Now, a path $P \in \mathcal{B}_{j,k}(n)$ can be decomposed as

$$P = U^{s_0} \Delta_{t_1} U^{s_1} \Delta_{t_2} D^{r_1} U^{s_2} \cdots \Delta_{t_{j-1}} D^{r_{j-2}} U^{s_{j-1}} \Delta_{t_j} D^{r_j} \Delta_{t_{j+1}},$$

where $r_i \in \{0, 1\}$, $t_i \ge 1$, $s_i \ge 0$, and with the additional property that there are exactly $k$ indices $i$ for which $r_i = 1$.

There are $n-k$ South-East steps that belong to one of the $j+1$ pyramids in the path. So, we can represent the possible choices of the $t_i$ as an integer composition of $n-k$ into $j+1$ parts in $\binom{n-k-1}{j+1-1} = \binom{n-k-1}{j}$ ways. This means that setting $t_i = 1$ for all $i$, in the spirit of Proposition 3.2, the Narayana numbers $N(j, k+1)$ should correspond to the number of $(-1)$-Dyck paths of semi-length $j+1+k$ containing exactly $j$ valleys and $k \le j-1$ $(-1)$-valleys where the last valley is at ground level. That is $|\mathcal{B}_{j,k}(j+k+1)| = N(j, k+1)$ for $j > 0$.

**Theorem 3.4.** The total number of paths in $\mathcal{D}_{-1}(n)$ is given by

$$r(n) = \sum_{k=0}^{n} \sum_{i=0}^{n-k-1} \binom{n-k-1}{i} q^{(i)}(k),$$

where

$$q^{(i)}(n) = \sum_{n_1+n_2+\cdots+n_i=n} b(n_1)b(n_2)\cdots b(n_i).$$

*Proof.* Recall that $\ell(P)$ denotes the semi-length of a path $P$. Let us denote by $\mathcal{Q}^{(i)}(n)$ the set of $i$-tuples $(P_1, \dots, P_i)$ of paths $P_j \in \mathcal{B} = \bigcup_{m \ge 0} \mathcal{B}(m)$, such that $\ell(P_1) + \cdots + \ell(P_i) = n$. It is clear that $|\mathcal{Q}^{(i)}(n)| = q^{(i)}(n)$. Note that the empty path $\lambda \in \mathcal{B}$. Let $C_i(n)$ be the set of integer compositions of $n$ with $i$ parts. The cardinality of this set is given by the binomial coefficient $\binom{n-1}{i-1}$.

Let $\mathcal{QC}(n)$ be the set of $(2i+1)$-tuples $(c_1, P_1, \dots, c_i, P_i, c_{i+1})$ such that the element $((P_1, \dots, P_i), (c_1, \dots, c_{i+1}))$ is in $\mathcal{Q}^{(i)}(j) \times C_{i+1}(n-j)$. (Note that $\mathcal{QC}(n)$ is isomorphic to $\bigcup_{i,j} (\mathcal{Q}^{(i)}(j) \times C_{i+1}(n-j))$.) We now consider the function

$$\varphi : \mathcal{QC}(n) \to \mathcal{D}_{-1}(n),$$

defined by

$$\varphi((c_1, P_1, c_2, P_2, \dots, c_i, P_i, c_{i+1})) = U^{c_1} M_1 U^{c_2} \cdots M_i U^{c_{i+1}} D^g,$$

where the integer $g \ge c_{i+1}$ is the number of necessary down-steps to reach the $x$-axis, and $M_j$ is given by

$$M_j = \begin{cases} D^{c_j}, & \text{if } P_j = \lambda; \\ P_j, & \text{if } P_j = \Delta; \\ P_j D, & \text{otherwise.} \end{cases}$$

Figure 6 depicts two examples on the application of the function $\varphi$.
<figure><img src="image_85.png" /><figcaption>FIGURE 6. Function $\varphi$ applied to the vectors $(c_1, \Delta, c_2, \lambda, c_3)$ and $(c_1, P_1, c_2)$.</figcaption></figure>

For the remaining part of this proof we use $\Delta_0 = \lambda$. We define $\phi$ from $D_{-1}(n)$ to $QC(n)$ via the Algorithm 1 below.

<caption>**Algorithm 1 Function $\phi$**</caption>

(1) Let $i = 1$.

(2) If there are $(-1)$-valleys, go to step (3), else, the path is non-decreasing, and for some integers $s_m \ge 0$, $g \ge 0$, and $t_m > 0$, it can be decomposed as

$$P = U^{s_0} \Delta_{t_1} U^{s_1} \Delta_{t_2} \cdots U^{s_{j-1}} \Delta_{t_j} \Delta_{t_{j+1}} D^g.$$

• If no valleys, that is $j = s_0 = g = 0$, then **return** the vector $(t_1)$.

• If there is just one valley, that is $j = 1$, set

$$(s'_0, t'_1) = \begin{cases} (s_0, t_1), & \text{if } s_0 > 0; \\ (t_1, 0), & \text{otherwise;} \end{cases}$$

and then **return** the vector $(s'_0, \Delta_{t'_1}, t_2)$.

• In the general case, set

$$(s'_m, t'_{m+1}) = \begin{cases} (s_m, t_{m+1}), & \text{if } s_m > 0; \\ (t_{m+1}, 0), & \text{otherwise;} \end{cases}$$

for $m < j$ and then **return** the vector $(s'_0, \Delta_{t'_1}, s'_1, \dots, \Delta_{t'_j}, t_{j+1})$.

(3) Find the **rightmost** occurrence of an $(-1)$-valley, that is, a subpath of the form $D\Delta_k DU$, with $k > 0$. Denote the height of this valley as $h_i$. Decompose the path $P$ as $P = \tilde{P}_0 P_i D \tilde{P}_1$, where $P_i$ is the maximal subpath that is a Dyck path to the left of the aforementioned $(-1)$-valley. Notice that $P_i$ ends on $D\Delta_k$ and so, it belongs to $\mathcal{B}$. Let $\hat{P}_0 = \tilde{P}_0 D^{h_i+1}$ and $\hat{P}_1 = \tilde{P}_1 D^{-h_i}$, where $D^{-r}$ means deleting the last $r$ South-East steps of the path. By assumption, the path $\hat{P}_1$ is non-decreasing: go to step (2) using $\hat{P}_1$ and call the returned tuple $\tau_1$. Increase the value of $i$ by one and go to step (2) with the path $\hat{P}_0$ and call the returning tuple $\tau_0$. **Return** $(\tau_0, P_i, \tau_1)$.
We now give an example of the application of the Algorithm 1. Consider, for instance, the path given in Figure 7. First of all, search for the rightmost (-1)-valley (in the first case, it is denoted by dashed circle after $P_1$), they are decorated by a red circle around them, the algorithm applied to $\hat{P}_1 = UD$ (where $\hat{P}_1 = UDD$) gives $\tau_1 = (1)$. We extract the path $P_1$ and we locate the next (-1)-valley, the right part on this instance, given by UDUDU, corresponds to $\tau_1 = (1, \lambda, 1, \lambda, 1)$, and the left part of $P_2$ corresponds to $(1, \Delta_1, 1)$, and so the whole path is encoded by the vector $(1, \Delta_1, 1, P_2, 1, \lambda, 1, \lambda, 1, P_1, 1)$.

<figure><img src="image_86.png" /><figcaption>FIGURE 7. Example inverse function.</figcaption></figure>

Using these decompositions, we show by induction that $\phi \circ \varphi|_{QC_k(n)} = id_{QC_k(n)}$ and $\varphi \circ \phi|_{B_k(n)} = id_{B_k(n)}$ for every $k \ge 0$. These equalities and the functionality of $\phi$, given by choosing the paths $P_i$ in a maximal way, imply that $\varphi$ is a bijection and $\phi$ is its inverse. Let $S(k)$ be the statement

$$ \phi \circ \varphi|_{QC_k(n)} = id_{QC_k(n)} \quad \text{and} \quad \varphi \circ \phi|_{B_k(n)} = id_{B_k(n)}. $$

For the basis step, $S(0)$, first notice that if $P \in B_0(n)$, then the Algorithm 1 Part (2) guarantees that $\phi(P)$ contains only paths of the form $\Delta_t$ for $t \ge 0$. On the other hand, $\varphi$ returns a path without (-1)-valley when given a tuple $\tau \in QC_0(n)$ by definition of the $M_j$'s, and so the functions and their compositions are well defined when restricted to $B_0(n)$ and $QC_0(n)$. Let $P = U^{s_0}\Delta_{t_1} \cdots \Delta_{t_i}\Delta_{t_{i+1}}D^g \in B_0(n)$, using Algorithm 1 we get $\phi(P) = (s'_0, \Delta_{t'_1}, \dots, \Delta_{t'_i}, t_{i+1})$.
Now, we have

$$ \varphi(\phi(P)) = \varphi(s'_0, \Delta_{t_1}, \dots, \Delta_{t'_i}, t_{i+1}) = U^{s'_0} M_1 \cdots M_i U^{t_{i+1}} D^{g'}, $$

with $M_m = D^{s'_{m-1}} = D^{t_m}$ if $t'_m = 0$ and $s'_{m-1} = t_m$, or $M_m = \Delta_{t'_m} = \Delta_{t_m}$ if $s_{m-1} > 0$, for $1 \le m \le i$. This gives $\varphi(\phi(P)) = P$.

Let $\tau = (c_1, \Delta_{t_1}, \dots, c_i, \Delta_{t_i}, c_{i+1})$ with $c_m > 0$ and $t_m \ge 0$, then

$$ \varphi(\tau) = U^{c_1} M_1 \cdots U^{c_i} M_i U^{c_{i+1}} D^g, $$

where

$$ M_m = \begin{cases} D^{c_m}, & \text{if } t_m = 0; \\ \Delta_{t_m}, & \text{otherwise;} \end{cases} $$

and let $1 \le x_1 < x_2 < \dots < x_q \le i$ be such that $t_{x_m} = 0$, that is the paths $\Delta_{t_{x_m}}$ in $\tau$ that are of the form $\Delta_0 = \lambda$. Notice that $c_m > 0$ and the definition of $M_m$ imply that either $U^{c_m} M_m = \Delta_{c_m}$ exactly for $t_m = 0$ or $U^{c_m} \Delta_{t_m}$ for $t_m > 0$, which allows us to decompose $\varphi(\tau)$ as

$$ \varphi(\tau) = (U^{c_1} \Delta_{t_1} \cdots U^{c_{x_1-1}} \Delta_{t_{x_1-1}}) U^0 \Delta_{c_{x_1}} \cdots U^0 \Delta_{c_{x_q}} (U^{c_{x_q+1}} \Delta_{t_{x_q+1}} \cdots \Delta_{t_i}) \Delta_{c_{i+1}} D^{g-c_{i+1}}, $$

where every pyramid in the decomposition is non-empty and so the decomposition is unique. We now have that $\phi(\varphi(\tau)) = (c_1, \Delta_{t_1}, \dots, c_{x_1-1}, \Delta_{t_{x_1-1}}, c_{x_1}, \lambda, \dots, c_{x_q}, \lambda, \dots, c_{i+1}) = \tau$. For the inductive step $S(k)$, we assume that we have the desired equalities for $\ell < k$. Notice that any tuple $\tau \in \mathcal{QC}_k(n)$ can be decomposed as $\tau = (\tau_0, P_1, \tau_1)$ with $\tau_0$ containing $\ell < k$ paths that are not pyramids, $P_1 \neq \Delta_t$ for any $t \ge 0$, and $\tau_1 \in \mathcal{QC}_0(n')$. Notice, further, that

$$ \varphi((\tau_0, P_1, \tau_1)) = \varphi(\tau_0) D^- P_1 D \varphi(\tau_1) D^{g_2}, $$

where $\varphi(\tau_0)D^-$ means deleting the South-East steps suffix of $\varphi(\tau_0)$. By the recursive step in the Algorithm 1, we have that $\phi(\varphi(\tau)) = \tau$ by using the inductive hypothesis. Analogously, we can decompose a path as in the recursive step of Algorithm 1, and the inductive hypothesis give $\varphi(\phi(P)) = P$. $\square$

Proposition 3.5 is a direct consequence of the decomposition given in the proof of Theorem 3.1. The first result follows from Figure 4 and the second result uses the first part of this proposition and the decomposition $UTD, U\Delta DT$, or $UQDT$ as given in the proof of Theorem 3.1.

**Proposition 3.5.** If $n > 1$, then these hold

(1) If $q_n = |\mathcal{Q}_n|$, then

$$ q_n = 2q_{n-1} + q_{n-2} + q_{n-3} + \sum_{i=2}^{n-4} q_i (q_{n-i-1} - q_{n-i-2}) + 1, $$

for $n > 3$, with the initial values $q_1 = 0, q_2 = 1$, and $q_3 = 3$.

(2) If $r(n) = |\mathcal{D}_d(n)|$, then

$$ r(n) = 3r(n-1) - r(n-2) + q_{n-2} + \sum_{i=2}^{n-3} q_i (r(n-i-1) - r(n-i-2)), $$

for $n > 3$, with the initial values $r(1) = 1, r(2) = 2$, and $r(3) = 5$.
The generating function of the sequence $r(n)$ is algebraic of order two, then $r(n)$ satisfies a recurrence relation with polynomial coefficients; see [1, Proposition 4]. This can be automatically solved with implementation of Kauers in *Mathematica* [18]. In particular we obtain that $r(n)$ satisfies the recurrence relation:

$$2nr(n) - 4nr(n + 1) + (12 + 5n)r(n + 2) - 4(15 + 4n)r(n + 3) + 10(9 + 2n)r(n + 4) - 2(21 + 4n)r(n + 5) + (6 + n)r(n + 6) = 0, \quad \text{with } n \ge 6$$

and the initial values $r(0) = 0, r(1) = 1, r(2) = 2, r(3) = 5, r(4) = 14$, and $r(5) = 41$.

In Theorem 3.6 we give an asymptotic approximation for the sequence $r(n)$. To accomplish this goal, we use the singularity analysis method to find the asymptotes of the coefficients of a generating function (see, for example, [11] for the details).

We recall that in literature $f_n \sim g_n$ means that $f_n$ and $g_n$ are asymptotic equivalent. That is, $f_n/g_n \to 1$ as $n \to \infty$.

**Theorem 3.6.** If $\rho$ is the smallest real positive root of $1 - 4x + 2x^2 + x^4$, then the number of $(-1)$-Dyck paths has this asymptotic approximation

$$r(n) \sim \frac{\rho^{-n}}{\sqrt{n^3 \pi}} \cdot \frac{\sqrt{\rho(4 - 4\rho - 4\rho^3)}}{4(-1 + 4\rho - 2\rho^2)},$$

where $\rho$ is called the dominant singularity of the generating function $L(x)$.

*Proof.* From a symbolic computation we find that

$$\rho = \frac{1}{3} \left( -1 - \frac{4 \ 2^{2/3}}{\sqrt[3]{13 + 3\sqrt{33}}} + \sqrt[3]{2 \left( 13 + 3\sqrt{33} \right)} \right) \approx 0.295598.$$

From the expression given in (3.2) for $L(x)$ we have

$$L(x) = \frac{-1 + 4x - 3x^2}{2(1 - 4x + 2x^2)} + \frac{\sqrt{1 - 4x + 2x^2 + x^4}}{2(1 - 4x + 2x^2)} \sim (\rho - x)^{1/2} \frac{\sqrt{\rho(4 - 4\rho - 4\rho^3)}}{2(1 - 4\rho + 2\rho^2)} \quad \text{as } x \to \rho^{-}.$$

Therefore,

$$r(n) \sim \frac{n^{-1/2-1}}{\rho^n(-2\sqrt{\pi})} \frac{\sqrt{\rho(4-4\rho-4\rho^3)}}{2(1-4\rho+2\rho^2)} = \frac{\rho^{-n}}{\sqrt{n^3\pi}} \frac{\sqrt{\rho(4-4\rho-4\rho^3)}}{4(-1+4\rho-2\rho^2)}. \quad \square$$

### 4. THE AREA OF THE $(-1)$-DYCK PATHS

In this section we use generating functions and recursive relations to analyze the distribution of the area of the paths in the set of restricted $(-1)$-Dyck paths. We recall that the *area* of a Dyck path is the sum of the absolute values of $y$-components of all points in the path. We use $\text{area}(P)$ to denote the area of a path $P$. From Figure 1 on Page 118, we can see that $\text{area}(P) = 70$. We use $a(n)$ to denote the total area of all paths in $D_{-1}(n)$. In Theorem 4.1 we give a generating function for the sequence $a(n)$. We now introduce a bivariate generating function depending on this previous parameter and $\ell(P)$ (the semi-length of $P$). So,

$$A(x, q) := \sum_{P \in D_{-1}} x^{\ell(P)} q^{\text{area}(P)}.$$
Let $\mathcal{Q} \subset \mathcal{D}_{-1}(n)$ be the set formed by all paths having at least one valley, where the last valley is at ground level; let $\mathcal{Q}_n \subset \mathcal{Q}$ be the set formed by all paths of semi-length $n$, and let $q_n = |\mathcal{Q}_n|$.

**Theorem 4.1.** The generating function for the sequence $a(n)$ is given by

$$V(x) = \sum_{n \ge 0} a(n) x^n = \frac{b(x) - c(x) \sqrt{1 - 4x + 2x^2 + x^4}}{(1 - x)^2 (1 - 4x + 2x^2)^3 (1 - 3x - x^2 - x^3)},$$

where

$$b(x) = 2x - 23x^2 + 107x^3 - 262x^4 + 359x^5 - 256x^6 + 82x^7 - 5x^8 - 10x^9 + 6x^{10},$$

$$c(x) = x - 10x^2 + 41x^3 - 89x^4 + 108x^5 - 73x^6 + 18x^7 + 2x^8.$$

*Proof.* From the decomposition $UD$, $UTD$, $U\Delta DT$, or $UQDT$ given in the proof of Theorem 3.1 we obtain the functional equation

$$A(x, q) = xq + xqA(xq^2, q) + E(x, q)A(x, q) + xqB(xq^2, q)A(x, q), \quad (4.1)$$

where $E(x, q) := \sum_{j \ge 1} x^j q^{j^2}$ and $B(x, q) := \sum_{P \in \mathcal{Q}} x^{\ell(P)} q^{\text{area}(P)}$. Note that $E(x, q)$ corresponds to the generating function that counts the total number of non-empty pyramids in the given decomposition.

From the decomposition given in Figure 4, we obtain the functional equation

$$B(x, q) = E(x, q)^2 + E(x, q)B(x, q) + xqB(q^2x, q)B(x, q) + xqB(q^2x, q)E(x, q). \quad (4.2)$$

Let $M(x)$ be the generating function of the total area of the $(-1)$-Dyck paths in $\mathcal{Q}$. From the definition of $A(x, q)$ we have

$$V(x) = \left. \frac{\partial A(x, q)}{\partial q} \right|_{q=1}.$$

Substituting $x$ by $xq^2$ in (4.2), and then differentiating with respect to $q$ and taking $q = 1$, we obtain

$$\begin{aligned} W(x) := \left. \frac{\partial B(xq^2, q)}{\partial q} \right|_{q=1} &= \frac{2(3-x)x^2}{(1-x)^4} + \frac{(3-x)x}{(1-x)^3}Q(x) + \frac{x}{1-x} \left( W(x) + 2x \frac{\partial Q(x)}{\partial x} \right) \\ &\quad + 3xQ(x)^2 + xQ(x) \left( W(x) + 4x \frac{\partial Q(x)}{\partial x} \right) + xQ(x) \left( W(x) + 2x \frac{\partial Q(x)}{\partial x} \right) \\ &\quad + \frac{3x^2}{1-x}Q(x) + \frac{x^2}{1-x} \left( W(x) + 4x \frac{\partial Q(x)}{\partial x} \right) + \frac{x^2(3-x)}{(1-x)^3}Q(x), \quad (4.3) \end{aligned}$$

where $Q(x) := Q(x, 1)$ and $Q(x, y)$ is the generating function given in (3.1) on Page 124.

Now, differentiating (4.1) with respect to $q$ and then taking $q = 1$ we obtain,

$$\begin{aligned} V(x) = x + xL(x) &+ x \left( V(x) + 2x \frac{\partial L(x)}{\partial x} \right) + \frac{x(x+1)}{(1-x)^3} L(x) \\ &+ \frac{x}{1-x} V(x) + xQ(x)L(x) + xW(x)L(x) + xQ(x)V(x). \quad (4.4) \end{aligned}$$

Solving (4.3) for $W(x)$ and substituting into (4.4) and then solving the resulting expression for $V(x)$ we obtain the desired result. $\square$
The first few values of the series of $V(x)$ are

$$V(x) = \sum_{n \ge 1} a(n) x^n = x + 6x^2 + 29x^3 + 130x^4 + 547x^5 + 2198x^6 + 8551x^7 + \dots$$

We now give a recursive relation for $a(n)$. Again for the sake of simplicity, the proof here is based on a geometric decomposition of the paths. So, we avoid some details. However, in [13] there are detailed proofs of Proposition 4.2 and Theorem 4.3. We recall that $q_n = |Q_n|$ and that for simplicity we use $r(n)$ instead of $r_{-1}(n)$.

The following two results may follow as a direct application of (4.2). However, we include here a different combinatorial proof.

**Proposition 4.2.** If $A_n$ with $n \ge 1$ is the total area of all paths in $Q_n$, then

$$A_n = 2A_{n-1} + A_{n-2} + 2A_{n-3} + q_n - q_{n-1} + 2nq_{n-2} + 2(n-5)q_{n-3} + 4n^2 - 14n + 13 + \sum_{i=2}^{n-4} 2(A_i + iq_i + i(i+1))(q_{n-i-1} - q_{n-i-2}), \quad \text{with } n > 4,$$

and the initial values $A_1 = 0$, $A_2 = 2$, $A_3 = 13$, and $A_4 = 58$.

*Proof.* From Figure 4 we know that a path in $Q_n$ can be decomposed in one of these four cases; $\Delta_i\Delta_{n-i}$, $\Delta_iQ$, $XQY\Delta_i$, $XQ'YQ$ where $Q, Q' \in Q$

**Case 1.** The area of $\Delta_i\Delta_{n-i}$ is $i^2 + (n-i)^2$. Since for a fixed $i \in \{1, 2, \dots, n-1\}$, there is exactly one path of the form $\Delta_i\Delta_{n-i}$ in $Q_n$, we have that the total area of this type of paths is $\sum_{i=1}^{n-1} (i^2 + (n-i)^2) = n(n-1)(2n-1)/3$.

**Case 2.** The area of $P_i := \Delta_i Q$ is $i^2 + A_{n-i}$. Since for every $i \in \{1, 2, \dots, n-2\}$ there are $q_{n-i}$ paths of the form $P_i$, we have that the total area of all paths of the form $P_i$ is given by $i^2 q_{n-i} + A_i$. Therefore, the total area of this type of paths is $\sum_{i=1}^{n-2} i^2 q_{n-i} + \sum_{j=2}^{n-1} A_j$.

**Case 3.** For a fixed $i$, the area of a path of the form $XQ'YQ''$ is given by $2i + 1 + A_i + A_{n-i-1}$, where $Q' \in Q_i$, $Q'' \in Q_{n-i-1}$ and $i \in \{2, 3, \dots, n-3\}$. Note that for a fixed $i$ and a fixed $Q \in Q_{n-i-1}$ there $q_i$ paths of the form $XQ'YQ$ with $Q \in Q_i$. This implies that for a fixed $i \in \{2, 3, \dots, n-3\}$ the total area of this type of paths is $A_{n-i-1}q_i + (2i+1)q_iq_{n-i-1} + A_iq_{n-i-1}$. We conclude for $i$ varying from 2 to $n-3$, we obtain that the total area of this type of paths is

$$\sum_{i=2}^{n-3} A_{n-i-1}q_i + \sum_{i=2}^{n-3} ((2i+1)q_iq_{n-i-1} + A_iq_{n-i-1}).$$

**Case 4.** The area of $H_i := XQ_iY\Delta_i$ is given by area of $\Delta_i$ (which is $i^2$) plus the area of $XQ_iY$ (this is given by $A_i$, the area of $Q_i$, plus $2i+1$ which is the area of the trapezoid generated by $X$ and $Y$). Since for every $i \in \{1, 2, \dots, n-3\}$ there are $q_{n-i-1}$ paths of the form $H_i$ with $Q \in Q_{n-i}$, we conclude that the total area of this type of paths is

$$\sum_{i=1}^{n-3} i^2 q_{n-i-1} + \sum_{i=2}^{n-2} ((2i+1)q_i + A_i).$$
Adding the results from Cases 1-4, we obtain that the recursive relation for the area $A_n$ is given by

$$A_n = \sum_{i=1}^{n-1} (i^2 + (n-i)^2) + \sum_{i=1}^{n-2} i^2 q_{n-i} + \sum_{i=2}^{n-1} A_i + \sum_{i=2}^{n-3} (2i+1)q_i q_{n-(i+1)} + \sum_{i=2}^{n-3} A_i q_{n-(i+1)} + \\ \sum_{i=2}^{n-3} A_i q_{n-(i+1)} + \sum_{i=2}^{n-2} A_i + \sum_{i=1}^{n-3} i^2 q_{n-(i+1)} + \sum_{i=2}^{n-2} (2i+1)q_i.$$

Subtracting $A_n$ from $A_{n+1}$ and simplifying we have

$$A_n = 2A_{n-1} + A_{n-2} + 2A_{n-3} + (2n-5)q_{n-3} + (2n-4)q_{n-2} + q_{n-1} + 4n^2 - 14n + 15 + \\ \sum_{i=2}^{n-4} (2A_i + (2i+1)q_i)(q_{n-i-1} - q_{n-i-2}) + \sum_{i=2}^{n-3} (2i^2 - 2i + 1)(q_{n-i} - q_{n-i-1}).$$

We now rearrange this expression to obtain $q_n$ (see the expression within brackets) given in Proposition 3.5

$$A_n = 2A_{n-1} + A_{n-2} + 2A_{n-3} + (2n-6)q_{n-3} + (2n-4)q_{n-2} - q_{n-1} + 4n^2 - 14n + 13 + \\ \sum_{i=2}^{n-4} 2(A_i + iq_i)(q_{n-i-1} - q_{n-i-2}) + \sum_{i=2}^{n-3} 2(i^2 - i)(q_{n-i} - q_{n-i-1}) + \\ + [2q_{n-1} + q_{n-2} + q_{n-3} + \sum_{i=2}^{n-4} q_i(q_{-i+n-1} - q_{-i+n-2}) + 1].$$

After some simplifications we obtain the desired recursive relation. □

The proof of the following theorem is similar to the proof of Proposition 4.2. We recall that $r(i) = |\mathcal{D}_{-1}(i)|$ and $q_j = |\mathcal{Q}_j|$. □

**Theorem 4.3.** If $a(n)$ is the total area of all paths in $\mathcal{D}_{-1}(n)$, for $n \ge 1$, then $a(n)$ satisfies the recursive relation

$$a(n) = 3a(n-1) - a(n-2) + A_{n-2} + 2(n-1)q_{n-2} + 2nr(n-1) + 2(3-n)r(n-2) \\ - 4r(n-3) + (n-1)^2 + \sum_{i=3}^{n-2} q_{i-1}(a(n-i) - a(n-i-1)) \\ + \sum_{i=3}^{n-2} (A_{i-1} + (2i-1)q_{i-1} + i^2)(r(n-i) - r(n-i-1)).$$

*Proof.* First of all, we note that a path in $\mathcal{D}_{-1}(n)$ can be decomposed as $XQ_1Y$, $\Delta_i Q_{n-i}$, and $XQ'YD$, where $Q_j, D \in \mathcal{D}_{-1}$, and $Q' \in \mathcal{Q}_j$. This decomposition gives these three cases to consider.

**Case 1.** The area of $XQY$ is $(2n-1) + a(n-1)$, where $a(n-1)$ is the area of $Q \in \mathcal{D}_{-1}(n-1)$ and $2n-1$ is the area of the trapezoid generated by $X$ and $Y$. This gives that the total area of all paths of the form $XQY$ with $Q \in \mathcal{D}_{-1}(n-1)$ is $(2n-1)r(n-1)+a(n-1)$.

**Case 2.** The area of $K_i := X^i Y^i Q_\ell$ is $i^2 + a(n-i)$, where $Q_\ell \in \mathcal{D}_{-1}(n-i)$. Since for a fixed $i \in \{1, 2, \dots, n-1\}$ there are $r(n-i)$ paths of form $K_i$, we conclude that the total area of all these paths is $\sum_{i=1}^{n-1} i^2 r(n-i) + a(n-i)$. □
**Case 3.** The area of $M_i := XQ'YD$ is $((2i+1)+A_i+a(n-i-1)$, where $Q' \in Q_i$ and $D \in D_{-1}(n-i-1)$. Note that for a given path $D \in D_{-1}(n-i-1)$, there are as many paths of the form $XQ'YD$ as paths in $Q_i$. It is easy to see that for a fixed $i \in \{2, 3, \dots, n-2\}$ there are $r(n-i-1)$ subpaths of the form $XQ'Y$. Note that $X$ and $Y$ give rise to a trapezoid, where the two parallel sides have lengths $2i$ and $2i+2$, giving rise to an area of $2i+1$. So, the contribution to the area given by the first subpaths of the form $XQ'Y$ is equal to the area of the trapezoids plus the area of all paths of the form $Q'$ (these are on top of the trapezoids). Thus, the area of a trapezoid multiplied by the total number of the paths of the form $Q'$ plus the area of all paths of the form $Q'$ and then all of these multiplied by the total number of paths of the form $D$. Thus, the contribution to the area given by the first subpaths of the form $XQ'Y$ (overall paths of the form $M_i$ for a fixed $i$), is $((2i+1)q_i r(n-i-1)+A_i r(n-i-1))$.

We conclude that the total area of this type of paths is

$$ \sum_{i=2}^{n-2} A_i r(n-i-1) + \sum_{i=2}^{n-2} (2i+1)q_i r(n-i-1). $$

Adding the results from Cases 1-3, we obtain that the recursive relation for the area $a(n)$ is given by

$$ a(n) = a(n-1) + (2n-1)r(n-1) + \sum_{i=1}^{n-1} i^2 r(n-i) + \sum_{i=1}^{n-1} a(n-i) \\ + \sum_{i=2}^{n-2} q_i a(n-i-1) + \sum_{i=2}^{n-2} A_i r(n-i-1) + \sum_{i=2}^{n-2} (2i+1) q_i r(n-i-1). $$

Subtracting $a(n)$ from $a(n+1)$ and simplifying we have

$$ a(n) = 3a(n-1) - a(n-2) + A_{n-2} + 2(n-1)q_{n-2} + (2n-1)r(n-1) + (3-2n)r(n-2) + (n-1)^2 \\ + \sum_{i=3}^{n-2} q_{i-1}(a(n-i) - a(n-i-1)) + \sum_{i=3}^{n-2} A_{i-1}(r(n-i) - r(n-i-1)) \\ + \sum_{i=3}^{n-2} (2i-1)q_{i-1}(r(n-i) - r(n-i-1)) + \sum_{i=1}^{n-2} i^2(r(n-i) - r(n-i-1)). $$

After some other simplifications we have that

$$ a(n) = 3a(n-1) - a(n-2) + A_{n-2} + 2(n-1)q_{n-2} + 2nr(n-1) \\ + 2(3-n)r(n-2) - 4r(n-3) + (n-1)^2 + \sum_{i=3}^{n-2} q_{i-1}(a(n-i) - a(n-i-1)) \\ + \sum_{i=3}^{n-2} (A_{i-1} + (2i-1)q_{i-1} + i^2) (r(n-i) - r(n-i-1)). $$

This completes the proof.

<figure><img src="image_87.png" /></figure>

Notice that the total area of the Dyck paths (cf. [21]) is given by $4^n - \binom{2n+1}{n}$.
## 5. APPENDIX. NOTATION TABLE

<table><caption>TABLE 1. Summary of notation.</caption><thead><tr><td>Concept</td><td>Notation</td></tr></thead><tbody><tr><td>Set restricted d-Dyck paths</td><td>D<sub>d</sub></td></tr><tr><td>Set restricted d-Dyck paths of length n</td><td>D<sub>n</sub></td></tr><tr><td>Cardinality of D<sub>d</sub>(n)</td><td>r<sub>d</sub>(n)</td></tr><tr><td>Cardinality of D<sub>-1</sub>(n)</td><td>r<sub>-1</sub>(n) or r(n)</td></tr><tr><td>Area of a path P</td><td>area(P)</td></tr><tr><td>Semi-length of P</td><td>l(P)</td></tr><tr><td>Number of peaks of P</td><td>ρ(P)</td></tr><tr><td>Number of paths in D<sub>d</sub>(n) having exactly k peaks.</td><td>p<sub>d</sub>(n, k)</td></tr><tr><td>Paths with the last valley at level i</td><td>Q<sub>d,i</sub></td></tr><tr><td>General pyramid</td><td>Δ</td></tr><tr><td>Pyramid (XY)<sup>k</sup></td><td>Δ<sub>k</sub></td></tr></tbody></table>

**Acknowledgments.** The authors are grateful to the referees and the editor for the helpful suggestions and comments. The first author was partially supported by The Citadel Foundation. The third author was partially supported by Universidad Nacional de Colombia. The last author thanks the ANTA group at Aalto University where part of the presented work was written.

## REFERENCES

[1] Cyril Banderier and Michael Drmota. Formulae and asymptotics for coefficients of algebraic functions. *Combin. Probab. Comput.*, 24(1):1–53, 2015.

[2] Cyril Banderier and Philippe Flajolet. Basic analytic combinatorics of directed lattice paths. *Theor. Comput. Sci.*, 281:37–80, 2002.

[3] Cyril Banderier and Bernhard Gittenberger. Analytic combinatorics of lattice paths: enumeration and asymptotics for the average area. In *Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities*, pages 345–356. Discrete Math. Theor. Comput. Sci., 2006.

[4] Elena Barcucci, Alberto Del Lungo, Stefano Fezzi, and Renzo Pinzani. Nondecreasing Dyck paths and q-Fibonacci numbers. *Discrete Math.*, 170:211–217, 1997.

[5] Paul Barry. Riordan pseudo-involutions, continued fractions and Somos-4 sequences. *J. Integer Seq.*, 22:Article 19.6.1, 2019.

[6] Éva Czabarka, Rigoberto Flórez, and Leandro Junes. Some enumerations on non-decreasing Dyck paths. *Electron. J. Comb.*, 22(1):# P1.3, 1–22, 2015.

[7] Éva Czabarka, Rigoberto Flórez, Leandro Junes, and José L. Ramírez. Enumerations of peaks and valleys on non-decreasing Dyck paths. *Discrete Math.*, 341:2789–2807, 2018.

[8] Emeric Deutsch. Dyck path enumeration. *Discrete Math.*, 204:167–202, 1999.

[9] Emeric Deutsch and Helmut Prodinger. A bijection between directed column-convex polyominoes and ordered trees of height at most three. *Theor. Comput. Sci.*, 307:319–325, 2003.

[10] Sergi Elizalde, Rigoberto Flórez, and José L. Ramírez. Enumerating symmetric peaks in non-decreasing Dyck paths. *Ars Math. Contemp.*, 21(2):# P2.04, 2021.

[11] Philippe Flajolet and Robert Sedgewick. *Analytic Combinatorics*. Cambridge University Press, 2009.

[12] Rigoberto Flórez, Leandro Junes, and José L. Ramírez. Enumerating several aspects of non-decreasing Dyck paths. *Discrete Math.*, 342(11):3079–3097, 2019.
[13] Rigoberto Flórez, Toufik Mansour, José L. Ramírez, Fabio A. Velandia, and Diego Villamizar. *Restricted Dyck paths on valleys sequence*. arXiv, 2021.

[14] Rigoberto Flórez and José L. Ramírez. *Some enumerations on non-decreasing Motzkin paths*. *Australas. J. Comb.*, 72:138–154, 2018.

[15] Rigoberto Flórez and José L. Ramírez. *Enumerations of rational non-decreasing Dyck paths with integer slope*. *Graphs Comb.*, 37(6):2775–2801, 2021.

[16] Rigoberto Flórez, José L. Ramírez, Fabio A. Velandia, and Diego Villamizar. *Some connections between restricted Dyck paths, polyominoes, and non-crossing partitions*. In *Proceedings of the 52nd Southeastern International Conference on Combinatorics, Graph Theory & Computing*. To appear in Springer Proceedings in Mathematics & Statistics, 2021.

[17] Rigoberto Flórez, José L. Ramírez, Fabio A. Velandia, and Diego Villamizar. *A refinement of Dyck paths: a combinatorial approach*. *Discrete Math. Algorithms Appl.*, 14(7), 2022.

[18] Manuel Kauers. *Guessing handbook*. *Technical Report 09-07, RISC-Linz*, 2009.

[19] Aristidis Sapounakis, Ioannis Tasoulas, and Panagiotis Tsikouras. *Ordered trees and the inorder traversal*. *Discrete Math.*, 306(15):1732–1741, 2006.

[20] Aristidis Sapounakis and Panagiotis Tsikouras. *Counting peaks and valleys in *k*-colored Motzkin paths*. *Electron. J. Comb.*, 12:R#16, 2005.

[21] Wen-jin Woan. *Area of Catalan paths*. *Discrete Math.*, 226(15):439–444, 2001.
# COUNTING LATTICE PATHS
## BY CROSSINGS AND MAJOR INDEX II:
## TRACKING DESCENTS VIA TWO-ROWED ARRAYS

SERGI ELIZALDE¹

¹DARTMOUTH COLLEGE, HANOVER, USA; https://math.dartmouth.edu/~sergi

**Abstract.** We present refined enumeration formulas for lattice paths in $\mathbb{Z}^2$ with two kinds of steps, by keeping track of the number of descents (i.e., turns in a given direction), the major index (i.e., the sum of the positions of the descents), and the number of crossings. One formula considers crossings between a path and a fixed line; the other considers crossings between two paths. Building on the first paper of the series, which used lattice path bijections to give the enumeration with respect to major index and crossings, we obtain a refinement that keeps track of the number of descents. The proof is based on new bijections which rely on certain two-rowed arrays that were introduced by Krattenthaler.

**Keywords:** lattice path, major index, crossings, descents, bijection.

## 1. INTRODUCTION

1.1. **Background.** Lattice paths in the plane with two kinds of steps have played an important role in combinatorics and mathematical statistics for decades [14, 19]. The statistic giving the number of times that a path crosses a fixed line has been studied at least since the sixties [4–6, 10, 21, 23], often in connection to random walks. For tuples of paths, the enumeration in the special case of non-crossing tuples, in its closely related non-intersecting variant, is given by the celebrated Lindström–Gessel–Viennot determinant [9, 17], and has applications to symmetric functions, plane partitions, tilings, and statistical physics [7].

On the other hand, a very different statistic, the sum of the positions of the turns in a given direction, has been studied in [12, 15, 20]. This statistic is called the *major index* because it arises naturally when interpreting the paths as binary words, and it was introduced by MacMahon [18].

In the first paper of this series [3], we enumerated paths with respect to the number of crossings of a line and the major index, as well as pairs of paths with respect to the number of times they cross each other and the sum of their major indices. The goal of the present paper is to refine the results from [3] by another important statistic, which is related to the major index and arguably more natural: the number of turns in a given direction, or equivalently, the number of descents of the associated binary word.
The number of turns arises when studying the distribution of runs in random walks [19], the coefficients of Hilbert polynomials of determinantal and Pfaffian rings [16], and summations for Schur functions [12]. A thorough investigation of this parameter on lattice paths was provided by Krattenthaler [13]. In particular, a refinement by this statistic of the classical determinantal formula of Lindström–Gessel–Viennot [9, 17] counting tuples of non-intersecting paths was given in [11, Thm. 1] and [13, Thm. 3.6.1]. In related work, Krattenthaler and Mohanty [15] enumerated lattice paths constrained to a strip with respect to the number of descents and the major index.

The tools that were used in [3] to deal with crossings and the major index consisted of bijections with a neat description in terms of lattice paths. While these bijections were suited to study the major index, unfortunately they do not behave well with respect to the number of descents, which is why the results obtained in [3] do not include this statistic. Instead, in this paper we will construct different bijections that are not described in terms of paths, but rather in terms of two-rowed arrays.

Such arrays, which are more general than paths, have been used by Krattenthaler and Mohanty to study descents and major index on lattice paths in a strip [15], and by Krattenthaler to enumerate tuples of non-intersecting paths with respect to the number of turns [11,13] and to the major index [12]. However, to our knowledge, they have never been used while also keeping track of the number of crossings. While two-rowed arrays allow us to track simultaneously track multiple statistics, including the number of descents, the trade-off is that they make the proofs more involved and less intuitive than those in [3].

Paralleling the results in [3], this paper solves two problems: the enumeration of single paths with respect to the number of times that they cross a fixed line, and the enumeration of pairs of paths with respect to the number of times that they cross each other, refined in both cases by the number of descents and the major index. This paper is self-contained and does not rely on any material from [3].

Our work is partially motivated by the simplicity of the resulting formulas in both cases. For single paths with given endpoints, crossing a line at least a certain number of times and having a fixed number of descents, we will show that the polynomial enumerating them with respect to the major index is given by a product of two $q$-binomial coefficients and a power of $q$. For pairs of paths crossing each other, the formulas we obtain involve a product of two generating functions whose coefficients have again the same form.

The second source of motivation is that our results for paths crossing a line have applications to the refined enumeration of integer partitions according to the number of sign changes of their successive ranks (or off-diagonal ranks). These applications, which generalize results of Seo and Yee [22], will be explored in [2] in connection to the study of partitions with constrained ranks.

## 1.2. Preliminaries.
For points $A, B \in \mathbb{Z}^2$, we denote by $P_{A \to B}$ the set of lattice paths with steps $N = (0, 1)$ (north) and $E = (1, 0)$ (east) that start at $A$ and end at $B$. Sometimes it will be convenient to consider paths with steps $U = (1, 1)$ (up) and $D = (1, -1)$ (down) instead. For nonnegative integers $a, b$, we denote by $G_{a,b}$ set of paths with $a$ steps $U$ and $b$ steps $D$ starting at the origin.
<figure><img src="image_88.png" /><figcaption>FIGURE 1. A path $P \in \mathcal{G}_{8,6}^{\ge 3,1}$ with $\mathrm{maj}(P) = 1+3+7+10 = 21$. The four valleys are marked with teal diamonds, and the three crossings of the line $y=1$ are circled in black. The middle crossing is a downward crossing, whereas the other two are upward crossings.</figcaption></figure>

In both cases, encoding paths as binary words, with 0s recording $N$ (resp. $U$) steps, and 1s recording $E$ (resp. $D$) steps, we define a descent (also called a *valley*) of the path to be a vertex preceded by an $E$ and followed by an $N$ (resp. preceded by a $D$ and followed by a $U$). The number of descents of a path $P$ is denoted by $\mathrm{des}(P)$. The major index of $P$, denoted by $\mathrm{maj}(P)$, is defined to be the sum of the positions of the descents, where the position is determined by numbering the vertices along the path, starting at 0. See Figure 1 for an example. We also define a *peak* of the path to be a vertex preceded by an $N$ and followed by an $E$ (resp. preceded by a $U$ and followed by a $D$).

The enumeration of binary words by the number of descents and the major index is implicit in work of MacMahon [18]. An explicit proof was given by Fürlinger and Hofbauer [8]. To state this result in its lattice path version, recall that the *q-binomial coefficients* are defined as

$$ \begin{bmatrix} m \\ n \end{bmatrix}_q = \prod_{k=0}^{n-1} \frac{1 - q^{m-k}}{1 - q^{n-k}} $$

if $0 \le n \le m$, and as 0 otherwise.

**Lemma 1.1** ([8, 18]). For $a, b \ge 0$,

$$ \sum_{P \in \mathcal{G}_{a,b}} t^{\mathrm{des}(P)} q^{\mathrm{maj}(P)} = \sum_{n \ge 0} t^n q^{n^2} \begin{bmatrix} a \\ n \end{bmatrix}_q \begin{bmatrix} b \\ n \end{bmatrix}_q . $$

Equivalently, for $x, y, u, v \in \mathbb{Z}$,

$$ \sum_{P \in \mathcal{P}_{(x,y) \to (u,v)}} t^{\mathrm{des}(P)} q^{\mathrm{maj}(P)} = \sum_{n \ge 0} t^n q^{n^2} \begin{bmatrix} u-x \\ n \end{bmatrix}_q \begin{bmatrix} v-y \\ n \end{bmatrix}_q . $$

A self-contained proof of this lemma will be included in Section 3.1. The rest of the paper is structured as follows. In Section 2 we state our results, both for single paths crossing a line and for pairs of paths crossing each other. In Section 3 we prove them in the case of single paths crossing a line, by introducing two-rowed arrays to encode paths, generalizing the notion of crossings to such arrays, and then describing certain bijections on them. In Section 4 we prove our results for pairs of paths crossing each other, by generalizing crossings to pairs of two-rowed arrays, and then defining bijections on such pairs.
## 2. MAIN RESULTS

### 2.1. Paths crossing a line.
First we consider the enumeration of paths with $U$ and $D$ steps according to the number of times that they cross a fixed horizontal line. For integers $\ell, r$ with $r \ge 0$, let $G_{a,b}^{\ge r, \ell}$ denote the set of paths in $G_{a,b}$ that cross the line $y = \ell$ at least $r$ times. A vertex of the path on the line $y = \ell$ is a crossing if it is either preceded and followed by a $D$ —in which case it is called a downward crossing—, or preceded and followed by a $U$ —called an upward crossing. See Figure 1 for an example.

We will provide expressions for the polynomials

$$G_{a,b}^{\ge r, \ell}(t, q) = \sum_{P \in \mathcal{G}_{a,b}^{\ge r, \ell}} t^{\text{des}(P)} q^{\text{maj}(P)}$$

for arbitrary integers $a, b, r, \ell$ with $a, b, r \ge 0$. Note that the polynomials for paths crossing the line $y = \ell$ exactly $r$ times can be obtained from the above simply as $G_{a,b}^{\ge r, \ell}(t, q) - G_{a,b}^{\ge r+1, \ell}(t, q)$.

An expression for $G_{a,b}^{\ge r, \ell}(1, q)$ was given in [3, Thms. 2.1 and 2.2]. The following result refines these theorems by incorporating the statistic des.

**Theorem 2.1.** Let $a, b, m \ge 0$, and let $\ell \in \mathbb{Z}$.

I. If $0 < \ell < a - b$, then

$$G_{a,b}^{\ge 2m+1, \ell}(t, q) = G_{a,b}^{\ge 2m, \ell}(t, q) = \sum_{n \ge 0} t^n q^{n^2+m(m+\ell+1)} \begin{bmatrix} a \\ n-m \end{bmatrix}_q \begin{bmatrix} b \\ n+m \end{bmatrix}_q. \quad (2.1)$$

II. If $0 > \ell > a - b$, then

$$G_{a,b}^{\ge 2m+1, \ell}(t, q) = G_{a,b}^{\ge 2m, \ell}(t, q) = \sum_{n \ge 0} t^n q^{n^2+m(m-\ell-1)} \begin{bmatrix} a \\ n+m \end{bmatrix}_q \begin{bmatrix} b \\ n-m \end{bmatrix}_q. \quad (2.2)$$

III. If $0 > \ell < a - b$, then

$$G_{a,b}^{\ge 2m+2, \ell}(t, q) = G_{a,b}^{\ge 2m+1, \ell}(t, q) = \sum_{n \ge 0} t^n q^{n^2+(m+1)(m-\ell)} \begin{bmatrix} a-\ell-1 \\ n-m-1 \end{bmatrix}_q \begin{bmatrix} b+\ell+1 \\ n+m+1 \end{bmatrix}_q. \quad (2.3)$$

IV. If $0 < \ell > a - b$, then

$$G_{a,b}^{\ge 2m+2, \ell}(t, q) = G_{a,b}^{\ge 2m+1, \ell}(t, q) = \sum_{n \ge 0} t^n q^{n^2+m(m+\ell+1)} \begin{bmatrix} a-\ell-1 \\ n+m \end{bmatrix}_q \begin{bmatrix} b+\ell+1 \\ n-m \end{bmatrix}_q. \quad (2.4)$$

V. If $0 = \ell < a - b$, then

$$G_{a,b}^{\ge 2m, \ell}(t, q) = \sum_{n \ge 0} t^n q^{n^2+m(m+1)} \begin{bmatrix} a \\ n-m \end{bmatrix}_q \begin{bmatrix} b \\ n+m \end{bmatrix}_q, \quad (2.5)$$

$$G_{a,b}^{\ge 2m+1, \ell}(t, q) = \sum_{n \ge 0} t^n q^{n^2+m(m+1)} \begin{bmatrix} a-1 \\ n-m-1 \end{bmatrix}_q \begin{bmatrix} b+1 \\ n+m+1 \end{bmatrix}_q. \quad (2.6)$$
VI. If $0 = \ell > a - b$, then

$$G_{a,b}^{\ge 2m, \ell}(t, q) = \sum_{n \ge 0} t^n q^{n^2+m(m-1)} \begin{bmatrix} a \\ n+m \end{bmatrix}_q \begin{bmatrix} b \\ n-m \end{bmatrix}_q, \qquad (2.7)$$

$$G_{a,b}^{\ge 2m+1, \ell}(t, q) = \sum_{n \ge 0} t^n q^{n^2+m(m+1)} \begin{bmatrix} a-1 \\ n+m \end{bmatrix}_q \begin{bmatrix} b+1 \\ n-m \end{bmatrix}_q. \qquad (2.8)$$

VII. If $0 < \ell = a - b$, then

$$G_{a,b}^{\ge 2m, \ell}(t, q) = \sum_{n \ge 0} t^n q^{n^2+m(m+\ell+1)} \begin{bmatrix} a \\ n-m \end{bmatrix}_q \begin{bmatrix} b \\ n+m \end{bmatrix}_q, \qquad (2.9)$$

$$G_{a,b}^{\ge 2m+1, \ell}(t, q) = \sum_{n \ge 0} t^n q^{n^2+m(m+\ell+1)} \begin{bmatrix} a+1 \\ n-m \end{bmatrix}_q \begin{bmatrix} b-1 \\ n+m \end{bmatrix}_q. \qquad (2.10)$$

VIII. If $0 > \ell = a - b$, then

$$G_{a,b}^{\ge 2m, \ell}(t, q) = \sum_{n \ge 0} t^n q^{n^2+m(m-\ell-1)} \begin{bmatrix} a \\ n+m \end{bmatrix}_q \begin{bmatrix} b \\ n-m \end{bmatrix}_q, \qquad (2.11)$$

$$G_{a,b}^{\ge 2m+1, \ell}(t, q) = \sum_{n \ge 0} t^n q^{n^2+(m+1)(m-\ell)} \begin{bmatrix} a+1 \\ n+m+1 \end{bmatrix}_q \begin{bmatrix} b-1 \\ n-m-1 \end{bmatrix}_q. \qquad (2.12)$$

IX. If $0 = \ell = a - b$, then

$$G_{a,b}^{\ge 2m, \ell}(t, q) = \sum_{n \ge 0} t^n q^{n^2+m(m+1)} \frac{1-q^{a-2m}}{1-q^a} \begin{bmatrix} a \\ n+m \end{bmatrix}_q \begin{bmatrix} a \\ n-m \end{bmatrix}_q, \qquad (2.13)$$

$$G_{a,b}^{\ge 2m+1, \ell}(t, q) = \sum_{n \ge 0} t^n q^{n^2+m(m+1)} \frac{1-q^{a+2(m+1)}}{1-q^a} \begin{bmatrix} a \\ n+m+1 \end{bmatrix}_q \begin{bmatrix} a \\ n-m-1 \end{bmatrix}_q. \qquad (2.14)$$

2.2. **Pairs of paths crossing each other.** Next we consider the enumeration pairs of paths with respect to the number of crossings between them. For this problem it is convenient to consider paths with $N$ and $E$ steps. Let $P$ and $Q$ be two such paths, and suppose that $V_1, V_2, \dots, V_s$ (where $s \ge 1$) is a maximal sequence of consecutive common vertices such that

* neither $V_1$ nor $V_s$ are endpoints of $P$ or $Q$;

* for each of $P$ and $Q$, its step arriving at $V_1$ is of the same type ($N$ or $E$) as its step leaving $V_s$.
In this case, vertex $V_s$ is called a crossing of $P$ and $Q$. This definition differs slightly from the one used in [3], where the term crossing refers to the first vertex $V_1$ of the sequence. Of course, the number of crossings of $P$ and $Q$ does not depend on this convention, but defining the crossing to be $V_s$ will be more convenient in the proofs in Section 4. Figure 2 shows some examples of crossings.

<figure><img src="image_89.png" /><figcaption>FIGURE 2. Two examples of crossings, circled in black, and a pair of paths that do not cross (right).</figcaption></figure>

Let $\chi(P, Q)$ denote the number of crossings of $P$ and $Q$; see Figure 3 for an example.

<figure><img src="image_90.png" /><figcaption>FIGURE 3. A pair of paths with $\chi(P, Q) = 3$, $\text{des}(P) + \text{des}(Q) = 6$, and $\text{maj}(P) + \text{maj}(Q) = 45$.</figcaption></figure>

For $A_1, A_2, B_1, B_2 \in \mathbb{Z}^2, r \ge 0$, and $\{\circ, \bullet\} = \{1, 2\}$, let

$$ \mathcal{P}_{A_1 \to B_0, A_2 \to B_\bullet}^{\ge r} = \{(P, Q) : P \in \mathcal{P}_{A_1 \to B_0}, Q \in \mathcal{P}_{A_2 \to B_\bullet}, \chi(P, Q) \ge r\}. $$

To enumerate such pairs of paths with respect to the sum of their numbers of descents (the *total descent number*) and the sum of their major indices (the *total major index*), we define the polynomials

$$ H_{A_1 \to B_0, A_2 \to B_\bullet}^{\ge r}(t, q) = \sum_{(P,Q) \in \mathcal{P}_{A_1 \to B_0, A_2 \to B_\bullet}^{\ge r}} t^{\text{des}(P)+\text{des}(Q)} q^{\text{maj}(P)+\text{maj}(Q)}. $$

Note that the polynomials for pairs of paths that cross each other *exactly* $r$ times are given by the difference $H_{A_1 \to B_0, A_2 \to B_\bullet}^{\ge r}(t, q) - H_{A_1 \to B_0, A_2 \to B_\bullet}^{\ge r+1}(t, q)$.
To state our formulas, let us first define the following polynomial in $t$ and $q$ that depends on the points $A_1 = (x_1, y_1)$, $A_2 = (x_2, y_2)$, $B_1 = (u_1, v_1)$, $B_2 = (u_2, v_2)$, and a parameter $k \in \mathbb{Z}$:

$$f_{k,A_1,A_2,B_2,B_1}(t,q) = q^{k(k+x_2-x_1)} \left( \sum_{n \ge 0} t^n q^{n(n+k)} \begin{bmatrix} u_2 - x_1 \\ n \end{bmatrix}_q \begin{bmatrix} v_2 - y_1 \\ n+k \end{bmatrix}_q \right) \left( \sum_{n \ge 0} t^n q^{n(n-k)} \begin{bmatrix} u_1 - x_2 \\ n \end{bmatrix}_q \begin{bmatrix} v_1 - y_2 \\ n-k \end{bmatrix}_q \right).$$

We use the notation $A_1 \prec A_2$ to mean that $x_1 < x_2$ and $y_1 > y_2$. The theorem below refines [3, Thm. 2.4].

**Theorem 2.2.** Let $A_1 = (x_1, y_1)$, $A_2 = (x_2, y_2)$, $B_1 = (u_1, v_1)$ and $B_2 = (u_2, v_2)$ be points in $\mathbb{Z}^2$ such that $A_1 \prec A_2$ and $B_1 \prec B_2$. Suppose additionally that

$$x_1 + y_1 = x_2 + y_2. \qquad (2.15)$$

Then, for all $m \ge 0$,

$$H_{A_1 \to B_2, A_2 \to B_1}^{\ge 2m+1}(t,q) = H_{A_1 \to B_2, A_2 \to B_1}^{\ge 2m}(t,q) = f_{2m, A_1, A_2, B_2, B_1}(t,q), \qquad (2.16)$$

$$H_{A_1 \to B_1, A_2 \to B_2}^{\ge 2m+2}(t,q) = H_{A_1 \to B_1, A_2 \to B_2}^{\ge 2m+1}(t,q) = f_{2m+1, A_1, A_2, B_2, B_1}(t,q). \qquad (2.17)$$

Let now $A = (x, y)$ and $B = (u, v)$ be points in $\mathbb{Z}^2$. Then, for all $r \ge 0$,

$$H_{A \to B_1, A \to B_2}^{\ge r}(t,q) = f_{r, A, A, B_2, B_1}(t,q), \qquad (2.18)$$

$$H_{A_1 \to B, A_2 \to B}^{\ge r}(t,q) = f_{r, A_1, A_2, B, B}(t,q), \qquad (2.19)$$

$$H_{A \to B, A \to B}^{\ge r}(t,q) = \begin{cases} f_{0, A, A, B, B}(t,q) & \text{if } r=0, \\ 2 \sum_{j \ge 1} (-1)^{j-1} f_{r+j, A, A, B, B}(t,q) & \text{if } r \ge 1. \end{cases} \qquad (2.20)$$

Let us now detail the proofs of these results.
### 3. PROOFS FOR PATHS CROSSING A LINE

In this section we prove Theorem 2.1. Before diving into the details, we remark that it would be possible to give an alternative proof by induction on the length (number of steps) of the path, by first separating each of the nine cases of the theorem into two subcases, according to whether the last step of the path is a $U$ or a $D$. For example, if $0 < l < a - b$, the refinement to be proved by induction would state that the generating function for paths in $G_{a,b}^{\ge r, l}$ that end with a $D$, where $r = 2m$ or $r = 2m + 1$, equals

$$G_{a,b-1}^{\ge r, l}(t, q) = \sum_{n \ge 0} t^n q^{n^2+m(m+1+l)} \begin{bmatrix} a \\ n-m \end{bmatrix}_q \begin{bmatrix} b-1 \\ n+m \end{bmatrix}_q,$$

and so the generating function for those that end with a $U$ equals

$$G_{a,b}^{\ge r, l}(t, q) - G_{a,b-1}^{\ge r, l}(t, q) = \sum_{n \ge 0} t^n q^{n^2+m(m+l)+b-n} \begin{bmatrix} a \\ n-m \end{bmatrix}_q \begin{bmatrix} b-1 \\ n+m-1 \end{bmatrix}_q.$$

Then, to prove each one of these formulas, we would remove the last step of the path, and deduce them from the formulas for shorter paths that hold by the induction hypothesis. This often requires additional subcases; for example, for the above paths ending in $U$, the cases $l+1 < a-b$ and $l+1 = a-b$ would be considered separately.

Instead of such a tedious induction proof, we have chosen to present a proof that relies on certain two-rowed arrays that have been used by Krattenthaler and Mohanty [15]. One advantage of our proof is that it is bijective. Additionally, the methodology of two-rowed arrays that we introduce here will later allow us to prove Theorem 2.2 for pairs of paths, where a potential proof by induction is much less clear.

#### 3.1. Two-rowed arrays.
Let $x, y, u, v, k \in \mathbb{Z}$ and $n, j \ge 0$ throughout the section. We use the notation

$$ \begin{align*} (x, u)_j &= \{(c_1, \dots, c_j) : x < c_1 < c_2 < \dots < c_j \le u\}, \\ [y, v)_j &= \{(d_1, \dots, d_j) : y \le d_1 < d_2 < \dots < d_j < v\}, \\ (x, v)_j &= \{(c_1, \dots, c_j) : x < c_1 < c_2 < \dots < c_j < v\}, \\ [y, u)_j &= \{(d_1, \dots, d_j) : y \le d_1 < d_2 < \dots < d_j \le u\}. \end{align*} $$

We consider pairs of such sequences arranged in a particular way, which we call two-rowed arrays, following [11–13, 15]. We denote by $\{(x,u]_{n+k} \atop [y,v]_{n-k}\}$, or $\{(x,u] \atop [y,v)\}_{n \pm k}$ for short, the set of arrays of the form

$$ \begin{array}{l} x < c_1 < c_2 < \dots < c_{n+k} \le u, \\ y \le d_1 < d_2 < \dots < d_{n-k} < v \end{array}, $$

with the convention that this set is empty unless $|k| \le n$. The two rows are interlaced from the left, starting with the leftmost element in the bottom row. Elements in this set are denoted by $c$, where $c = (c_1, \dots, c_{n+k}) \in (x, u]_{n+k}$ and $d = (d_1, \dots, d_{n-k}) \in [y, v]_{n-k}$.

Similarly, we denote by $\{(x,v]_{n+k} \atop [y,u]\}$ the set of arrays of the form

$$ \begin{array}{l} x < c_1 < c_2 < \dots < c_{n+k} < v \\ y \le d_1 < d_2 < \dots < d_{n-k} \le u \end{array}. $$
The reason two-rowed arrays are useful for our problem is that elements of $\{(x,u] \atop [y,v)]\}_{n \pm 0}$, which we denote simply by $\{(x,u] \atop [y,v)]\}_n$, encode lattice paths in $P_{(x,y)\to(u,v)}$. This is because such paths are uniquely determined by the coordinates of their valleys. There exists a path in $P_{(x,y)\to(u,v)}$ whose valleys are at coordinates $(c_1, d_1), (c_2, d_2), \dots, (c_n, d_n)$ if and only if
$$x < c_1 < c_2 < \dots < c_n \le u \quad \text{and} \quad y \le d_1 < d_2 < \dots < d_n < v,$$

that is, $\mathbf{c} = (c_1, \dots, c_n) \in (x, u]_n$ and $\mathbf{d} = (d_1, \dots, d_n) \in [y, v)_n$. Thus, this encoding is a bijection

$$\{P \in \mathcal{P}_{(x,y) \to (u,v)} : \mathrm{des}(P) = n\} \to \{(x,u] \atop [y,v)]\}_n. \qquad (3.1)$$

It has the property that, if $P$ is encoded by $\mathbf{c}$, then

$$\mathrm{maj}(P) = \sum_{i=1}^{n} (c_i + d_i - x - y) = \|\mathbf{c}\| + \|\mathbf{d}\| - n(x + y), \qquad (3.2)$$

where $\|\mathbf{c}\|$ denotes the sum of the entries of $\mathbf{c}$. Next we enumerate two-rowed arrays with respect to this statistic.

**Lemma 3.1.** (i) We have

$$\sum_{\mathbf{c} \in (x, u]_j} q^{\|\mathbf{c}\|} = q^{\binom{j+1}{2} + jx} \begin{bmatrix} u-x \\ j \end{bmatrix}_q, \qquad \sum_{\mathbf{d} \in [y, v)_j} q^{\|\mathbf{d}\|} = q^{\binom{j+1}{2} + j(y-1)} \begin{bmatrix} v-y \\ j \end{bmatrix}_q, \\ \sum_{\mathbf{c} \in (x, v)_j} q^{\|\mathbf{c}\|} = q^{\binom{j+1}{2} + jx} \begin{bmatrix} v-x-1 \\ j \end{bmatrix}_q, \qquad \sum_{\mathbf{d} \in [y, u]_j} q^{\|\mathbf{d}\|} = q^{\binom{j+1}{2} + j(y-1)} \begin{bmatrix} u-y+1 \\ j \end{bmatrix}_q.$$

(ii) We have

$$\sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \{(x,u] \\ [y,v]\}_{n \pm k}}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| - n(x+y)} = q^{n^2+k(k+x-y+1)} \begin{bmatrix} u-x \\ n+k \end{bmatrix}_q \begin{bmatrix} v-y \\ n-k \end{bmatrix}_q, \qquad (3.3)$$

$$\sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \{(x,v] \\ [y,u]\}_{n \pm k}}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| - n(x+y)} = q^{n^2+k(k+x-y+1)} \begin{bmatrix} v-x-1 \\ n+k \end{bmatrix}_q \begin{bmatrix} u-y+1 \\ n-k \end{bmatrix}_q. \qquad (3.4)$$

*Proof.* We prove the first identity in part (i), since the other three are analogous. Writing $c'_i = c_i - i - x$ for $1 \le i \le j$, the left-hand side is equal to

$$\sum_{x<c_1<c_2<\dots<c_j \le u} q^{c_1+\dots+c_j} = q^{\binom{j+1}{2}+jx} \sum_{0 \le c'_1 \le c'_2 \le \dots \le c'_j \le u-x-j} q^{c'_1+\dots+c'_j}.$$

This sum counts partitions with at most $j$ parts with largest part at most $u-x-j$, which is a well-known interpretation of the $q$-binomial coefficients (see e.g. [1, Thm. 3.1]).

Part (ii) follows easily from part (i) using the simplification

$$\binom{n+k+1}{2} + \binom{n-k+1}{2} + (n+k)x + (n-k)(y-1) - n(x+y) = n^2 + k(k+x-y+1)$$
in the exponent of $q$. $\square$

To see how Lemma 3.1 will be applied, let us first use it to give a proof of Lemma 1.1.
Proof of Lemma 1.1. The two statements are clearly equivalent, so we prove the second one. Using the encoding (3.1), together with Equations (3.2) and (3.3) for $k = 0$, we get

$$ \sum_{P \in \mathcal{P}_{(x,y) \to (u,v)}} t^{\text{des}(P)} q^{\text{maj}(P)} = \sum_{n \ge 0} t^n \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \{(x,u) \\ [y,v)\}_n}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| - n(x+y)} = \sum_{n \ge 0} t^n q^{n^2} \begin{bmatrix} u-x \\ n \end{bmatrix}_q \begin{bmatrix} v-y \\ n \end{bmatrix}_q. \quad \square $$

3.2. Crossings in single two-rowed arrays. To encode paths in $\mathcal{G}_{a,b}$ as two-rowed arrays, we first turn the $U$ and $D$ steps into $N$ and $E$ steps, respectively. Additionally, to study crossings of the line $y = \ell$ in the original path, we move the starting point to $(\ell, 0)$, so that these crossings become crossings of the diagonal $y = x$ for the resulting path. Denoting by $\mathcal{P}_{A \to B}^{\ge r}$ the set of paths in $\mathcal{P}_{A \to B}$ that cross the diagonal at least $r$ times, this transformation is a bijection

$$ \mathcal{G}_{a,b}^{\ge r, \ell} \to \mathcal{P}_{(\ell,0) \to (b+\ell,a)}. \quad (3.5) $$

See Figure 4 for an example. In analogy to the definitions for paths in $\mathcal{G}_{a,b}$ crossing a line $y = \ell$, we define upward (resp. downward) crossings of paths in $\mathcal{P}_{A \to B}$ to be vertices in the diagonal $y = x$ that are preceded and followed by an $N$ (resp. by an $E$).

<figure><img src="image_91.png" /><figcaption>FIGURE 4. The path in $\mathcal{P}_{(1,0) \to (7,8)}^{\ge 3}$ obtained by applying the transformation (3.5) to the path in Figure 1, and the corresponding two-rowed array given by the encoding (3.1), where the crossings have been circled.</figcaption></figure>

Next we show how these crossings of the diagonal can be read from the encoding (3.1) of the path as a two-rowed array. Indeed, suppose that $P \in \mathcal{P}_{(x,y) \to (u,v)}$ is encoded by $\mathbf{c} \in \{(x,u]\}_{[y,v]}_n$, and let $c_0 := x$, $d_0 := y$, $c_{n+1} := u$, $d_{n+1} := v$ by convention. An upward crossing of $P$ occurs when, for some $0 \le i \le n$, the vertex $(c_i, d_i)$ —which is a valley or the first vertex of the path— lies below the diagonal and the vertex $(c_i, d_{i+1})$ —which is a peak or the last vertex of the path— lies above the diagonal. This happens precisely when $d_i < c_i < d_{i+1}$ for some $0 \le i \le n$. Similarly, a downward crossing occurs when, for some $1 \le i \le n+1$, the vertex $(c_{i-1}, d_i)$ —which is a peak or the starting point of the path— lies above the diagonal and the vertex $(c_i, d_i)$ —which is a valley or the last vertex of the path— lies below the diagonal. This happens precisely when $c_{i-1} < d_i < c_i$ for some $1 \le i \le n+1$.
This description allows us to extend the notion of crossings to two-rowed arrays $c_d \in \{(x,u] \mid [y,v] \}_{n \pm k}$ with $k \in \mathbb{Z}$, whose rows may have different lengths. Using the convention $c_0 := x$, $d_0 := y$, $c_{n+k+1} := u$, $d_{n-k+1} := v$, say that $c_d$ has an upward crossing at $c_i$ if $0 \le i \le n - |k|$ and

$$d_i < c_i < d_{i+1}, \qquad (3.6)$$

and that it has a downward crossing at $d_i$ if $1 \le i \le n - |k| + 1$ and

$$c_{i-1} < d_i < c_i.$$

For two-rowed arrays of the form $c_d \in \{(x,v] \mid [y,u] \}_{n \pm k}$, the definition of upward and downward crossings is the same, now using the convention $c_0 := x$, $d_0 := y$, $c_{n+k+1} := v$, $d_{n-k+1} := u$. Figure 5 shows two examples, where the crossings have been circled. As usual, the term *crossings* refers to both upward and downward crossings.

$$0 < 1 < \textcircled{4} < 5 < 7 \le 7 \qquad 2 \le 2 < \textcircled{3} < 5 \in \{(0,7] \mid [2,5] \}_{3 \pm 1}$$

<figure><img src="image_92.png" /></figure>

$$0 < 3 < \textcircled{4} < 6 \qquad 0 \le \textcircled{1} < 2 < \textcircled{5} < 7 \le 8 \in \{(0,6] \mid [0,8] \}_{3 \mp 1}$$

<figure><img src="image_93.png" /><figcaption>FIGURE 5. Two two-rowed arrays $c_d$ with their crossings circled, and the corresponding paths $T(c_d)$. Note that for the array on the right, $c_3 = 6$ is not a crossing because it violates the condition $i \le n - |k|$.</figcaption></figure>

In both of the above cases, let $T(c_d) \in \mathcal{P}_{(x,y) \to (c_{n-|k|+1}, d_{n-|k|+1})}$ be the path whose valleys are at coordinates $(c_i, d_i)$ for $1 \le i \le n - |k|$ (with the caveat that, in the special case when $c_d \in \{(x,v] \mid [y,u] \}_{n}$ and $d_n = u$, the vertex $(c_n, d_n)$ is not actually a valley of this path). Then the upward and downward crossings of the two-rowed array $c_d$ can be identified with the upward and downward crossings of $T(c_d)$; see the examples in Figure 5. Note that $T(c_d)$ is essentially the path corresponding to the two-rowed array obtained by truncating the longer row of $c_d$ so that both rows have equal length. To be precise, this path depends not only on $c_d$ but also on the endpoints $x, y, u, v$.

Throughout the paper, the *rth crossing* of a two-rowed array refers to the *rth crossing from the left*, in the order in which the entries are placed, namely $y, x, d_1, c_1, d_2, c_2, \dots$. We note that this convention is different from the one used in [3], where path crossings were numbered from the right. The unusual convention in [3] was needed because the path bijections in that paper, in order to track the major index, changed the portion of the paths to the *left* of a crossing. On the other hand, the notation in this paper becomes slightly simpler by defining bijections for two-rowed arrays (in Sections 3.3 and 4.3) that change the portion of the arrays to the *right* of a crossing instead.
For nonnegative $r$, the superscript $\ge r$ on a set of two-rowed arrays denotes the subset of those that have at least $r$ crossings. When $r \ge 1$, a symbol $\uparrow$ (resp. $\downarrow$) next to this superscript denotes the subset where the $r$th crossing is an upward (resp. downward) crossing. For example, $\{(x,u] \}_{[y,v]}^{\ge r \uparrow}$ consists of two-rowed arrays in $\{(x,u] \}_{[y,v]}^{\ge r}$ where the $r$th crossing is an upward crossing. In the case $r = 0$, we simply define

$$ \{(x,u] \}_{[y,v]}^{\ge 0 \uparrow} = \{(x,u] \}_{[y,v]}^{\ge 0 \downarrow} = \{(x,u] \}_{[y,v]}^{\ge 0} = \{(x,u] \}_{[y,v]}^{\ge 0} \quad (3.7) $$

by convention.

The encoding (3.1) restricts to a bijection

$$ \{P \in \mathcal{P}_{(x,y) \to (u,v)}^{\ge r} : \mathrm{des}(P) = n\} \to \{(x,u] \}_{[y,v]}^{\ge r} \}_{n}^{\ge r}. \quad (3.8) $$

Composing this with the bijection (3.5) and using Equation (3.2), it follows that

$$ G_{a,b}^{\ge r, \ell}(t, q) = \sum_{n \ge 0} t^n \sum_{\mathbf{c} \in \{(x,u] \}_{[y,v]}^{\ge r} \}_{n} q^{\|\mathbf{c}\| + \|\mathbf{d}\| - n(x+y)}, \quad (3.9) $$

where $(x, y) = (\ell, 0)$ and $(u, v) = (b + \ell, a)$.

To prove Theorem 2.1, we will construct bijections between $\{(x,u] \}_{[y,v]}^{\ge r} \}_{n}$ and sets of the form $\{(x,u] \}_{[y,v]}^{\ge r} \}_{n}$ or $\{(x,v] \}_{[y,u]}^{\ge r} \}_{n}$ for some $k \in \mathbb{Z}$, which will depend on the relations between $x$ and $y$ and between $u$ and $v$, and then apply Lemma 3.1.

**Lemma 3.2.** Let $r \ge 1$, and let $\mathbf{c}_d$ be a two-rowed array in either $\{(x,u] \}_{[y,v]}^{\ge r} \}_{n}$ or $\{(x,v] \}_{[y,u]}^{\ge r} \}_{n}$. If $x > y$ or $x = y = d_1$, then the $r$th crossing of $\mathbf{c}_d$ is an upward crossing if $r$ is odd, and a downward crossing if $r$ is even.

If $x < y$ or $x = y < d_1$, then the $r$th crossing of $\mathbf{c}_d$ is a downward crossing if $r$ is odd, and an upward crossing if $r$ is even.

*Proof.* As noted above, upward and downward crossings of $\mathbf{c}_d$ are the same as those of the path $T(\mathbf{c}_d) \in \mathcal{P}_{(x,y) \to (c_{n-|k|+1}, d_{n-|k|+1})}$. If $x > y$ (resp. $x < y$), this path starts below (resp. above) the diagonal, which forces the first crossing to be upward (resp. downward), with successive crossings alternating between upward and downward. If $x = y$, then $T(\mathbf{c}_d)$ starts with an $E$ if $y = d_1$, and with an $N$ if $y < d_1$, from which the same conclusions follow. $\square$

The next lemma shows that the relationships between $x$ and $y$ and between $u$ and $v$ often force the number of crossings of a two-rowed array to have a given parity. We use the notation $n \mp s$ to mean $n \pm (-s)$.
**Lemma 3.3.** Let $s, m \ge 0$.

(a) If $x > y$ and $u < v$, then

$$ \{ (x,u] \}_{n \mp s}^{\ge 2m+1} = \{ (x,u] \}_{n \mp s}^{\ge 2m+1 \uparrow} = \{ (x,u] \}_{n \mp s}^{\ge 2m \downarrow} = \{ (x,u] \}_{n \mp s}^{\ge 2m} \quad (3.10) $$

$$ \{ (x,v] \}_{n \mp s}^{\ge 2m+2} = \{ (x,v] \}_{n \mp s}^{\ge 2m+2 \downarrow} = \{ (x,v] \}_{n \mp s}^{\ge 2m+1 \uparrow} = \{ (x,v] \}_{n \mp s}^{\ge 2m+1} \quad (3.11) $$

(b) If $x > y$ and $u > v$, then

$$ \{ (x,u] \}_{n \mp s}^{\ge 2m+2} = \{ (x,u] \}_{n \mp s}^{\ge 2m+2 \downarrow} = \{ (x,u] \}_{n \mp s}^{\ge 2m+1 \uparrow} = \{ (x,u] \}_{n \mp s}^{\ge 2m+1} \quad (3.12) $$

$$ \{ (x,v] \}_{n \mp s}^{\ge 2m+1} = \{ (x,v] \}_{n \mp s}^{\ge 2m+1 \uparrow} = \{ (x,v] \}_{n \mp s}^{\ge 2m \downarrow} = \{ (x,v] \}_{n \mp s}^{\ge 2m} \quad (3.13) $$

(c) If $x < y$ and $u < v$, then

$$ \{ (x,u] \}_{n \mp s}^{\ge 2m+2} = \{ (x,u] \}_{n \mp s}^{\ge 2m+2 \uparrow} = \{ (x,u] \}_{n \mp s}^{\ge 2m+1 \downarrow} = \{ (x,u] \}_{n \mp s}^{\ge 2m+1} \quad (3.14) $$

$$ \{ (x,v] \}_{n \mp s}^{\ge 2m+1} = \{ (x,v] \}_{n \mp s}^{\ge 2m+1 \downarrow} = \{ (x,v] \}_{n \mp s}^{\ge 2m \uparrow} = \{ (x,v] \}_{n \mp s}^{\ge 2m} \quad (3.15) $$

(d) If $x < y$ and $u > v$, then

$$ \{ (x,u] \}_{n \mp s}^{\ge 2m+1} = \{ (x,u] \}_{n \mp s}^{\ge 2m+1 \downarrow} = \{ (x,u] \}_{n \mp s}^{\ge 2m \uparrow} = \{ (x,u] \}_{n \mp s}^{\ge 2m} \quad (3.16) $$

$$ \{ (x,v] \}_{n \mp s}^{\ge 2m+2} = \{ (x,v] \}_{n \mp s}^{\ge 2m+2 \uparrow} = \{ (x,v] \}_{n \mp s}^{\ge 2m+1 \downarrow} = \{ (x,v] \}_{n \mp s}^{\ge 2m+1} \quad (3.17) $$

(e) If $x > y$ and $u = v$, then (3.10)–(3.12) hold for $s \ge 1$, and (3.13) holds for $s \ge 0$.

(f) If $x < y$ and $u = v$, then (3.14)–(3.16) hold for $s \ge 1$, and (3.17) holds for $s \ge 0$.

(g) Statements (a), (b), (e) also hold if we replace $x > y$ with $x = y$ and restrict to two-rowed arrays $c_d$ with $y = d_1$.

*Proof.* In each equation, the outer equalities follow from Lemma 3.2 (using the convention (3.7) as needed), and the left-hand side is trivially contained in the right-hand side. To prove the reverse containment, we will show that the parity of the number of crossings of the relevant two-rowed arrays is determined by the relation between $x$ and $y$ and between $u$ and $v$ in each case.

Recall that if $c_d$ is a two-rowed array in either $\{(x,u]\}_{n \pm k}$ or $\{(x,v]\}_{n \pm k}$, for some $k \in \mathbb{Z}$, then $T(c_d)$ is a path from $(x, y)$ to $(c_{n-|k|+1}, d_{n-|k|+1})$ which has the same upward and downward crossings as $c_d$. The parity of the number of crossings is determined by what side of the diagonal the endpoints of the path are on. If $x > y$, $T(c_d)$ starts below the diagonal; if $x < y$, it starts above the diagonal; and if $x = y = d_1$, it starts with an E leaving the diagonal, so it behaves as in the $x > y$ case.

Suppose first that $c_d \in \{(x,u]\}_{[y,v]}_{n \pm s}$, where $s \ge 0$ and $u < v$. Then the last vertex of $T(c_d)$ is $(c_{n-s+1}, v)$, which lies above the diagonal, since $c_{n-s+1} \le u < v$. Thus, if $x > y$, then $T(c_d)$ starts below the diagonal and ends above the diagonal, so it must have an odd number of crossings, proving Equation (3.10). If $x = y = d_1$, the same conclusion holds. On the other hand, if $x < y$, then $T(c_d)$ starts and ends above the diagonal, so it must have an even number of crossings, proving Equation (3.14). Modifying the hypotheses so that $s \ge 1$ and $u \ge v$, the last vertex of $T(c_d)$ still lies above the diagonal, since $c_{n-s+1} < c_{n-s+2} \le u \le v$, so Equations (3.10) and (3.14) also hold in this case.
If $\mathbf{c}_d \in \{(x,v) \mid [y,u] \}_{n \neq s}$, where $s \ge 0$ and $u < v$, then the last vertex of $T(\mathbf{c}_d)$ is $(v, d_{n-s+1})$, which lies below the diagonal, since $d_{n-s+1} \le u < v$. Thus, $T(\mathbf{c}_d)$ must have an even number of crossings if $x > y$ or $x = y = d_1$, proving Equation (3.11), and an odd number of crossings if $x < y$, proving Equation (3.15). These two equations still hold with the modified hypotheses $s \ge 1$ and $u \le v$, since $d_{n-s+1} < d_{n-s+2} \le u \le v$ in this case, so the last vertex of $T(\mathbf{c}_d)$ still lies below the diagonal.

If $\mathbf{c}_d \in \{(x,v) \mid [y,u] \}_{n \neq s}$, where $s \ge 0$ and $u > v$, then the last vertex of $T(\mathbf{c}_d)$ is $(u, d_{n-s+1})$, which lies below the diagonal, since $d_{n-s+1} \le v < u$. This vertex also lies below the diagonal when $s \ge 1$ and $u \ge v$, since $d_{n-s+1} < d_{n-s+2} \le v \le u$. This proves Equations (3.12) and (3.16).

If $\mathbf{c}_d \in \{(x,v) \mid [y,u] \}_{n \neq s}$, where $s \ge 0$ and $u > v$, then the last vertex of $T(\mathbf{c}_d)$ is $(c_{n-s+1}, u)$, which lies above the diagonal, since $c_{n-s+1} \le v < u$. This vertex also lies above the diagonal when $s \ge 1$ and $u \ge v$, since $c_{n-s+1} < c_{n-s+2} \le v \le u$. Finally, when $s = 0$ and $u = v$, the path $T(\mathbf{c}_d)$ ends on the diagonal (at $(v, u)$), but its last step is an E step, since $c_{n-s} < v$. This proves Equations (3.13) and (3.17) for all $s \ge 0$ and $u \ge v$. $\square$

**3.3. The bijections $\alpha_r$ and $\beta_r$.** We are almost ready to define the key bijections $\alpha_r$ and $\beta_r$. These are reminiscent of the bijections $\sigma_r$ and $\tau_r$ defined in [3] for paths. An important difference, however, is that the image by $\beta_r$ of a two-rowed array that encodes a path does not encode a path in general, so one cannot view $\beta_r$ as a map on paths.

Let $\mathbf{c}_d$ be a two-rowed array in either $\{(x,u) \mid [y,v] \}_{n \neq k}$ or $\{(x,v) \mid [y,u] \}_{n \neq k}$. We say that a crossing of $\mathbf{c}_d$ at $c_i$ (resp. $d_i$) is proper if $c_i \notin \{u,v\}$ (resp. $d_i \notin \{u,v\}$).

For $r \ge 1$, the map $\alpha_r$ applies to two-rowed arrays $\mathbf{c}_d$ whose $r$th crossing is a proper upward crossing, and it swaps the parts of the top and the bottom rows of the array to the right of this crossing. Schematically, if the $r$th crossing is at $c_i$, we have

<figure><img src="image_94.png" /></figure>

The properness of the crossing guarantees that $c_{i+1}$ exists and that $c_i < c_{i+1}$. Additionally, we have $c_i < d_{i+1}$ and $d_i < c_{i+1}$, so the rows of $\alpha_r(\mathbf{c}_d)$ are increasing. The two-rowed array $\alpha_r(\mathbf{c}_d)$ has a crossing at $c_i$, since $d_i < c_i < c_{i+1}$, and this crossing is still proper. This is in fact the $r$th crossing of $\alpha_r(\mathbf{c}_d)$, because the portion of the arrays to the left of $c_i$ is not affected by $\alpha_r$. It follows that $\alpha_r$ is an involution.

Similarly, the map $\beta_r$ applies to two-rowed arrays $\mathbf{c}_d$ whose $r$th crossing is a proper downward crossing, and it also swaps the top and the bottom rows of the array to the right of this crossing. Schematically, if the $r$th crossing is at $d_i$, we have

<figure><img src="image_95.png" /></figure>

Again, the $r$th crossing of $\beta_r(\mathbf{c}_d)$ is still at $d_i$ and is a proper crossing, and the map $\beta_r$ is an involution.
**Lemma 3.4.** Let $x, y, u, v, k \in \mathbb{Z}$, $n \ge 0$ and $r \ge 1$, satisfying that, if $u > v$, then $k \le 0$, and if $u < v$, then $k \ge 1$. The map $\alpha_r$ restricts to a bijection

$$ \{ (x,u] \}_{[y,v]}^{\ge r \uparrow} \underset{n \pm k}{\longleftrightarrow} \{ (x,v) \}_{[y,u]}^{\ge r \uparrow} \quad \{ (x,v) \}_{n \mp k}^{\ge r \downarrow} $$

and the map $\beta_r$ restricts to a bijection

$$ \{ (x,u] \}_{[y,v]}^{\ge r \downarrow} \underset{n \pm (k-1)}{\longleftrightarrow} \{ (x,v) \}_{[y,u]}^{\ge r \downarrow} \quad \{ (x,v) \}_{n \mp k}^{\ge r \uparrow} $$

Both $\alpha_r$ and $\beta_r$ preserve the sum of the entries of the arrays.

*Proof.* The conditions on $k$, which depend on the relationship between $u$ and $v$, guarantee that the $r$th crossing of a two-rowed array in any of the four sets above is always proper, and so the maps $\alpha_r$ and $\beta_r$ are defined. Indeed, an improper upward crossing of $c_d \in \{ (x,u] \}_{[y,v]}_{n \pm k}$ at $c_i$ could only occur if $u = c_i < d_{i+1} \le v$ and $k \le 0$. Arrays $c_d \in \{ (x,v) \}_{[y,u]}_{n \mp k}$ cannot have improper upward crossings, since $c_i = v$ is incompatible with $i \le n - |k|$. An improper downward crossing of $c_d \in \{ (x,u] \}_{[y,v]}_{n \pm (k-1)}$ at $d_i$ could only occur if $v = d_i < c_i \le u$ and $k-1 \ge 0$. And an improper downward crossing of $c_d \in \{ (x,v) \}_{[y,u]}_{n \mp k}$ at $d_i$ could only occur if $u = d_i < c_i \le v$ and $k \le 0$.

Having already seen that $\alpha_r$ and $\beta_r$ are involutions, it remains to describe their images. Given $c_d \in \{ (x,u] \}_{[y,v]}^{\ge r \uparrow}$ whose $r$th crossing is at $c_i$, if we write $c_d$ as

$$ \begin{array}{l} x < c_1 < c_2 < \dots < \underbrace{c_i}_{\text{down}} < c_{i+1} < \dots < c_{n+k} \le u \\ y \le d_1 < d_2 < \dots < \underbrace{d_i}_{\text{up}} < d_{i+1} < d_{i+2} < \dots < d_{n-k} < v \end{array} $$

then $\alpha_r(c_d)$ is the two-rowed array

$$ \begin{array}{l} x < c_1 < c_2 < \dots < \underbrace{c_i}_{\text{down}} < d_{i+1} < d_{i+2} < \dots < d_{n-k} < v \\ y \le d_1 < d_2 < \dots < \underbrace{d_i}_{\text{up}} < c_{i+1} < \dots < c_{n+k} \le u, \end{array} $$

which has an upward crossing at $c_i$ and thus belongs to $\{ (x,v) \}_{[y,u]}^{\ge r \uparrow}$.

Similarly, given $c_d \in \{ (x,u] \}_{[y,v]}^{\ge r \downarrow}$ whose $r$th crossing is at $d_i$, if we write $c_d$ as

$$ \begin{array}{l} x < c_1 < c_2 < \dots < c_{i-1} < \underbrace{c_i}_{\text{down}} < c_{i+1} < \dots < c_{n+k-1} \le u \\ y \le d_1 < d_2 < \dots < \underbrace{d_i}_{\text{up}} < d_{i+1} < \dots < d_{n-k+1} < v \end{array} $$

then $\beta_r(c_d)$ is the two-rowed array

$$ \begin{array}{l} x < c_1 < c_2 < \dots < c_{i-1} < \underbrace{d_{i+1}}_{\text{down}} < \dots < \underbrace{d_{n-k+1}}_{\text{up}} < v \\ y \le d_1 < d_2 < \dots < \underbrace{d_i}_{\text{up}} < c_i < c_{i+1} < \dots < c_{n+k-1} \le u, \end{array} $$

which has a downward crossing at $d_i$ and thus belongs to $\{ (x,v) \}_{[y,u]}^{\ge r \downarrow}$.

It is clear by construction that both $\alpha_r$ and $\beta_r$ preserve the sum of the entries of the arrays. $\square$
### 3.4. Proof of Theorem 2.1.
For $a, b, r \ge 0$ and $\ell \in \mathbb{Z}$, we interpret elements of $G_{a,b}^{\ge r, \ell}$ as paths in $P_{(x,y) \to (u,v)}^{\ge r}$, where $(x, y) = (\ell, 0)$ and $(u, v) = (b + \ell, a)$, using the transformation (3.5). For any $n \ge 0$, the subset of paths having $n$ descents is in bijection with the set $\{(x,u] \}_{[y,v]}^{\ge r}$, using the encoding (3.8).

The proof is divided into nine cases according to whether the paths start below $(0 < \ell$, equivalently $x > y$), on $(0 = \ell$, equivalently $x = y$), or above $(0 > \ell$, equivalently $x < y$) the line being crossed, and whether they end below $(\ell > a - b$, equivalently $u > v$), on $(\ell = a - b$, equivalently $u = v$), or above $(\ell < a - b$, equivalently $u < v$) this line. In each case, we determine $G_{a,b}^{\ge r, \ell}(t, q)$ by first using Equation (3.9) to rewrite it in terms of two-rowed arrays, then repeatedly applying the maps from Lemma 3.4 to construct bijections between $\{(x,u] \}_{[y,v]}^{\ge r}$ and certain sets of two-rowed arrays with no requirement on the number of crossings, and finally using Lemma 3.1. The cases are labeled as in [3] for consistency, but we will prove them in a slightly different order.

**Case I:** $0 < \ell < a - b$, equivalently $x > y$ and $u < v$. By Equation (3.10) with $s = 0$,

$$ \{(x,u]\}_{[y,v]}^{\ge 2m+1} = \{(x,u]\}_{[y,v]}^{\ge 2m}, $$

and so $G_{a,b}^{\ge 2m+1, \ell}(t, q) = G_{a,b}^{\ge 2m, \ell}(t, q)$. Using Lemmas 3.3(a) and 3.4, noting that the condition $k \ge 1$ in the latter holds at each step, we construct a composition of bijections $\alpha_1 \circ \beta_2 \circ \cdots \circ \alpha_{2m-1} \circ \beta_{2m}$:

$$ \begin{aligned} \{(x,u]\}_{[y,v]}^{\ge 2m} &= \{(x,u]\}_{[y,v]}^{\ge 2m\downarrow} \xrightarrow{\beta_{2m}} \{(x,v]\}_{[y,u]}^{\ge 2m\downarrow} \xrightarrow{n \neq 1} \{(x,v]\}_{[y,u]}^{\ge 2m-1\uparrow} \xrightarrow{\alpha_{2m-1}} \{(x,u]\}_{[y,v]}^{\ge 2m-1\uparrow} = \{(x,u]\}_{[y,v]}^{\ge 2m-2\downarrow} \\ & \xrightarrow{\beta_{2m-2}} \cdots \xrightarrow{\alpha_1} \{(x,u]\}_{[y,v]}^{\ge 1\uparrow} = \{(x,u]\}_{[y,v]}^{\ge 0\downarrow} = \{(x,u]\}_{[y,v]}^{\ge 0\downarrow} \end{aligned} \quad (3.18) $$

See Figure 6 for an example. Since these bijections preserve the sum of the entries of the two-rowed arrays, Equation (3.3) gives

$$ \begin{aligned} \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \{(x,u]\}_{[y,v]}^{\ge 2m}}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| - n(x+y)} &= \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \{(x,u]\}_{[y,v]}^{\ge m}}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| - n(x+y)} \\ &= q^{n^2+m(m+x-y+1)} \begin{bmatrix} u-x \\ n+m \end{bmatrix}_q \begin{bmatrix} v-y \\ n-m \end{bmatrix}_q = q^{n^2+m(m+\ell+1)} \begin{bmatrix} a \\ n-m \end{bmatrix}_q \begin{bmatrix} b \\ n+m \end{bmatrix}_q. \end{aligned} \quad (3.19) $$

Using Equation (3.9), this proves Equation (2.1).

$$ \begin{array}{c} \{(1,7]\}_{[0,8]}^{\ge 2} = \{(1,7]\}_{[0,8]}^{\ge 2\downarrow} \xrightarrow{\beta_2} \{(1,8]\}_{[0,7]}^{\ge 2\downarrow} = \{(1,8]\}_{[0,7]}^{\ge 1\uparrow} \xrightarrow{\alpha_1} \{(1,7]\}_{[0,8]}^{\ge 1\uparrow} = \{(1,7]\}_{[0,8]}^{\ge 1} \\ 1 < 2 < \text{③} < 4 < \text{⑥} \le 7 \qquad 1 < 2 < \text{③} < 4 < 8 \qquad 1 < 2 < \text{③} < 4 < 5 < 6 \le 7 \\ 0 \le 0 < 1 < 4 < \text{⑤} < 8 \qquad 0 \le 0 < 1 < 4 < \text{⑤} < 6 \le 7 \qquad 0 \le 0 < 1 < 4 < 8 \end{array} $$

<caption>**FIGURE 6.** An example of the bijection (3.18), where $(x, y) = (1, 0)$, $(u, v) = (7, 8)$, $m = 1$ and $n = 4$.</caption>
**Case II:** $0 > \ell > a-b$, equivalently $x < y$ and $u > v$. Similarly to Case I, the equality $G_{a,b}^{\ge 2m+1,\ell}(t,q) = G_{a,b}^{\ge 2m,\ell}(t,q)$ follows now from Equation (3.16) with $s=0$. Again Lemmas 3.3(d) and 3.4, noting that the condition $k \le 0$ holds at each step, allow us to build a sequence of bijections $\beta_1 \circ \alpha_2 \circ \dots \circ \beta_{2m-1} \circ \alpha_{2m}$:

$$
\begin{align*}
& \left\{ \begin{matrix} (x,u] \\ [y,v) \end{matrix} \right\}_n^{\ge 2m} = \left\{ \begin{matrix} (x,u] \\ [y,v) \end{matrix} \right\}_n^{\ge 2m\uparrow} \\
\xrightarrow{\alpha_{2m}} & \left\{ \begin{matrix} (x,v] \\ [y,u] \end{matrix} \right\}_n^{\ge 2m\uparrow} = \left\{ \begin{matrix} (x,v) \\ [y,u] \end{matrix} \right\}_n^{\ge 2m-1\downarrow} \xrightarrow{\beta_{2m-1}} \left\{ \begin{matrix} (x,u] \\ [y,v) \end{matrix} \right\}_{n \mp 1}^{\ge 2m-1\downarrow} = \left\{ \begin{matrix} (x,u] \\ [y,v) \end{matrix} \right\}_{n \mp 1}^{\ge 2m-2\uparrow} \\
\xrightarrow{\alpha_{2m-2}} & \dots \xrightarrow{\beta_1} \left\{ \begin{matrix} (x,u] \\ [y,v) \end{matrix} \right\}_{n \mp m}^{\ge 1\downarrow} = \left\{ \begin{matrix} (x,u] \\ [y,v) \end{matrix} \right\}_{n \mp m}^{\ge 0\uparrow} = \left\{ \begin{matrix} (x,u) \\ [y,v) \end{matrix} \right\}_{n \mp m}.
\end{align*}
$$

Then, by Equation (3.3),

$$
\begin{align}
\sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \left\{ \begin{matrix} (x,u) \\ [y,v) \end{matrix} \right\}_n^{\ge 2m}}} q^{\|\mathbf{c}\|+\|\mathbf{d}\|-n(x+y)} &= \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \left\{ \begin{matrix} (x,u) \\ [y,v) \end{matrix} \right\}_{n \mp m}}} q^{\|\mathbf{c}\|+\|\mathbf{d}\|-n(x+y)} \nonumber \\
&= q^{n^2-m(-m+x-y+1)} \begin{bmatrix} u-x \\ n-m \end{bmatrix}_q \begin{bmatrix} v-y \\ n+m \end{bmatrix}_q = q^{n^2+m(m-\ell-1)} \begin{bmatrix} a \\ n+m \end{bmatrix}_q \begin{bmatrix} b \\ n-m \end{bmatrix}_q, \tag{3.20}
\end{align}
$$

proving Equation (2.2).

**Case III:** $0 > \ell < a-b$, equivalently $x < y$ and $u < v$. The equality $G_{a,b}^{\ge 2m+2,\ell}(t,q) = G_{a,b}^{\ge 2m+1,\ell}(t,q)$ follows now from Equation (3.14) with $s=0$. Lemmas 3.3(c) and 3.4 produce a sequence of bijections $\beta_1 \circ \alpha_2 \circ \dots \circ \beta_{2m+1}$:

$$
\begin{align*}
& \left\{ \begin{matrix} (x,u] \\ [y,v) \end{matrix} \right\}_n^{\ge 2m+1} = \left\{ \begin{matrix} (x,u] \\ [y,v) \end{matrix} \right\}_n^{\ge 2m+1\downarrow} \\
\xrightarrow{\beta_{2m+1}} & \left\{ \begin{matrix} (x,v) \\ [y,u] \end{matrix} \right\}_{n \mp 1}^{\ge 2m+1\downarrow} = \left\{ \begin{matrix} (x,v) \\ [y,u] \end{matrix} \right\}_{n \mp 1}^{\ge 2m\uparrow} \xrightarrow{\alpha_{2m}} \left\{ \begin{matrix} (x,u] \\ [y,v) \end{matrix} \right\}_{n \pm 1}^{\ge 2m\uparrow} = \left\{ \begin{matrix} (x,u] \\ [y,v) \end{matrix} \right\}_{n \pm 1}^{\ge 2m-1\downarrow} \\
\xrightarrow{\beta_{2m-1}} & \dots \xrightarrow{\beta_1} \left\{ \begin{matrix} (x,v) \\ [y,u] \end{matrix} \right\}_{n \mp (m+1)}^{\ge 1\downarrow} = \left\{ \begin{matrix} (x,v) \\ [y,u] \end{matrix} \right\}_{n \mp (m+1)}^{\ge 0\uparrow} = \left\{ \begin{matrix} (x,v) \\ [y,u] \end{matrix} \right\}_{n \mp (m+1)}.
\end{align*}
$$

By Equation (3.4),

$$
\begin{align*}
\sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \left\{ \begin{matrix} (x,u) \\ [y,v) \end{matrix} \right\}_n^{\ge 2m+1}}} q^{\|\mathbf{c}\|+\|\mathbf{d}\|-n(x+y)} &= \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \left\{ \begin{matrix} (x,v) \\ [y,u] \end{matrix} \right\}_{n \mp (m+1)}}} q^{\|\mathbf{c}\|+\|\mathbf{d}\|-n(x+y)} \\
&= q^{n^2-(m+1)(-m+x-y)} \begin{bmatrix} v-x-1 \\ n-m-1 \end{bmatrix}_q \begin{bmatrix} u-y+1 \\ n+m+1 \end{bmatrix}_q \\
&= q^{n^2+(m+1)(m-\ell)} \begin{bmatrix} a-\ell-1 \\ n-m-1 \end{bmatrix}_q \begin{bmatrix} b+\ell+1 \\ n+m+1 \end{bmatrix}_q, \quad (3.21)
\end{align*}
$$

proving Equation (2.3).
**Case IV:** $0 < \ell > a-b$, equivalently $x > y$ and $u > v$. Here $G_{a,b}^{\ge 2m+2,\ell}(t,q) = G_{a,b}^{\ge 2m+1,\ell}(t,q)$ because of Equation (3.12) with $s = 0$. Lemmas 3.3(b) and 3.4 give a sequence of bijections $\alpha_1 \circ \beta_2 \circ \cdots \circ \alpha_{2m+1}$:

$$ \begin{array}{ccc} \substack{\{ (x,u) \} \\ \{ [y,v) \} }_{n}^{\ge 2m+1} & = & \substack{\{ (x,u) \} \\ \{ [y,v) \} }_{n}^{\ge 2m+1 \uparrow} \\ \xrightarrow{\alpha_{2m+1}} & & \substack{\{ (x,v) \} \\ \{ [y,u) \} }_{n}^{\ge 2m+1 \uparrow} = \substack{\{ (x,v) \} \\ \{ [y,u) \} }_{n}^{\ge 2m \downarrow} \\ & \xrightarrow{\beta_{2m}} & \substack{\{ (x,u) \} \\ \{ [y,v) \} }_{n \mp 1}^{\ge 2m \downarrow} = \substack{\{ (x,u) \} \\ \{ [y,v) \} }_{n \mp 1}^{\ge 2m-1 \uparrow} \\ \xrightarrow{\alpha_{2m-1}} & \cdots & \xrightarrow{\alpha_1} \substack{\{ (x,v) \} \\ \{ [y,u) \} }_{n \pm m}^{\ge 1 \uparrow} = \substack{\{ (x,v) \} \\ \{ [y,u) \} }_{n \pm m}^{\ge 0 \downarrow} = \substack{\{ (x,v) \} \\ \{ [y,u) \} }_{n \pm m}. \end{array} $$

Thus, using Equation (3.4), we get Equation (2.4):

$$ \begin{aligned} \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \{ (x,u) \\ [y,v) \} \}_{n}^{\ge 2m+1}} q^{\|\mathbf{c}\|+\|\mathbf{d}\|-n(x+y)} &= \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \{ (x,v) \\ [y,u) \} \}_{n \pm m}} q^{\|\mathbf{c}\|+\|\mathbf{d}\|-n(x+y)} \\ &= q^{n^2+m(m+x-y+1)} \begin{bmatrix} v-x-1 \\ n+m \end{bmatrix}_q \begin{bmatrix} u-y+1 \\ n-m \end{bmatrix}_q = q^{n^2+m(m+\ell+1)} \begin{bmatrix} a-\ell-1 \\ n+m \end{bmatrix}_q \begin{bmatrix} b+\ell+1 \\ n-m \end{bmatrix}_q. \end{aligned} \quad (3.22) $$

**Case VII:** $0 < \ell = a-b$, equivalently $x > y$ and $u = v$. In this case, the parity of the total number of crossings is not forced by the endpoints, so we consider the cases $r = 2m$ and $r = 2m+1$ separately. The case $r = 2m$ is proved like Case I, constructing a sequence of bijections $\alpha_1 \circ \beta_2 \circ \cdots \circ \alpha_{2m-1} \circ \beta_{2m}$:

$$ \{ (x,u) \}_{n}^{\ge 2m} = \{ (x,u) \}_{n}^{\ge 2m \downarrow} \rightarrow \{ (x,u) \}_{n \pm m}^{\ge 1 \uparrow} = \{ (x,u) \}_{n \pm m}^{\ge 0 \downarrow} = \{ (x,u) \}_{n \pm m}, \quad (3.23) $$

where we use Lemma 3.2 for the left equality, and Lemmas 3.3(e) and 3.4 to compose the bijections. Equation (2.9) now follows using Equation (3.19) again.

The case $r = 2m + 1$ is proved like Case IV, constructing a sequence of bijections $\alpha_1 \circ \beta_2 \circ \cdots \circ \alpha_{2m+1}$:

$$ \{ (x,u) \}_{n}^{\ge 2m+1} = \{ (x,u) \}_{n}^{\ge 2m+1 \uparrow} \rightarrow \{ (x,v) \}_{n \pm m}^{\ge 1 \uparrow} = \{ (x,v) \}_{n \pm m}^{\ge 0 \downarrow} = \{ (x,v) \}_{n \pm m}. \quad (3.24) $$

Now we use Equation (3.22) and the fact that $\ell = a-b$ to prove Equation (2.10).

**Case VIII:** $0 > \ell = a-b$, equivalently $x < y$ and $u = v$. This case is analogous to Case VII. When $r = 2m$, we use the same sequence bijections as in Case II,

$$ \beta_1 \circ \alpha_2 \circ \cdots \circ \beta_{2m-1} \circ \alpha_{2m} : \{ (x,u) \}_{n}^{\ge 2m} \rightarrow \{ (x,v) \}_{n \mp m}, \quad (3.25) $$

using Lemma 3.3(f). Equation (2.11) now follows from Equation (3.20).

When $r = 2m + 1$, we use the same sequence of bijections as in Case III,

$$ \beta_1 \circ \alpha_2 \circ \cdots \circ \beta_{2m+1} : \{ (x,u) \}_{n}^{\ge 2m+1} \rightarrow \{ (x,v) \}_{n \mp (m+1)}. \quad (3.26) $$

Equation (2.12) follows from Equation (3.21) after the substitution $\ell = a-b$.
**Case V:** $0 = \ell < a - b$, equivalently $x = y$ and $u < v$. We will reduce this case to Case VIII by applying an involution $\nu$ on two-rowed arrays that changes the sign of each entry, reverses each row (so that the negated entries increase from left to right), and swaps the top and the bottom rows. The map $\nu$ restricts to bijections

$$ \left\{ \begin{smallmatrix} (x,u) \\ [y,v] \end{smallmatrix} \right\}_{n \pm k} \stackrel{\nu}{\longleftrightarrow} \left\{ \begin{smallmatrix} (-v,-y) \\ [-u,-x) \end{smallmatrix} \right\}_{n \mp k}, \qquad \left\{ \begin{smallmatrix} (x,v) \\ [y,u] \end{smallmatrix} \right\}_{n \pm k} \stackrel{\nu}{\longleftrightarrow} \left\{ \begin{smallmatrix} [-u,-y) \\ (-v,-x) \end{smallmatrix} \right\}_{n \mp k} \qquad (3.27) $$

for any $k \in \mathbb{Z}$. Additionally, in the case $k = 0$, it restricts to a bijection

$$ \left\{ \begin{smallmatrix} (x,u) \\ [y,v] \end{smallmatrix} \right\}_n^{\ge r} \stackrel{\nu}{\longleftrightarrow} \left\{ \begin{smallmatrix} (-v,-y) \\ [-u,-x) \end{smallmatrix} \right\}_n^{\ge r}, \qquad (3.28) $$

since it preserves the number of crossings; specifically, upward crossings turn into downward crossings, and vice versa. Indeed, the two-rowed array

$$ \begin{gathered} x < c_1 < c_2 < \cdots < c_n \le u \\ y \le d_1 < d_2 < \cdots < d_n < v \end{gathered} $$

is mapped by $\nu$ to

$$ \begin{gathered} -v < -d_n < -d_{n-1} < \cdots < -d_1 \le -y \\ -u \le -c_n < -c_{n-1} < \cdots < -c_1 < -x \end{gathered} $$

Thus, the first array has an upward crossing at $c_i$ if and only if the second one has a downward crossing at $-c_i$, since condition (3.6) is equivalent to $-d_{i+1} < -c_i < -d_i$, and similarly for the other type of crossing. In terms of the corresponding lattice paths given by the encoding (3.8), the involution $\nu$ translates to a reflection along the line $x + y = 0$.

The conditions $x = y$ and $u < v$ are equivalent to $-v < -u$ and $-y = -x$, so we can apply the bijections from Case VIII to the set on the right-hand side of (3.28). When $r = 2m$, Equation (3.25) gives a bijection

$$ \beta_1 \circ \alpha_2 \circ \cdots \circ \beta_{2m-1} \circ \alpha_{2m} : \left\{ \begin{smallmatrix} (-v,-y) \\ [-u,-x) \end{smallmatrix} \right\}_n^{\ge 2m} \longrightarrow \left\{ \begin{smallmatrix} (-v,-y) \\ [y,v) \end{smallmatrix} \right\}_{n \mp m}. $$

Conjugating by $\nu$, we get a bijection

$$ \nu \circ \beta_1 \circ \alpha_2 \circ \cdots \circ \beta_{2m-1} \circ \alpha_{2m} \circ \nu : \left\{ \begin{smallmatrix} (x,u) \\ [y,v) \end{smallmatrix} \right\}_n^{\ge 2m} \longrightarrow \left\{ \begin{smallmatrix} (x,u) \\ [y,v) \end{smallmatrix} \right\}_{n \pm m} $$

that preserves the sum of the entries. Using Equation (3.19) with $\ell = 0$, we deduce Equation (2.5).

When $r = 2m + 1$, Equation (3.26) gives a bijection

$$ \beta_1 \circ \alpha_2 \circ \cdots \circ \beta_{2m+1} : \left\{ \begin{smallmatrix} (-v,-y) \\ [-u,-x) \end{smallmatrix} \right\}_n^{\ge 2m+1} \longrightarrow \left\{ \begin{smallmatrix} (-v,-x) \\ [-u,-y) \end{smallmatrix} \right\}_{n \mp (m+1)}, $$

and conjugating by $\nu$ we get

$$ \nu \circ \beta_1 \circ \alpha_2 \circ \cdots \circ \beta_{2m+1} \circ \nu : \left\{ \begin{smallmatrix} (x,u) \\ [u,v) \end{smallmatrix} \right\}_n^{\ge 2m} \longrightarrow \left\{ \begin{smallmatrix} [y,u) \\ (x,v) \end{smallmatrix} \right\}_{n \pm (m+1)}. $$

Swapping the top and bottom rows and using Equation (3.21) with $\ell = 0$, we deduce Equation (2.6).
**Case VI:** $0 = \ell > a - b$, equivalently $x = y$ and $u > v$. By applying the map $\nu$, this case reduces to Case VII, since the conditions $x = y$ and $u > v$ are equivalent to $-v > -u$ and $-y = -x$. When $r = 2m$, conjugating the bijection (3.23) with $\nu$ gives a bijection

$$ \nu \circ \alpha_1 \circ \beta_2 \circ \dots \circ \alpha_{2m-1} \circ \beta_{2m} \circ \nu : \left\{ \begin{smallmatrix} (x,u) \\ [y,v) \end{smallmatrix} \right\}_n^{\ge 2m} \to \left\{ \begin{smallmatrix} (x,u) \\ [y,v) \end{smallmatrix} \right\}_{n \ne m}. $$

Using Equation (3.20) with $\ell = 0$, we deduce Equation (2.7).

When $r = 2m + 1$, conjugating the bijection (3.24) with $\nu$ gives a bijection

$$ \nu \circ \alpha_1 \circ \beta_2 \circ \dots \circ \alpha_{2m+1} \circ \nu : \left\{ \begin{smallmatrix} (x,u) \\ [y,v) \end{smallmatrix} \right\}_n^{\ge 2m+1} \to \left\{ \begin{smallmatrix} [y,u) \\ (x,v) \end{smallmatrix} \right\}_{n \ne m}. $$

Swapping the top and bottom rows and using Equation (3.22) with $\ell = 0$, we deduce Equation (2.8).

**Case IX:** $0 = \ell = a - b$, equivalently $x = y$ and $u = v$. We consider two cases according to the first step of the path. Via the bijection (3.8), paths in the left-hand side starting with an $N$ are encoded by two-rowed arrays $\mathbf{c}_d \in \left\{ \begin{smallmatrix} (x,u) \\ [y,v) \end{smallmatrix} \right\}_n^{\ge r}$ with $y < d_1$; equivalently, by $\mathbf{c}_d \in \left\{ \begin{smallmatrix} (x,u) \\ [y+1,v) \end{smallmatrix} \right\}_n^{\ge r}$. Note that replacing the lower bound $y$ with $y+1$ does not affect the number of crossings of the array, since $\mathbf{c}_d$ cannot have a crossing at $c_0$ in either case. Since $x < y+1$, the conditions in Case VIII hold with $y+1$ playing the role of $y$. Equation (3.25) gives a bijection

$$ \beta_1 \circ \alpha_2 \circ \dots \circ \beta_{2m-1} \circ \alpha_{2m} : \left\{ \begin{smallmatrix} (x,u) \\ [y+1,v) \end{smallmatrix} \right\}_n^{\ge 2m} \to \left\{ \begin{smallmatrix} (x,u) \\ [y+1,v) \end{smallmatrix} \right\}_{n \ne m}. $$

Then, using Equation (3.3), it follows that

$$ \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \left\{ \begin{smallmatrix} (x,u) \\ [y+1,v) \end{smallmatrix} \right\}_n^{\ge 2m}}} q^{\|\mathbf{c}\|+\|\mathbf{d}\|-n(x+y)} = q^n \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \left\{ \begin{smallmatrix} (x,u) \\ [y+1,v) \end{smallmatrix} \right\}_{n \ne m}}} q^{\|\mathbf{c}\|+\|\mathbf{d}\|-n(x+y+1)} \\ = q^n q^{n^2-m(-m+x-y)} \begin{bmatrix} u-x \\ n-m \end{bmatrix}_q \begin{bmatrix} v-y-1 \\ n+m \end{bmatrix}_q = q^{n^2+n+m^2} \begin{bmatrix} a \\ n-m \end{bmatrix}_q \begin{bmatrix} a-1 \\ n+m \end{bmatrix}_q. \quad (3.29) $$

Similarly, Equation (3.26) gives a bijection

$$ \beta_1 \circ \alpha_2 \circ \dots \circ \beta_{2m+1} : \left\{ \begin{smallmatrix} (x,u) \\ [y+1,v) \end{smallmatrix} \right\}_n^{\ge 2m+1} \to \left\{ \begin{smallmatrix} (x,v) \\ [y+1,u] \end{smallmatrix} \right\}_{n \ne (m+1)}, $$

and Equation (3.4) implies that

$$ \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \left\{ \begin{smallmatrix} (x,u) \\ [y+1,v) \end{smallmatrix} \right\}_n^{\ge 2m+1}}} q^{\|\mathbf{c}\|+\|\mathbf{d}\|-n(x+y)} = q^n \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \left\{ \begin{smallmatrix} (x,v) \\ [y+1,u] \end{smallmatrix} \right\}_{n \ne (m+1)}}} q^{\|\mathbf{c}\|+\|\mathbf{d}\|-n(x+y+1)} \\ = q^n q^{n^2-(m+1)(-m-1+x-y)} \begin{bmatrix} v-x-1 \\ n-m-1 \end{bmatrix}_q \begin{bmatrix} u-y \\ n+m+1 \end{bmatrix}_q \\ = q^{n^2+n+(m+1)^2} \begin{bmatrix} a-1 \\ n-m-1 \end{bmatrix}_q \begin{bmatrix} a \\ n+m+1 \end{bmatrix}_q. \quad (3.30) $$
On the other hand, paths in the left-hand side of (3.8) starting with an E are encoded by two-rowed arrays $\mathbf{c}_d \in \{(x,u] \mid [y,v)]_n\}_{n \ge r}$ with $y = d_1$. Let us use the notation $\{(x,u]_n \mid [y,v)_n\}_{n \ge r}$ for such arrays, where the double bracket indicates that the first element in the bottom row is forced to equal its lower bound. By Lemma 3.3(g), we can use the same bijections as in Case VII, noting that the condition $y = d_1$ is preserved when applying the maps from Lemma 3.4. For $r = 2m$, we get a bijection

$$ \alpha_1 \circ \beta_2 \circ \dots \circ \alpha_{2m-1} \circ \beta_{2m} : \{(x,u] \mid [y,v)]_n\}_{n \ge 2m} \to \{(x,u] \mid [y,v)]_n\}_{n \pm m}, $$

and Equation (3.3) implies that

$$
\begin{align*}
\sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \{(x,u] \mid [y,v)]_n\}_{n \ge 2m}}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| - n(x+y)} &= \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \{(x,u] \mid [y,v)]_n\}_{n \pm m}}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| - n(x+y)} \\
&= \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \{(x,u] \mid [y,v)]_n\}_{n \pm m}}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| - n(x+y)} - q^n \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \{(x,u] \mid [y+1,v)]_n\}_{n \pm m}}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| - n(x+y+1)} \\
&= q^{n^2+m(m+x-y+1)} \begin{bmatrix} u-x \\ n+m \end{bmatrix}_q \begin{bmatrix} v-y \\ n-m \end{bmatrix}_q - q^n q^{n^2+m(m+x-y)} \begin{bmatrix} u-x \\ n+m \end{bmatrix}_q \begin{bmatrix} v-y-1 \\ n-m \end{bmatrix}_q \\
&= q^{n^2+m(m+1)} \begin{bmatrix} a \\ n+m \end{bmatrix}_q \begin{bmatrix} a \\ n-m \end{bmatrix}_q - q^n q^{n^2+m^2} \begin{bmatrix} a \\ n+m \end{bmatrix}_q \begin{bmatrix} a-1 \\ n-m \end{bmatrix}_q \\
&= q^{n^2+m(m+1)} \begin{bmatrix} a \\ n+m \end{bmatrix}_q \left( \begin{bmatrix} a \\ n-m \end{bmatrix}_q - q^{n-m} \begin{bmatrix} a-1 \\ n-m \end{bmatrix}_q \right) \\
&= q^{n^2+m(m+1)} \begin{bmatrix} a \\ n+m \end{bmatrix}_q \begin{bmatrix} a-1 \\ n-m-1 \end{bmatrix}_q. \tag{3.31}
\end{align*}
$$

Similarly, for $r = 2m + 1$, we get a bijection (see the example in Figure 7):

$$ \alpha_1 \circ \beta_2 \circ \dots \circ \alpha_{2m+1} : \{(x,u] \mid [y,v)]_n\}_{n \ge 2m+1} \to \{(x,v) \mid [y,u]_n\}_{n \pm m}. \tag{3.32} $$

$$
\begin{array}{l}
\{(0,7]\}_{3}^{\ge 3} = \{(0,7]\}_{3}^{\ge 3\uparrow} \xrightarrow{\alpha_3} \{(0,7]\}_{3}^{\ge 3\uparrow} = \{(0,7]\}_{3}^{\ge 2\downarrow} \xrightarrow{\alpha_1} \{(0,7]\}_{3\mp 1}^{\ge 2\downarrow} = \{(0,7]\}_{3\mp 1}^{\ge 1\uparrow} \xrightarrow{\alpha_1} \{(0,7]\}_{3\pm 1}^{\ge 1\uparrow} = \{(0,7]\}_{3\pm 1} \\
0<2<3<6\le 7 & 0<2<3<6<7 & 0<2<3\le 7 & 0<2<3<5<6<7 \\
0=0<3<5<7 & 0=0<3<5\le 7 & 0=0<3<5<6<7 & 0=0<3\le 7
\end{array}
$$

<caption>FIGURE 7. An example of the bijection (3.32), where $(x, y) = (0, 0)$, $(u, v) = (7, 7)$, $m = 1$ and $n = 3$.</caption>
Then, Equation (3.4) implies that

$$
\begin{align*}
\sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \{(x,u]\} \}_{n}^{\ge 2m+1}} q^{\|\mathbf{c}\|+\|\mathbf{d}\|-n(x+y)} &= \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \{(x,v]\} \}_{n \pm m}} q^{\|\mathbf{c}\|+\|\mathbf{d}\|-n(x+y)} \\
&= \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \{(x,v]\} \}_{n \pm m}} q^{\|\mathbf{c}\|+\|\mathbf{d}\|-n(x+y)} - q^n \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \{[y+1,u]\} \}_{n \pm m}} q^{\|\mathbf{c}\|+\|\mathbf{d}\|-n(x+y+1)} \\
&= q^{n^2+m(m+x-y+1)} \begin{bmatrix} v-x-1 \\ n+m \end{bmatrix}_q \begin{bmatrix} u-y+1 \\ n-m \end{bmatrix}_q - q^n q^{n^2+m(m+x-y)} \begin{bmatrix} v-x-1 \\ n+m \end{bmatrix}_q \begin{bmatrix} u-y \\ n-m \end{bmatrix}_q \\
&= q^{n^2+m(m+1)} \begin{bmatrix} a-1 \\ n+m \end{bmatrix}_q \begin{bmatrix} a+1 \\ n-m \end{bmatrix}_q - q^n q^{n^2+m^2} \begin{bmatrix} a-1 \\ n+m \end{bmatrix}_q \begin{bmatrix} a \\ n-m \end{bmatrix}_q \\
&= q^{n^2+m(m+1)} \begin{bmatrix} a-1 \\ n+m \end{bmatrix}_q \begin{bmatrix} a \\ n-m-1 \end{bmatrix}_q. \tag{3.33}
\end{align*}
$$

Adding Equations (3.29) and (3.31) to account for all paths with at least 2m crossings, we get

$$
\begin{align*}
& \sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \{(x,u]\} \\ \qquad [y,v]\} \substack{\ge 2m \\ n}}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| - n(x+y)} \\
&= q^{n^2+m(m+1)} \left( q^{n-m} \begin{bmatrix} a \\ n-m \end{bmatrix}_q \begin{bmatrix} a-1 \\ n+m \end{bmatrix}_q + \begin{bmatrix} a \\ n+m \end{bmatrix}_q \begin{bmatrix} a-1 \\ n-m-1 \end{bmatrix}_q \right) \\
&= q^{n^2+m(m+1)} \frac{1-q^{a-2m}}{1-q^a} \begin{bmatrix} a \\ n+m \end{bmatrix}_q \begin{bmatrix} a \\ n-m \end{bmatrix}_q,
\end{align*}
$$

which proves Equation (2.13).

Similarly, adding Equations (3.30) and (3.33) to account for all paths with at least
$2m+1$ crossings, we get

$$
\sum_{\substack{\mathbf{c} \\ \mathbf{d} \in \{(x,u]\} \\ \qquad [y,v]\} \substack{\ge 2m+1 \\ n}}} q^{\|\mathbf{c}\|+\|\mathbf{d}\|-n(x+y)} = q^{n^2+m(m+1)} \frac{1-q^{a+2(m+1)}}{1-q^a} \begin{bmatrix} a \\ n+m+1 \end{bmatrix}_q \begin{bmatrix} a \\ n-m-1 \end{bmatrix}_q,
$$

which proves Equation (2.14).
## 4. PROOFS FOR PATHS CROSSING EACH OTHER

In this section we prove Theorem 2.2. Using the bijection (3.1), we will encode pairs of lattice paths as pairs of two-rowed arrays, describe crossings in this setting, and then define certain bijections on pairs of arrays.

**4.1. Pairs of two-rowed arrays.** Throughout the section, let $k \in \mathbb{Z}$ and $n \ge 0$, let $\{\circ, \bullet\} = \{1, 2\}$, and let $A_1 = (x_1, y_1)$, $A_2 = (x_2, y_2)$, $B_1 = (u_1, v_1)$, and $B_2 = (u_2, v_2)$ be four pairs of integers. We consider certain sets of pairs of two-rowed arrays, for which we introduce the notation

$$ \left\{ \begin{array}{c} (x_1, u_\circ) \\ [y_1, v_\circ) \end{array} \middle| \begin{array}{c} (x_2, u_\bullet) \\ [y_2, v_\bullet) \end{array} \right\}_{n,k} = \bigcup_{n_1+n_2=n} \left\{ \begin{array}{c} (x_1, u_\circ]_{n_1} \\ [y_1, v_\circ)_{n_1+k} \end{array} \right\} \times \left\{ \begin{array}{c} (x_2, u_\bullet]_{n_2} \\ [y_2, v_\bullet)_{n_2-k} \end{array} \right\}. \quad (4.1) $$

Elements of such sets are denoted by placing two two-rowed arrays side by side, namely $\mathbf{c}|_{\mathbf{f}}^e$, where $\mathbf{c} \in \left\{ \begin{array}{c} (x_1, u_\circ]_{n_1} \\ [y_1, v_\circ)_{n_1+k} \end{array} \right\}$ and $\mathbf{e} \in \left\{ \begin{array}{c} (x_2, u_\bullet]_{n_2} \\ [y_2, v_\bullet)_{n_2-k} \end{array} \right\}$, with $n_1 + n_2 = n$. When $k = 0$, the subscript $k$ will often be omitted.

Applying the encoding (3.1) to each component of a pair of paths, we get a bijection

$$ \{(P, Q) \in \mathcal{P}_{A_1 \to B_0} \times \mathcal{P}_{A_2 \to B_\bullet} : \mathrm{des}(P) + \mathrm{des}(Q) = n\} \to \left\{ \begin{array}{c} (x_1, u_\circ) \\ [y_1, v_\circ) \end{array} \middle| \begin{array}{c} (x_2, u_\bullet) \\ [y_2, v_\bullet) \end{array} \right\}_n. \quad (4.2) $$

See Figure 8 for an example. Suppose that condition (2.15) holds, and let $z = x_1 + y_1 = x_2 + y_2$. If $(P, Q)$ is encoded by $\mathbf{c}|_{\mathbf{f}}^e$, then

$$ \mathrm{maj}(P) + \mathrm{maj}(Q) = \sum_{i=1}^{n_1} (c_i + d_i - x_1 - y_1) + \sum_{j=1}^{n_2} (e_j + f_j - x_2 - y_2) = \|\mathbf{c}\| + \|\mathbf{d}\| + \|\mathbf{e}\| + \|\mathbf{f}\| - nz. \quad (4.3) $$

Next we adapt Lemma 3.1 to enumerate the sets (4.1) with respect to this statistic.

<figure><img src="image_96.png" /><figcaption>FIGURE 8. The encoding (4.2) applied to the pair of paths from Figure 3, and the resulting pair of two-rowed arrays, where the crossings have been circled.</figcaption></figure>
**Lemma 4.1.** Suppose that $z = x_1 + y_1 = x_2 + y_2$. We have

$$ 
\begin{aligned}
& \sum_{n \ge 0} t^n \sum_{\substack{\mathbf{c} \, | \, \mathbf{e} \\ \mathbf{d} \, | \, \mathbf{f}}} \sum_{\substack{(x_1, u_\circ) \, | \, (x_2, u_\bullet) \\ [y_1, v_\circ) \, | \, [y_2, v_\bullet]}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| + \|\mathbf{e}\| + \|\mathbf{f}\| - nz} \\
& = q^{k(k+x_2-x_1)} \left( \sum_{n_1 \ge 0} t^{n_1} q^{n_1(n_1+k)} \begin{bmatrix} u_\circ - x_1 \\ n_1 \end{bmatrix}_q \begin{bmatrix} v_\circ - y_1 \\ n_1 + k \end{bmatrix}_q \right) \times \\
& \qquad \left( \sum_{n_2 \ge 0} t^{n_2} q^{n_2(n_2-k)} \begin{bmatrix} u_\bullet - x_2 \\ n_2 \end{bmatrix}_q \begin{bmatrix} v_\bullet - y_2 \\ n_2 - k \end{bmatrix}_q \right) \\
& = f_{k,A_1,A_2,B_\circ,B_\bullet}(t,q).
\end{aligned}
$$

*Proof.* Using (4.1), the left-hand side expression can be factored as

$$ \left( \sum_{n_1 \ge 0} t^{n_1} \sum_{\substack{\mathbf{c} \in \{(x_1, u_\circ)_{n_1}\} \\ \mathbf{d} \in \{(y_1, v_\circ)_{n_1+k}\}}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| - n_1 z} \right) \left( \sum_{n_2 \ge 0} t^{n_2} \sum_{\substack{\mathbf{c} \in \{(x_2, u_\bullet)_{n_2}\} \\ \mathbf{d} \in \{(y_2, v_\bullet)_{n_2-k}\}}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| - n_2 z} \right). \quad (4.4) $$

For fixed $n_1$, Lemma 3.1(i) gives

$$ 
\begin{aligned}
\sum_{\substack{\mathbf{c} \in \{(x_1, u_\circ)_{n_1}\} \\ \mathbf{d} \in \{(y_1, v_\circ)_{n_1+k}\}}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| - n_1 z} &= \left( \sum_{\mathbf{c} \in (x_1, u_\circ]_{n_1}} q^{\|\mathbf{c}\|} \right) \left( \sum_{\mathbf{d} \in [y_1, v_\circ)_{n_1+k}} q^{\|\mathbf{d}\|} \right) q^{-n_1(x_1+y_1)} \\
&= q^{n_1(n_1+k) + \binom{k}{2} + k y_1} \begin{bmatrix} u_\circ - x_1 \\ n_1 \end{bmatrix}_q \begin{bmatrix} v_\circ - y_1 \\ n_1 + k \end{bmatrix}_q,
\end{aligned}
\quad (4.5) $$

where we used the simplification

$$ \binom{n_1+1}{2} + \binom{n_1+k+1}{2} + n_1 x_1 + (n_1+k)(y_1-1) - n_1(x_1+y_1) = n_1(n_1+k) + \binom{k}{2} + k y_1. $$

Similarly,

$$ \sum_{\substack{\mathbf{c} \in \{(x_2, u_\bullet)_{n_2}\} \\ \mathbf{d} \in \{(y_2, v_\bullet)_{n_2-k}\}}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| - n_2 z} = q^{n_2(n_2-k) + \binom{k+1}{2} - k y_2} \begin{bmatrix} u_\bullet - x_2 \\ n_2 \end{bmatrix}_q \begin{bmatrix} v_\bullet - y_2 \\ n_2 - k \end{bmatrix}_q. \quad (4.6) $$

Substituting (4.5) and (4.6) into (4.4) and using that $\binom{k}{2} + \binom{k+1}{2} + k(y_1 - y_2) = k(k + x_2 - x_1)$, we obtain the stated identity. $\square$
### 4.2. Crossings in pairs of two-rowed arrays.
Let vertex $V_s$ be a crossing of two paths $P$ and $Q$, as defined in Section 2.2. We say that $V_s$ is an *upward* (resp. *downward*) crossing of $(P,Q)$ if the step of $P$ leaving $V_s$ is an $N$ (resp. $E$); equivalently, if the step of $Q$ leaving $V_s$ is an $E$ (resp. $N$).

Crossings of a pair of paths can be read from their encoding (4.2) as a pair of two-rowed arrays. Indeed, suppose that $(P,Q)$ is encoded by $c_d|_f^e$, where $c_d \in \{(x_1,u_\circ)_{n_1} \\ [y_1,v_\circ)_{n_1}\}$ and $e_f \in \{(x_2,u_\bullet)_{n_2} \\ [y_2,v_\bullet)_{n_2}\}$, and let $c_0 := x_1$, $d_0 := y_1$, $c_{n_1+1} := u_\circ$, $d_{n_1+1} := v_\circ$, $e_0 := x_2$, $f_0 := y_2$, $e_{n_2+1} := u_\bullet$, $f_{n_2+1} := v_\bullet$ by convention. For simplicity, let us assume that $A_1 < A_2$ or $A_1 = A_2$. Then $(P,Q)$ has an upward crossing at $(c_i, f_j)$, where $0 \le i \le n_1$ and $1 \le j \le n_2+1$, if all of the following hold:

$$(i^\uparrow) \quad e_{j-1} \le c_i < e_j \quad \text{and} \quad d_i \le f_j < d_{i+1},$$

$$(ii^\uparrow) \quad (e_{j-1}, f_{j-1}, e_{j-2}, f_{j-2}, \dots, e_0, f_0) <_{\text{alt}} (c_i, d_i, c_{i-1}, d_{i-1}, \dots, c_0, d_0) \quad \text{and} \\ (d_i, c_{i-1}, d_{i-1}, c_{i-2}, \dots, c_0, d_0) <_{\text{alt}} (f_j, e_{j-1}, f_{j-1}, e_{j-2}, \dots, e_0, f_0),$$

where $<_{\text{alt}}$ is defined recursively by $(a_1, a_2, a_3, \dots) <_{\text{alt}} (b_1, b_2, b_3, \dots)$ if either $a_1 < b_1$, or $a_1 = b_1$ and $(b_2, b_3, \dots) <_{\text{alt}} (a_2, a_3, \dots)$. Indeed, condition $(i^\uparrow)$ states that $(c_i, f_j)$ belongs to both $P$ and $Q$, and that $P$ (resp. $Q$) leaves this vertex with an $N$ (resp. $E$). Condition $(ii^\uparrow)$ states that, if $V_1$ is the first vertex of the maximal sequence of consecutive common vertices ending at $(c_i, f_j)$, then $P$ (resp. $Q$) arrives at $V_1$ with an $N$ (resp. $E$).

Similarly, $(P,Q)$ has a downward crossing at $(e_j, d_i)$, where $1 \le i \le n_1+1$ and $0 \le j \le n_2$, if

$$(i^\downarrow) \quad c_{i-1} \le e_j < c_i \quad \text{and} \quad f_j \le d_i < f_{j+1},$$

$$(ii^\downarrow) \quad (c_{i-1}, d_{i-1}, c_{i-2}, d_{i-2}, \dots, c_0, d_0) <_{\text{alt}} (e_j, f_j, e_{j-1}, f_{j-1}, \dots, e_0, f_0) \quad \text{and} \\ (f_j, e_{j-1}, f_{j-1}, e_{j-2}, \dots, c_0, d_0) <_{\text{alt}} (d_i, c_{i-1}, d_{i-1}, c_{i-2}, \dots, e_0, f_0).$$

For example, the pair of paths in Figure 8 has a downward crossing at $(e_1, d_2) = (3,4)$. Condition $(i^\downarrow)$ states that $3 \le 3 < 6$ and $2 \le 4 < 5$, and condition $(ii^\downarrow)$ states that $(3, 2, 0, 2) <_{\text{alt}} (3, 2, 2, 0)$ and $(2, 2, 0) <_{\text{alt}} (4, 3, 2, 0, 2)$.

Next we generalize the definition of upward and downward crossings to pairs of two-rowed arrays $c_d|_f^e \in \{(x_1,u_\circ)| (x_2,u_\bullet)| \\ [y_1,v_\circ)| [y_2,v_\bullet)\}_{n,k}$ with $k \in \mathbb{Z}$. Suppose that $c_d \in \{(x_1,u_\circ)_{n_1} \\ [y_1,v_\circ)_{n_1+k}\}$ and $e_f \in \{(x_2,u_\bullet)_{n_2} \\ [y_2,v_\bullet)_{n_2-k}\}$, where $n_1+n_2=n$, and use the convention $c_0 := x_1$, $d_0 := y_1$, $c_{n_1+1} := u_\circ$, $d_{n_1+k+1} := v_\circ$, $e_0 := x_2$, $f_0 := y_2$, $e_{n_2+1} := u_\bullet$, $f_{n_2-k+1} := v_\bullet$. Let $m_1 = \min(n_1, n_1+k)$ and $m_2 = \min(n_2, n_2-k)$. Then $c_d|_f^e$ has an upward crossing at $(c_i, f_j)$ if $0 \le i \le m_1$ and $1 \le j \le m_2+1$, and conditions $(i^\uparrow)$ and $(ii^\uparrow)$ hold. Similarly, it has a downward crossing at $(e_j, d_i)$ if $1 \le i \le m_1+1$ and $0 \le j \le m_2$, and conditions $(i^\downarrow)$ and $(ii^\downarrow)$ hold.

It is convenient to think of crossings of a pair of two-rowed arrays as crossings of the pair of paths obtained by truncating the arrays, similarly to what we did in Section 3.2 for single arrays. Let $T(c_d)$ be the path in $P(x_1,y_1) \to (c_{m_1+1},d_{m_1+1})$ having valleys at positions $(c_i, d_i)$ for $1 \le i \le m_1$, and let $T(e_f)$ be the path in $P(x_2,y_2) \to (e_{m_2+1},f_{m_2+1})$ having valleys at positions $(e_j, f_j)$ for $1 \le j \le m_2$. Then the upward and downward crossings of $c_d|_f^e$ can be identified with the upward and downward crossings of the pair of paths $(T(c_d), T(e_f))$. See Figure 9 for an example. In particular, upward crossings are always at vertices of the form $(c_i, f_j)$, and downward crossings are at vertices of the form $(e_j, d_i)$, for some $i, j$.
$$0 \le 3 \quad | \quad 1 < \textcircled{2} < 4 \le 4 \quad \in \left\{ \begin{matrix} (0,3) \\ [1,5) \end{matrix} \right\} \quad \begin{matrix} (1,4) \\ [0,4) \end{matrix} \quad 3,1$$

<figure><img src="image_97.png" /><figcaption>FIGURE 9. A pair of two-rowed arrays $c_d|_f^e$ with its crossing circled, and the corresponding pair of paths $(T(c_d), T(e_f))$.</figcaption></figure>

It is clear from this description that there is a natural ordering of the crossings by increasing $x$-coordinate, or equivalently, by increasing $y$-coordinate. As in the case of single arrays, the $r$th crossing of a pair of two-rowed arrays will always refer to the $r$th crossing in this ordering.

For $r \ge 0$, denote by $\{(x_1, u_\circ) \mid (x_2, u_\bullet)\}_{n,k}^{\ge r}$ the subset of $\{(x_1, u_\circ) \mid (x_2, u_\bullet)\}_{n,k}$ consisting of pairs of arrays that have at least $r$ crossings. The encoding (4.2) restricts to a bijection

$$\{\mathcal{P}_{A_1 \to B_0, A_2 \to B_\bullet}^{\ge r} : \mathrm{des}(P) + \mathrm{des}(Q) = n\} \to \{(x_1, u_\circ) \mid (x_2, u_\bullet)\}_{n,k}^{\ge r}$$

Using Equation (4.3), it follows that, if $z = x_1 + y_1 = x_2 + y_2$, then

$$H_{A_1 \to B_0, A_2 \to B_\bullet}^{\ge r}(t, q) = \sum_{n \ge 0} t^n \sum_{\substack{\mathbf{c}|\mathbf{e} \\ \mathbf{d}|\mathbf{f} \in \{(x_1, u_\circ) \mid (x_2, u_\bullet)\}_{n,k}^{\ge r}}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| + \|\mathbf{e}\| + \|\mathbf{f}\| - nz} \quad (4.7)$$

To prove Theorem 2.2, we will construct bijections between $\{(x_1, u_\circ) \mid (x_2, u_\bullet)\}_{n,k}^{\ge r}$ and sets of the form $\{(x_1, u_\circ) \mid (x_2, u_\circ)\}_{n,k}$ for some $k \in \mathbb{Z}$, and then apply Lemma 4.1.

**Lemma 4.2.** Let $r \ge 1$. If $A_1 \prec A_2$, then the $r$th crossing of a pair of arrays $c_d|_f^e \in \{(x_1, u_\circ) \mid (x_2, u_\circ)\}_{n,k}^{\ge r}$ is a downward crossing if $r$ is odd, and an upward crossing if $r$ is even.

*Proof.* Interpreting crossings of $c_d|_f^e$ as crossings of the pair of paths $(T(c_d), T(e_f))$, which start at $A_1$ and $A_2$, respectively, the fact that $A_1 \prec A_2$ implies that downward and upward crossings must alternate, with the first crossing being downward. $\square$

For $r \ge 1$, a symbol $\uparrow$ (resp. $\downarrow$) next to the superscript $\ge r$ denotes the subset of pairs of arrays where the $r$th crossing is an upward (resp. downward) crossing. For $r = 0$, in the case $A_1 \prec A_2$, we simplify define

$$\{(x_1, u_\circ) \mid (x_2, u_\bullet)\}_{n,k}^{\ge 0\uparrow} = \{(x_1, u_\circ) \mid (x_2, u_\bullet)\}_{n,k}^{\ge 0\downarrow} = \{(x_1, u_\circ) \mid (x_2, u_\bullet)\}_{n,k}^{\ge 0} = \{(x_1, u_\circ) \mid (x_2, u_\bullet)\}_{n,k} = \{(x_1, u_\circ) \mid (x_2, u_\circ)\}_{n,k} \quad (4.8)$$

by convention.
In the case $A_1 = A_2 = (x, y)$ and $B_1 = B_2 = (u, v)$, we define $\{(x,u]|(x,u[|y,v|)|y,v)\}_{n,k}^{\ge 0\uparrow}$ (resp. $\{(x,u]|(x,u)\}_{n,k}^{\ge 0\downarrow}$) to be the set of pairs $\mathbf{c}|_{\mathbf{d}}|_{\mathbf{f}}^{\mathbf{e}} \in \{(x,u]|(x,u)\}_{n,k}^{\ge 0\uparrow}$ such that $\mathbf{c}_d \neq \mathbf{e}_f$ and the leftmost entry in the usual zig-zag order where $\mathbf{c}_d$ and $\mathbf{e}_f$ differ is in the top row and satisfies $c_i < e_i$ (resp. $c_i > e_i$), or it is in the bottom row and satisfies $d_i > f_i$ (resp. $d_i < f_i$). Equivalently, $\mathbf{c}|_{\mathbf{d}}|_{\mathbf{f}}^{\mathbf{e}}$ is in the first (resp. second) set if the first step where the paths $T(\mathbf{c}|_{\mathbf{d}})$ and $T(\mathbf{e}|_{\mathbf{f}})$ disagree is an $N$ (resp. $E$) step of $T(\mathbf{c}|_{\mathbf{d}})$ and an $E$ (resp. $N$) step of $T(\mathbf{e}|_{\mathbf{f}})$. See the examples in Figure 10.

In analogy to Lemma 3.3 for single arrays, the next lemma shows how the relative locations of the two initial points and of the two final points often force the number of crossings of a pair of two-rowed arrays to have a given parity.

**Lemma 4.3.** Let $m \ge 0$.

(a) If $A_1 \prec A_2$, $B_1 \prec B_2$, and $s \ge 0$, then

$$ \{(x_1,u_2]|(x_2,u_1)]\}_{n,s}^{\ge 2m+1} = \{(x_1,u_2]|(x_2,u_1)]\}_{n,s}^{\ge 2m+1\downarrow} = \{(x_1,u_2]|(x_2,u_1)]\}_{n,s}^{\ge 2m\uparrow} = \{(x_1,u_2]|(x_2,u_1)]\}_{n,s}^{\ge 2m}, \quad (4.9) $$

$$ \{(x_1,u_1]|(x_2,u_2)]\}_{n,-s}^{\ge 2m+2} = \{(x_1,u_1]|(x_2,u_2)]\}_{n,-s}^{\ge 2m+2\uparrow} = \{(x_1,u_1]|(x_2,u_2)]\}_{n,-s}^{\ge 2m+1\downarrow} = \{(x_1,u_1]|(x_2,u_2)]\}_{n,-s}^{\ge 2m+1}. \quad (4.10) $$

(b) If $A_1 \prec A_2$ and $B_1 = B_2$, then (4.9) and (4.10) hold for $s \ge 1$.

(c) If $A_1 = A_2 = (x, y)$, $B_1 = B_2 = (u, v)$, and $s \ge 1$, then

$$ \{(x,u]|(x,u)]\}_{n,s}^{\ge 2m+1\downarrow} = \{(x,u]|(x,u)]\}_{n,s}^{\ge 2m\uparrow} \quad \text{and} \quad \{(x,u]|(x,u)]\}_{n,-s}^{\ge 2m+2\uparrow} = \{(x,u]|(x,u)]\}_{n,-s}^{\ge 2m+1\downarrow}. \quad (4.11) $$

*Proof.* In each of Equations (4.9) and (4.10) for $A_1 \prec A_2$, the two outer equalities follow from Lemma 4.2 (and convention (4.8) in the case $m = 0$), and the left-hand side is trivially contained in the right-hand side. To prove the reverse containment, we will show that the parity of the number of crossings is forced in each case.

Let us first prove Equation (4.9) with the hypotheses of part (a). Let

$$ \mathbf{c}|_{\mathbf{d}}|_{\mathbf{f}}^{\mathbf{e}} \in \{(x_1,u_2]|(x_2,u_1)]\}_{n,s}, \quad \text{so that} \quad \mathbf{c}_d \in \{(x_1,u_2]_{n_1}\}_{[y_1,v_2]_{n_1+s}} \quad \text{and} \quad \mathbf{e}_f \in \{(x_2,u_1]_{n_2-s}\}_{[y_2,v_1]_{n_2-s}} $$

for some $n_1, n_2$ summing to $n$. Crossings of $\mathbf{c}|_{\mathbf{d}}|_{\mathbf{f}}^{\mathbf{e}}$ are crossings of the pair of paths $(T(\mathbf{c}|_{\mathbf{d}}), T(\mathbf{e}|_{\mathbf{f}})) \in \mathcal{P}_{A_1 \to B'_2} \times \mathcal{P}_{A_2 \to B'_1}$, where $B'_2 = (u_2, d_{n_1+1})$ and $B'_1 = (e_{n_2-s+1}, v_1)$. Since $d_{n_1+1} \le v_2$ and $e_{n_2-s+1} \le u_1$, the condition $B_1 \prec B_2$ implies that $B'_1 \prec B'_2$. Thus, since $A_1 \prec A_2$, the number of crossings of $\mathbf{c}|_{\mathbf{d}}|_{\mathbf{f}}^{\mathbf{e}}$ must be odd, proving Equation (4.9) in this case.
4.3. **The bijections $\gamma_r$ and $\delta_r$.** The bijections $\gamma_r$ and $\delta_r$ play a similar role for pairs of two-rowed arrays as the bijections $\alpha_r$ and $\beta_r$ played for single arrays. They are reminiscent of the bijection $\theta_r$ defined in [3] for pairs of paths; however, $\gamma_r$ and $\delta_r$ do not restrict to bijections for pairs of paths, since they change the relative lengths of the rows of the arrays.

For $\mathbf{c}_d|^{\mathbf{e}}_f \in \{(x_1,u_\circ)| (x_2,u_\bullet)\mid [y_1,v_\circ)| [y_2,v_\bullet]\}_n$, we say that an upward crossing at $(c_i, f_j)$ (resp. a downward crossing at $(e_j, d_i)$) is proper if $c_i \neq u_\circ$ and $f_j \neq v_\bullet$ (resp. $e_j \neq u_\bullet$ and $d_i \neq v_\circ$), that is, neither entry equals the upper bound for its row.

For $r \ge 1$, the map $\gamma_r$ applies to pairs of two-rowed arrays $\mathbf{c}_d|^{\mathbf{e}}_f$ whose $r$th crossing is a proper upward crossing, say at $(c_i, f_j)$, and it swaps the entries to the right of $c_i$ in each row of the first array with the entries to the right of $f_j$ in each row of the second array. Schematically, we have:

<figure><img src="image_98.png" /></figure>

The fact that $(c_i, f_j)$ is a proper crossing of $\mathbf{c}_d|^{\mathbf{e}}_f$ guarantees that $c_{i+1}$ and $f_{j+1}$ exist, and that $c_i < c_{i+1}$ and $f_j < f_{j+1}$. Condition $(i^\uparrow)$ in the characterization of upward crossings implies that $c_i < e_j$, $d_i < f_{j+1}$, $e_{j-1} < c_{i+1}$ and $f_j < d_{i+1}$, and so the rows of the arrays in $\gamma_r(\mathbf{c}_d|^{\mathbf{e}}_f)$ are increasing. The pair $\gamma_r(\mathbf{c}_d|^{\mathbf{e}}_f)$ still has a crossing at $(c_i, f_j)$: condition $(i^\uparrow)$ holds because $e_{j-1} \le c_i < c_{i+1}$ and $d_i \le f_j < f_{j+1}$, and condition $(ii^\uparrow)$ holds because the relevant entries are not affected by $\gamma_r$. This crossing is clearly proper, and it is the $r$th crossing of $\gamma_r(\mathbf{c}_d|^{\mathbf{e}}_f)$ because the entries to the left of $c_i$ and $f_j$, and thus the first $r-1$ crossings of the pair of arrays, are not affected by $\gamma_r$. It follows that $\gamma_r$ is an involution.

Similarly, the map $\delta_r$ applies to pairs of two-rowed arrays $\mathbf{c}_d|^{\mathbf{e}}_f$ whose $r$th crossing is a proper downward crossing, say at $(e_j, d_i)$, and it again swaps the entries to the right of $d_i$ in the first array with the entries to the right of $e_j$ in the second array. Schematically, we have:

<figure><img src="image_99.png" /></figure>

The same argument shows that the rows of the arrays in $\delta_r(\mathbf{c}_d|^{\mathbf{e}}_f)$ are increasing, that $\delta_r(\mathbf{c}_d|^{\mathbf{e}}_f)$ still has a proper crossing at $(e_j, d_i)$, which is its $r$th crossing, and that the map $\delta_r$ is an involution. In fact, if we denote by $\zeta$ the involution that swaps the two two-rowed arrays in a pair, that is,

$$ \zeta(\mathbf{c}_d|^{\mathbf{e}}_f) = \mathbf{e}_f|^{\mathbf{c}}_d, \qquad (4.12) $$

then the maps $\gamma_r$ and $\delta_r$ are related by $\delta_r = \zeta \circ \gamma_r \circ \zeta$.
If $A_1 = A_2 = (x, y)$ and $B_1 = B_2 = (u, v)$, we can extend the definitions of $\gamma_r$ and $\delta_r$ to the case $r = 0$ as follows. Let $\mathbf{c}_d|_f^e \in \{(x,u] \mid [y,v) \mid [x,u] \mid [y,v)\}_{n,k}^{\ge 0\uparrow}$. If the leftmost entry where $\mathbf{c}_d$ and $\mathbf{e}_f$ differ is $c_i < e_i$, then the vertex $(c_i, f_i)$ satisfies condition $(i^\uparrow)$ from the characterization of upward crossings, since $e_{i-1} < c_i < e_i$ and $d_i = f_i < d_{i+1}$, even if it fails condition $(ii^\uparrow)$ since $(d_i, c_{i-1}, d_{i-1}, \dots, c_0, d_0) = (f_i, e_{i-1}, f_{i-1}, \dots, e_0, f_0)$. If $c_i \neq u$ and $f_i \neq v$, we define $\gamma_0$ by swapping the entries to the right of $c_i$ in each row of $\mathbf{c}_d$ with the entries to the right of $f_i$ in each row of $\mathbf{e}_f$, just as in the usual definition of $\gamma_r$ if $(c_i, f_i)$ had been the $r$th crossing.

If the leftmost entry where $\mathbf{c}_d$ and $\mathbf{e}_f$ differ is $d_i > f_i$, now it is the vertex $(c_{i-1}, f_i)$ that satisfies condition $(i^\uparrow)$, since $e_{i-1} = c_{i-1} < e_i$ and $d_{i-1} < f_i < d_i$. If $c_{i-1} \neq u$ and $f_i \neq v$, we define $\gamma_0$ by swapping the entries to the right of $c_{i-1}$ in each row of $\mathbf{c}_d$ with the entries to the right of $f_i$ in each row of $\mathbf{e}_f$, just as in the definition of $\gamma_r$ if $(c_{i-1}, f_i)$ had been the $r$th crossing. See the example in Figure 10.

The bijection $\delta_0$ can be defined analogously, or as $\delta_0 = \zeta \circ \gamma_0 \circ \zeta$, but it will not be needed in the proofs.

<figure><img src="image_100.png" /><figcaption>FIGURE 10. An example of the bijection $\gamma_0$. For each pair of two-rowed arrays $\mathbf{c}_d|_f^e$, the leftmost entry where they differ is $d_2 = 3 > 2 = f_2$, so $(c_1, f_2) = (2, 2)$ satisfies condition $(i^\uparrow)$. The corresponding vertex in the pair of paths $(T(\mathbf{c}_d), T(\mathbf{e}_f))$ has been marked with a dotted circle.</figcaption></figure>

**Lemma 4.4.** Fix $n \ge 0$, $k \in \mathbb{Z}$ and $r \ge 1$. Suppose that either $B_1 \prec B_2$ and $k \ge 0$, or that $B_1 = B_2$. The map $\gamma_r$ restricts to a bijection

$$ \left\{ \begin{array}{c} (x_1, u_2) \\ [y_1, v_2) \end{array} \right\} \begin{array}{c} \ge r \uparrow \\ n, k \end{array} \longleftrightarrow \left\{ \begin{array}{c} (x_1, u_1) \\ [y_1, v_1) \end{array} \right\} \begin{array}{c} \ge r \uparrow \\ n, -k-1 \end{array}. \quad (4.13) $$

The map $\delta_r$ restricts to a bijection

$$ \left\{ \begin{array}{c} (x_1, u_1) \\ [y_1, v_1) \end{array} \right\} \begin{array}{c} \ge r \downarrow \\ n, -k \end{array} \longleftrightarrow \left\{ \begin{array}{c} (x_1, u_2) \\ [y_1, v_2) \end{array} \right\} \begin{array}{c} \ge r \downarrow \\ n, k+1 \end{array}. \quad (4.14) $$

Both $\gamma_r$ and $\delta_r$ preserve the sum of the entries of the pair of arrays.

Additionally, if $A_1 = A_2$ and $B_1 = B_2$, then the above statements also hold for $r = 0$.
Proof. Suppose first that $r \ge 1$. Let us first check that pairs of arrays in the four sets above cannot have improper crossings, and so the maps $\gamma_r$ and $\delta_r$ are defined. For $\begin{bmatrix} c \\ d \end{bmatrix}_{\mathbf{f}} \in \left\{ \begin{array}{c} (x_1, u_\circ) \\ [y_1, v_\circ) \end{array} \right\}_{n,h}$, where $h \in \mathbb{Z}$, to have an improper upward crossing at $(c_i, f_j)$, we must have either $c_i = u_\circ$, in which case $u_\circ = c_i < e_j \le u_\bullet$ and $h \ge 0$, or $f_j = v_\bullet$, in which case $v_\bullet = f_j < d_{i+1} \le v_\circ$ and $h \ge 0$. Similarly, for $\begin{bmatrix} c \\ d \end{bmatrix}_{\mathbf{f}}^e$ to have an improper downward crossing at $(e_j, d_i)$, we must have either $e_j = u_\bullet$, in which case $u_\bullet = e_j < c_i \le u_\circ$ and $h \le 0$, or $d_i = v_\circ$, in which case $v_\circ = d_i < f_{j+1} \le v_\bullet$ and $h \le 0$.

If $\begin{bmatrix} c \\ d \end{bmatrix}_{\mathbf{f}}^e$ is in the left-hand side of (4.13) (resp. (4.14)) and has an improper upward (resp. downward) crossing, the previous paragraph forces $u_2 < u_1$ or $v_2 < v_1$, contradicting the hypothesis that $B_1 \prec B_2$ or $B_1 = B_2$. If $\begin{bmatrix} c \\ d \end{bmatrix}_{\mathbf{f}}^e$ is in the right-hand side instead, the forced inequalities $u_1 < u_2$ or $v_1 < v_2$ hold when $B_1 \prec B_2$, but the requirement on $h$ states that $k+1 \le 0$, contradicting the hypothesis that $k \ge 0$ in this case.

Having already seen that $\gamma_r$ and $\delta_r$ are involutions preserving the first $r$ crossings and preserving the sum of the entries, it remains to describe their images when restricted to the above sets. Let $\begin{bmatrix} c \\ d \end{bmatrix}_{\mathbf{f}}^e$ be in one of the sets in (4.13), so that one has

$$ \begin{bmatrix} c \\ d \end{bmatrix} \in \left\{ \begin{array}{c} (x_1, u_\circ]_{n_1} \\ [y_1, v_\circ)_{n_1+h} \end{array} \right\} \quad \text{and} \quad \begin{bmatrix} e \\ f \end{bmatrix} \in \left\{ \begin{array}{c} (x_2, u_\bullet]_{n_2} \\ [y_2, v_\bullet)_{n_2-h} \end{array} \right\} $$

for some $n_1, n_2$ summing to $n$, and $h \in \mathbb{Z}$. If the $r$th crossing of $\begin{bmatrix} c \\ d \end{bmatrix}_{\mathbf{f}}^e$ is an upward crossing at $(c_i, f_j)$, then

$$ \gamma_r(\begin{bmatrix} c \\ d \end{bmatrix}_{\mathbf{f}}^e) \in \left\{ \begin{array}{c} (x_1, u_\bullet]_{n_2+i-j+1} \\ [y_1, v_\bullet)_{n_2-h+i-j} \end{array} \right\} \times \left\{ \begin{array}{c} (x_2, u_\circ]_{n_1-i+j-1} \\ [y_2, v_\circ)_{n_1+h-i+j} \end{array} \right\} \subseteq \left\{ \begin{array}{c} (x_1, u_\bullet] \\ [y_1, v_\bullet) \end{array} \right\} \quad \begin{bmatrix} x_2, u_\circ \\ [y_2, v_\circ) \end{bmatrix}_{n, -h-1} $$

When $h \in \{-k, -k-1\}$, then $-h-1$ equals the other element in the set, so this argument works in both directions.

Similarly, if $\begin{bmatrix} c \\ d \end{bmatrix}_{\mathbf{f}}^e$ is in one of the sets in (4.14) and its $r$th crossing is a downward crossing at $(e_j, d_i)$, then

$$ \delta_r(\begin{bmatrix} c \\ d \end{bmatrix}_{\mathbf{f}}^e) \in \left\{ \begin{array}{c} (x_1, u_\bullet]_{n_2+i-j-1} \\ [y_1, v_\bullet)_{n_2-h+i-j} \end{array} \right\} \times \left\{ \begin{array}{c} (x_2, u_\circ]_{n_1-i+j+1} \\ [y_2, v_\circ)_{n_1+h-i+j} \end{array} \right\} \subseteq \left\{ \begin{array}{c} (x_1, u_\bullet] \\ [y_1, v_\bullet) \end{array} \right\} \quad \begin{bmatrix} x_2, u_\circ \\ [y_2, v_\circ) \end{bmatrix}_{n, -h+1} $$

When $h \in \{-k, k+1\}$, then $-h+1$ equals the other element in the set.

Finally, in the case that $A_1 = A_2$ and $B_1 = B_2$, a similar argument shows that the maps $\gamma_0$ and $\delta_0$ are defined and they are bijections between the stated sets. $\square$

**4.4. Proof of Theorem 2.2.** The proof is divided into four cases according to which endpoints of the paths coincide. In each case, we determine $H_{A_1 \to B_0, A_2 \to B_\bullet}^{\ge r}(t, q)$ by first using Equation (4.7) to write it as a sum over pairs of two-rowed arrays. Then we repeatedly apply the maps from Lemma 4.4 to construct bijections between $\left\{ \begin{bmatrix} (x_1, u_\circ) \\ [y_1, v_\circ) \end{bmatrix} \right\}_n^{\ge r}$ and certain sets of pairs of two-rowed arrays with no requirement on the number of crossings, and finally we use Lemma 4.1 to obtain the desired expressions. Again, the cases are labeled as in [3] for consistency.
**Case 1:** endpoints $A_1 \prec A_2$ and $B_1 \prec B_2$. If $P \in \mathcal{P}_{A_1 \to B_2}$ and $Q \in \mathcal{P}_{A_2 \to B_1}$, the relative position of the endpoints forces $\chi(P, Q)$ to be odd, which proves the first equality in Equation (2.16). Using Lemmas 4.3 and 4.4, we construct a sequence of bijections $\delta_1 \circ \gamma_2 \circ \dots \circ \delta_{2m-1} \circ \gamma_{2m}$:

$$ \begin{align} \left\{ \begin{array}{c} (x_1, u_2) \\ [y_1, v_2) \end{array} \right\}_{n}^{\ge 2m} &= \left\{ \begin{array}{c} (x_1, u_2) \\ [y_1, v_2) \end{array} \right\}_{n,0}^{\ge 2m \uparrow} \xrightarrow{\gamma_{2m}} \left\{ \begin{array}{c} (x_1, u_1) \\ [y_1, v_1) \end{array} \right\}_{n,-1}^{\ge 2m \uparrow} = \left\{ \begin{array}{c} (x_1, u_1) \\ [y_1, v_1) \end{array} \right\}_{n,-1}^{\ge 2m-1 \downarrow} \nonumber \\ & \xrightarrow{\delta_{2m-1}} \left\{ \begin{array}{c} (x_1, u_2) \\ [y_1, v_2) \end{array} \right\}_{n,2}^{\ge 2m-1 \downarrow} = \left\{ \begin{array}{c} (x_1, u_2) \\ [y_1, v_2) \end{array} \right\}_{n,2}^{\ge 2m-2 \uparrow} \nonumber \\ & \xrightarrow{\gamma_{2m-2}} \dots \xrightarrow{\delta_1} \left\{ \begin{array}{c} (x_1, u_2) \\ [y_1, v_2) \end{array} \right\}_{n,2m}^{\ge 1 \downarrow} = \left\{ \begin{array}{c} (x_1, u_2) \\ [y_1, v_2) \end{array} \right\}_{n,2m}^{\ge 0 \uparrow} = \left\{ \begin{array}{c} (x_1, u_2) \\ [y_1, v_2) \end{array} \right\}_{n,2m}, \tag{4.15} \end{align} $$

where the last equality comes from (4.8). See Figure 11 for an example. Since these bijections preserve the sum of the entries of the arrays, Equation (4.7) and Lemma 4.1 give

$$ H_{A_1 \to B_2, A_2 \to B_1}^{\ge 2m}(t, q) = \sum_{n \ge 0} t^n \sum_{\substack{\mathbf{c} \\ \mathbf{d}}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| + \|\mathbf{e}\| + \|\mathbf{f}\| - nz} = f_{2m, A_1, A_2, B_2, B_1}(t, q), $$

proving Equation (2.16).

$$ \begin{align*} \left\{ \begin{array}{c} (0,10) \\ [2,7) \end{array} \right\}_{6}^{\ge 2} &= \left\{ \begin{array}{c} (0,10) \\ [2,7) \end{array} \right\}_{6,0}^{\ge 2 \uparrow} \xrightarrow{\gamma_2} \left\{ \begin{array}{c} (0,8) \\ [2,8) \end{array} \right\}_{6,-1}^{\ge 2 \uparrow} = \left\{ \begin{array}{c} (0,8) \\ [2,8) \end{array} \right\}_{6,-1}^{\ge 1 \downarrow} \\ 0 < 3 < \textcolor{orange}{6} \le 10 \quad \middle| \quad 2 < \textcolor{orange}{3} < 4 < 7 < \textcolor{orange}{8} \le 8 & 0 < 3 < \textcolor{orange}{6} < 7 < \textcolor{orange}{8} \le 8 \quad \middle| \quad 2 < \textcolor{orange}{3} < 4 \le 10 \\ 2 \le 2 < \textcolor{orange}{4} < 7 \quad \middle| \quad 0 \le 2 < 5 < \textcolor{orange}{6} < 7 < 8 & 0 \le 2 < 5 < \textcolor{orange}{6} < 7 \quad \middle| \quad 0 \le 2 < 7 < 8 \end{align*} \right. \\ & \xrightarrow{\delta_1} \left\{ \begin{array}{c} (0,10) \\ [2,7) \end{array} \right\}_{6,2}^{\ge 1 \downarrow} = \left\{ \begin{array}{c} (0,10) \\ [2,7) \end{array} \right\}_{6,2}^{\ge 1 \uparrow} \\ 0 < 3 < 4 \le 10 \quad \middle| \quad 2 < \textcolor{orange}{3} < 6 < 7 < 8 \le 8 \\ 2 \le 2 < \textcolor{orange}{4} < 5 < 6 < 7 \quad \middle| \quad 0 \le 2 < 7 < 8 \end{align*} $$

FIGURE 11. An example of the bijection (4.15), where $m=1$ and $n=6$.

Similarly, if $P \in \mathcal{P}_{A_1 \to B_1}$ and $Q \in \mathcal{P}_{A_2 \to B_2}$, then $\chi(P, Q)$ must be even, which proves the first equality in Equation (2.17). In this case, we construct a sequence of bijections $\delta_1 \circ \gamma_2 \circ \dots \circ \delta_{2m+1}$:

$$ \begin{align*} \left\{ \begin{array}{c} (x_1, u_1) \\ [y_1, v_1) \end{array} \right\}_{n}^{\ge 2m+1} &= \left\{ \begin{array}{c} (x_1, u_1) \\ [y_1, v_1) \end{array} \right\}_{n,0}^{\ge 2m+1 \downarrow} \xrightarrow{\delta_{2m+1}} \left\{ \begin{array}{c} (x_1, u_2) \\ [y_1, v_2) \end{array} \right\}_{n,1}^{\ge 2m+1 \downarrow} = \left\{ \begin{array}{c} (x_1, u_2) \\ [y_1, v_1) \end{array} \right\}_{n,1}^{\ge 2m \uparrow} \\ & \xrightarrow{\gamma_{2m}} \left\{ \begin{array}{c} (x_1, u_1) \\ [y_1, v_1) \end{array} \right\}_{n,-2}^{\ge 2m \uparrow} = \left\{ \begin{array}{c} (x_1, u_1) \\ [y_1, v_1) \end{array} \right\}_{n,-2}^{\ge 2m-1 \downarrow} \\ & \xrightarrow{\delta_{2m-1}} \dots \xrightarrow{\delta_1} \left\{ \begin{array}{c} (x_1, u_2) \\ [y_1, v_2) \end{array} \right\}_{n,2m+1}^{\ge 1 \downarrow} = \left\{ \begin{array}{c} (x_1, u_2) \\ [y_1, v_2) \end{array} \right\}_{n,2m+1}. \end{align*} $$

Equation (4.7) and Lemma 4.1 now give

$$ H_{A_1 \to B_1, A_2 \to B_2}^{\ge 2m+1}(t, q) = \sum_{n \ge 0} t^n \sum_{\substack{\mathbf{c} \\ \mathbf{d}}} q^{\|\mathbf{c}\| + \|\mathbf{d}\| + \|\mathbf{e}\| + \|\mathbf{f}\| - nz} = f_{2m+1, A_1, A_2, B_2, B_1}(t, q), $$

proving Equation (2.17).

We now handle Case 3, followed by Cases 2 and 4.
**Case 3:** endpoints $A_1 \prec A_2$ and $B$. If $P \in \mathcal{P}_{A_1 \to B}$ and $Q \in \mathcal{P}_{A_2 \to B}$, the parity of $\chi(P, Q)$ is no longer forced by the endpoints, so we consider two cases. When $r = 2m$ for some $m \ge 1$, the $r$th crossing is an upward crossing by Lemma 4.2, and Lemmas 4.3 and 4.4 give a sequence of bijections $\delta_1 \circ \gamma_2 \circ \dots \circ \delta_{2m-1} \circ \gamma_{2m}$:

$$ \begin{aligned} \left\{ \begin{array}{c} (x_1, u) \\ [y_1, v] \end{array} \right\} \begin{array}{c} \ge 2m \\ \left\{ \begin{array}{c} (x_2, u) \\ [y_2, v] \end{array} \right\} \end{array} \underset{n, 0}{\stackrel{\gamma_{2m}}{\longrightarrow}} \begin{array}{c} \ge 2m \uparrow \\ \left\{ \begin{array}{c} (x_1, u) \\ [y_1, v] \end{array} \right\} \end{array} \begin{array}{c} \ge 2m \uparrow \\ \left\{ \begin{array}{c} (x_2, u) \\ [y_2, v] \end{array} \right\} \end{array} \underset{n, -1}{\stackrel{\gamma_{2m-1}}{\longrightarrow}} \begin{array}{c} \ge 2m-1 \downarrow \\ \left\{ \begin{array}{c} (x_1, u) \\ [y_1, v] \end{array} \right\} \end{array} \begin{array}{c} \ge 2m-1 \downarrow \\ \left\{ \begin{array}{c} (x_2, u) \\ [y_2, v] \end{array} \right\} \end{array} \underset{n, 2}{\stackrel{\delta_{2m-1}}{\longrightarrow}} \begin{array}{c} \ge 2m-1 \uparrow \\ \left\{ \begin{array}{c} (x_1, u) \\ [y_1, v] \end{array} \right\} \end{array} \begin{array}{c} \ge 2m-2 \uparrow \\ \left\{ \begin{array}{c} (x_2, u) \\ [y_2, v] \end{array} \right\} \end{array} \underset{n, 2}{\stackrel{\delta_{2m}}{\longrightarrow}} \begin{array}{c} \ge 2m-2 \downarrow \\ \left\{ \begin{array}{c} (x_1, u) \\ [y_1, v] \end{array} \right\} \end{array} \end{aligned} \quad (4.16) $$

using again (4.8). Equation (4.7) and Lemma 4.1 give

$$ H_{A_1 \to B, A_2 \to B}^{\ge 2m}(t, q) = \sum_{n \ge 0} t^n \sum_{\substack{\mathbf{c} \\ \mathbf{d}} \mid \mathbf{e} \\ \mathbf{f} \in \left\{ \begin{array}{c} (x_1, u) \\ [y_1, v] \end{array} \right\} \begin{array}{c} (x_2, u) \\ [y_2, v] \end{array} \right\}_{n, 2m} q^{\|\mathbf{c}\|+\|\mathbf{d}\|+\|\mathbf{e}\|+\|\mathbf{f}\|-nz} = f_{2m, A_1, A_2, B, B}(t, q), $$

proving Equation (2.19) for even $r$.

When $r = 2m+1$ for some $m \ge 0$, the $r$th crossing is a downward crossing by Lemma 4.2, and we get a sequence of bijections $\delta_1 \circ \gamma_2 \circ \dots \circ \delta_{2m+1}$:

$$ \begin{aligned} \left\{ \begin{array}{c} (x_1, u) \\ [y_1, v] \end{array} \right\} \begin{array}{c} \ge 2m+1 \\ \left\{ \begin{array}{c} (x_2, u) \\ [y_2, v] \end{array} \right\} \end{array} \underset{n, 0}{\stackrel{\delta_{2m+1}}{\longrightarrow}} \begin{array}{c} \ge 2m+1 \downarrow \\ \left\{ \begin{array}{c} (x_1, u) \\ [y_1, v] \end{array} \right\} \end{array} \begin{array}{c} \ge 2m+1 \downarrow \\ \left\{ \begin{array}{c} (x_2, u) \\ [y_2, v] \end{array} \right\} \end{array} \underset{n, 1}{\stackrel{\gamma_{2m}}{\longrightarrow}} \begin{array}{c} \ge 2m \uparrow \\ \left\{ \begin{array}{c} (x_1, u) \\ [y_1, v] \end{array} \right\} \end{array} \begin{array}{c} \ge 2m \uparrow \\ \left\{ \begin{array}{c} (x_2, u) \\ [y_2, v] \end{array} \right\} \end{array} \underset{n, -1}{\stackrel{\gamma_{2m-1}}{\longrightarrow}} \begin{array}{c} \ge 2m \uparrow \\ \left\{ \begin{array}{c} (x_1, u) \\ [y_1, v] \end{array} \right\} \end{array} \begin{array}{c} \ge 2m \uparrow \\ \left\{ \begin{array}{c} (x_2, u) \\ [y_2, v] \end{array} \right\} \end{array} \underset{n, -2}{\stackrel{\gamma_{2m-1}}{\longrightarrow}} \begin{array}{c} \ge 2m \uparrow \\ \left\{ \begin{array}{c} (x_1, u) \\ [y_1, v] \end{array} \right\} \end{array} \begin{array}{c} \ge 2m-1 \downarrow \\ \left\{ \begin{array}{c} (x_2, u) \\ [y_2, v] \end{array} \right\} \end{array} \underset{n, -2}{\stackrel{\delta_{2m-1}}{\longrightarrow}} \dots \stackrel{\delta_{2m-1}}{\longrightarrow} \begin{array}{c} \ge 2m \downarrow \\ \left\{ \begin{array}{c} (x_1, u) \\ [y_1, v] \end{array} \right\} \end{array} \begin{array}{c} \ge 2m \downarrow \\ \left\{ \begin{array}{c} (x_2, u) \\ [y_2, v] \end{array} \right\} \end{array} \underset{n, 2m+1}{\stackrel{\delta_{2m}}{\longrightarrow}} \begin{array}{c} \ge 2m \downarrow \\ \left\{ \begin{array}{c} (x_1, u) \\ [y_1, v] \end{array} \right\} \end{array} \begin{array}{c} \ge 2m \downarrow \\ \left\{ \begin{array}{c} (x_2, u) \\ [y_2, v] \end{array} \right\} \end{array} \underset{n, 2m+1}{\stackrel{\delta_{2m}}{\longrightarrow}} \dots \stackrel{\delta_{2m}}{\longrightarrow} \begin{array}{c} \ge 2m \downarrow \\ \left\{ \begin{array}{c} (x_1, u) \\ [y_1, v] \end{array} \right\} \end{array} \end{aligned} \quad (4.17) $$

from where

$$ H_{A_1 \to B_1, A_2 \to B_2}^{\ge 2m+1}(t, q) = \sum_{n \ge 0} t^n \sum_{\substack{\mathbf{c} \\ \mathbf{d}} \mid \mathbf{e} \\ \mathbf{f} \in \left\{ \begin{array}{c} (x_1, u) \\ [y_1, v] \end{array} \right\} \begin{array}{c} (x_2, u) \\ [y_2, v] \end{array} \right\}_{n, 2m+1} q^{\|\mathbf{c}\|+\|\mathbf{d}\|+\|\mathbf{e}\|+\|\mathbf{f}\|-nz} = f_{2m+1, A_1, A_2, B, B}(t, q), $$

proving Equation (2.19) for odd $r$.

**Case 2:** endpoints $A$ and $B_1 \prec B_2$. We will reduce this case to Case 3 by applying the involution $\nu$, defined above Equation (3.27), componentwise to each of the two-rowed arrays in a pair. With some abuse of notation, we also denote this map on pairs of two-rowed arrays by $\nu$. It restricts to a bijection

$$ \left\{ \begin{array}{c} (x_1, u_1) \\ [y_1, v_1) \end{array} \right\}_{n, k} \stackrel{\nu}{\longleftrightarrow} \left\{ \begin{array}{c} (-v_1, -y) \\ [-u_1, -x) \end{array} \right\}_{n, -k} \left\{ \begin{array}{c} (-v_2, -y) \\ [-u_2, -x) \end{array} \right\}_{n, -k} $$

for any $k \in \mathbb{Z}$. In the case $k = 0$, translating $\nu$ into a map on pairs of paths via the encoding (4.2) yields the involution that reflects each path along the line $x + y = 0$. In particular, it preserves the number of crossings, so it restricts to a bijection

$$ \left\{ \begin{array}{c} (x_1, u_1) \\ [y_1, v_1) \end{array} \right\}_{n} \stackrel{\nu}{\longleftrightarrow} \left\{ \begin{array}{c} (-v_1, -y) \\ [-u_1, -x) \end{array} \right\}_{n} \left\{ \begin{array}{c} (-v_2, -y) \\ [-u_2, -x) \end{array} \right\}_{n} \stackrel{\nu}{\geq} \left\{ \begin{array}{c} (x_2, u_2) \\ [y_2, v_2) \end{array} \right\}_{n} $$

The hypothesis $(u_1, v_1) \prec (u_2, v_2)$ implies that the initial points of the reflected paths satisfy $(-v_1, -u_1) \prec (-v_2, -u_2)$, whereas the final point is the same for both paths, namely $(-y, -x)$. This allows us to apply Case 3.