Rational Dyck Excursion Counts as Sums of Generalized Fuss-Catalan Products

Introduction

A nonempty walk can return to zero only if its increments have opposite signs. We write these increments as $+p$ and $-q$, where $p$ and $q$ are coprime positive integers denoting the jump magnitudes. A weak excursion starts and ends at zero and stays nonnegative; a strict excursion is positive between its endpoints. A weak meander starts at zero and stays nonnegative, but need not return to zero. A positive meander starts at zero and stays strictly positive at every later step. In the special case where the downward jump has magnitude one ($q = 1$), the weak and strict excursion counts are given by Fuss–Catalan and shifted Raney numbers, respectively. We seek expressions for these counts in terms of the same coefficient family when $q > 1$. We give weighted sums of generalized Fuss–Catalan products. These formulas sum over partitions of the jump magnitude $q$, rather than partitions of the path size. For each partition, the indices in the products must satisfy certain divisibility conditions.

For original jump magnitudes $p_0$, $q_0$, put $g = \gcd(p_0, q_0)$ and $p = p_0/g$, $q = q_0/g$. We call this normalization; dividing all heights by $g$ preserves the weak and strict excursion counts. After normalization, a returning walk of size $n$ has $qn$ upward steps and $pn$ downward steps, hence $(p + q)n$ steps altogether.

Figure 1 shows three walks with jumps +4 and −3 that return to zero after fourteen steps. The first is strict, the second is weak with an interior return to zero, and the third goes below zero.

These formulas include Duchon’s sequence A060941, the corresponding strict excursion sequence A293946 at positive indices, and the weak excursion sequences A300386, A300390, and A300391 in the On-Line Encyclopedia of Integer Sequences [16]. When one jump has magnitude one, they recover the integer-parameter Fuss–Catalan and Raney sequences. The contribution is a common product representation for these established excursion sequences.

To express the excursion counts in one coefficient family, we use the two-parameter Fuss–Catalan coefficients. For $\alpha> 1$, let $F_\alpha(x)$ be the formal power series with constant term one satisfying

For $\beta> 0$ and a nonnegative integer $m$, define

Brackets denote coefficient extraction: $[x^m]f(x)$ is the coefficient of $x^m$ in $f(x)$. With two variables, $[t^a x^b]f(t, x)$ is the coefficient of $t^a x^b$ in $f(t, x)$. The same convention applies with any choice of variables. When $\alpha$ is an integer, $\beta= 1$ gives the usual Fuss–Catalan numbers, and positive integer $\beta$ gives their Raney extension. Our formulas use positive rational values of $\alpha$ and $\beta$, so the individual coefficients need not be integers.

Raney [18] develops the composition and reversion framework behind these coefficients, and Gessel [11, Section 3.3] gives the power identity in (1). Lin [14] treats their integer-parameter interpretations. Partition-indexed Fuss–Catalan product identities also arise from the determinant expansions of Goy and Shattuck [12]. Here the partitioned integer is the jump $q$, and the parameters and residue restrictions of the factors are determined by $p$, $q$ and the partition parts.

The enumeration of rational Dyck paths is well known in the literature. Bizley [5] proves Grossman’s formula and counts paths with prescribed numbers of boundary contacts, covering both weak and strict excursions. Birmajer, Gil, and Weiner [4] express these counts using Bell polynomials. The factor-free words studied in these works and by Duchon [7] satisfy a stronger restriction than strict excursions. A strict excursion starts and ends at zero and stays strictly positive in between. Within such an excursion, a shorter segment may start and end at the same positive height and stay at or above that height throughout. Such a segment is a Dyck factor above zero.

Put $h = p + q$, and let $E(z)$ and $T(z)$ be the generating functions for weak and nonempty strict excursions, respectively, with $z^n$ marking length $hn$. The empty path contributes one to $E(z)$. Cutting a weak excursion at its interior returns to zero gives a unique ordered sequence of strict excursions. Multiplication counts successive choices of pieces, so

The Grossman–Bizley formula for $E(z)$ and the resulting expression for $T(z)$ are

Expanding the exponential results in sums indexed by partitions of the path size $n$. Theorem 1 instead indexes the products by partitions of the jump magnitude $q$: the weak formula alternates in sign with the number of partition parts, whereas every strict summand is positive.

The proof uses the walk factorization of Gessel [10] and Xin [22], obtained by cutting an unrestricted walk at its first and last visits to its minimum height. The middle piece is a weak excursion relative to that height. Deleting the final $-q$ step of a strict excursion leaves a positive walk ending at $q$. Expanding the positive endpoint factor distributes the endpoint height $q$ among partition parts and gives the strict product formula. The weak formula comes from the reciprocal of the negative endpoint factor, whose expansion produces the alternating signs. Section 4 gives a combinatorial interpretation of the integer multiples of the Fuss–Catalan factors.

Related convolution formulas have been obtained using the kernel method for paths below a line of rational slope. Sato’s matrix formulation [19] is reproduced by Krattenthaler [13, Section 10.5]; Banderier and Flajolet [1, Example 5] give a convolution of generalized binomial coefficients whose number of factors is independent of the path size, and attribute it to Sato.

Banderier and Wallner [3] use roots of unity and Lagrange inversion, while Bousquet-Mélou [6] expresses elementary symmetric functions in terms of power sums. In contrast, here we express weak and strict excursion counts as Fuss–Catalan products with explicit congruence conditions and positive parameters in the strict formula.

Panfil, Stošić, and Sułkowski [17] reproduce a root-of-unity convolution in their study of lattice paths and torus knots. Ek [8] develops computational methods for lattice-walk generating functions, and Firoozi, Jedwab, and Rattan [9] count paths according to the number of lattice points above a boundary of rational slope. The minimal bridges studied by Lou and Brown [15] avoid interior lattice points on the boundary but may cross it, whereas strict excursions stay strictly on one side between their endpoints.

The authors’ original motivation came from additive wealth processes [20, 21], which also provide an application context. For independent increments $+p$ and $-q$ with fixed probabilities, all walks with fixed numbers of upward and downward steps have the same probability of occurring. In Section 7, we use this fact to convert the excursion counts into probabilities of weak and strict returns. We also give probabilities for first entry at or below zero from initial height $p$, distinguishing exact landings at zero from overshoots.

Section 2 states the product formulas; Section 3 derives them from endpoint factorization and then gives their shifted forms. Their integer scalings are developed in Section 4. Sections 5 and 6 give sequence specializations and OEIS indexing. Appendix A collects expanded binomial formulas.

Fuss–Catalan product formulas

Throughout, $p$, $q$ are coprime positive integers and $h=p+q$. We index returning walks by their size $n$, so size $n$ means $hn$ steps. For a walk represented by an increment sequence $(x_1,\ldots,x_{hn})$ in $\{p,-q\}$, put $H_0=0$ and $H_j=x_1+\cdots+x_j$ for $1\leq j\leq hn$. For $n\geq0$, let $E_n^{(p,q)}$ count weak excursions of size $n$, that is, walks with $H_{hn}=0$ and $H_j\geq0$ for $0\leq j\leq hn$. For $n\geq1$, let $T_n^{(p,q)}$ count strict excursions of size $n$, with $H_{hn}=0$ and $H_j>0$ for $1\leq j<hn$. We take $E_0^{(p,q)}=1$ and $T_0^{(p,q)}=0$. Let $u$ and $d$ be the numbers of upward and downward steps.

A return to zero requires $pu=qd$, and the total length gives $u+d=hn$. Together these equations yield $u=qn$ and $d=pn$. Replacing each upward step by an east step and each downward step by a north step gives a lattice path from $(0,0)$ to $(qn,pn)$. At a vertex $(x,y)$, the height of the original walk is $px-qy$. This implies that a weak excursion corresponds to a path on or below the line $y=(p/q)x$. Furthermore, a strict excursion corresponds to a path that starts and ends on this line and stays strictly below it in between.

Write $\lambda=(\lambda_1,\ldots,\lambda_\ell)\vdash q$ for a partition of $q$ into $\ell=\ell(\lambda)$ positive parts, listed in nonincreasing order. Let $m_r(\lambda)$ be the number of occurrences of the part $r$, and define

For $q=3$, we obtain:

$\lambda$	$\ell(\lambda)$	Nonzero multiplicities	$z_\lambda$
$(3)$	$1$	$m_3=1$	$3^1 1! = 3$
$(2,1)$	$2$	$m_2=m_1=1$	$2^1 1! 1^1 1! = 2$
$(1,1,1)$	$3$	$m_1=3$	$1^3 3! = 6$

In the last row, $m_1=3$ gives the factor $3!$; all other multiplicities are zero. For every path size $n$, the formulas below sum over these same partitions of $q$. All summation indices are nonnegative integers. A sum over an empty index set is zero, and each displayed congruence is imposed separately on every factor. Congruences modulo 1 impose no restriction.

We use the coefficients $C_{\alpha,\beta}(m)$ defined in (1). In the weak formula, their parameters are $\alpha=h/q$ and $\beta=\lambda_j/q$, and their index $u_j$ is the number of upward steps in the associated auxiliary walk. In the strict formula, their parameters are $\alpha=h/p$ and $\beta=\lambda_j/p$, and their index $d_j$ is the number of downward steps in its auxiliary walk.