betaFeedback

WorksMathematics

Riordan lattice paths counted by area

Abstract

We study Riordan paths enumerated by the area between the path and the axis. We show that the generating function satisfies a qq-Riccati equation and can be written in a closed form as a ratio of basic hypergeometric series. The auxiliary series admits an algebraic representation as the motivic generating series of a symmetric two-node quiver. We obtain explicit formulas for the coefficients, the exponential asymptotics of the number of paths of given area, and a linear recurrence whose coefficients are signed counts of partitions into distinct parts. For a random path of area nn we obtain a joint Gaussian limit law for the numbers of returns, horizontal steps and up steps. The height is of order log⁡n\sqrt{\log n}, and its distribution concentrates on two adjacent integers determined explicitly by nn.

Introduction

Lattice paths weighted by area appear in polymer and vesicle models [1, 2], in the study of exclusion statistics and Hofstadter-type Hamiltonians [3, 4, 5], and in knot theory.1 Namely, in the so-called knots-quivers correspondence [9, 10, 11] certain families of paths below lines of rational slope encode coloured HOMFLY-PT invariants of torus knots. For several directed-path models, qq-difference equations and quotients of qq-series provide a useful description of the generating functions. For further developments in the knot-theoretic direction see [12, 13, 14, 15] and the review [16].

In this paper we study Riordan paths at fixed area. Recall that a Motzkin path of length nn runs from (0,0)(0,0) to (n,0)(n,0) with steps U=(1,1)U=(1,1), D=(1,−1)D=(1,-1) and H=(1,0)H=(1,0) and never passes below the xx-axis. A Riordan path is a Motzkin path with no horizontal steps on the axis, and a Dyck path has no horizontal steps at all. Enumeration by length gives the Riordan numbers 1,0,1,1,3,6,15,36,91,…1, 0, 1, 1, 3, 6, 15, 36, 91, \ldots and the Catalan numbers, respectively. Here we instead fix the area between the path and the axis, and we assign the weight xx to each up step and the weight yy to each horizontal step.

Let us mention that length-area generating functions for Motzkin meanders with boundary markers were obtained by Polychronakos [2]; setting the weight of horizontal steps on the floor to zero in his formulas gives the Riordan case. Counts with prescribed step profiles were also studied by Gan, Ouvry and Polychronakos [4]. Here we use these path decompositions to study the fixed-area ensemble. We give explicit coefficient formulas and a partition recurrence, and determine the exponential growth, additive statistics and height distribution at large area. We also express the auxiliary qq-series as the generating series of a symmetric two-node quiver; this is an algebraic identity, without an associated knot invariant.

Let Sn(x,y)S_n(x,y) be the weight polynomial of the paths of area nn and let F(x,y;q)=∑n≥0Sn(x,y)qnF(x,y;q)=\sum_{n\geq0}S_n(x,y)q^n. As the point of departure one may regard the following functional equation,

F(x,y;q)−1=qF(xq2,yq;q)[(x+y)F(x,y;q)−y],(1)F(x,y;q)-1=qF(xq^2,yq;q)\left[(x+y)F(x,y;q)-y\right], \tag*{(1)}

which follows from a decomposition of the path at its first horizontal step at height one or its first return to the axis. The substitutions x↦xq2x\mapsto xq^2 and y↦yqy\mapsto yq account for the area gained when a path is lifted by one level. A continued fraction expansion then leads to the closed form

F(x,y;q)=A(q)A(q)−xqA(q2),A(z)=∑n=0∞(−1)nq(n2)pn(x,y;q)(q;q)nzn,(2)F(x,y;q)=\frac{A(q)}{A(q)-xqA(q^2)},\qquad A(z)=\sum_{n=0}^{\infty}\frac{(-1)^nq^{\binom{n}{2}}p_n(x,y;q)}{(q;q)_n}z^n, \tag*{(2)}

where pnp_n stand for homogeneous forms of the Rogers continuous qq-Hermite polynomials, defined in § 4. Here and below we use the standard notation

(a;q)n=(1−a)(1−aq)⋯(1−aqn−1),(a;q)∞=∏j≥0(1−aqj),(a;q)_n=(1-a)(1-aq)\cdots(1-aq^{n-1}),\qquad(a;q)_\infty=\prod_{j\geq0}(1-aq^j),

with (a;q)0=1(a;q)_0=1 and ∣q∣<1|q|<1. The identity (2) holds as a formal power series in qq, and the quotient also gives the meromorphic continuation of FF to the unit disc. For y=0y=0 it reduces to the Rogers-Ramanujan type formula for Dyck paths counted by area [17, 18]. After the substitution x=αβx=\alpha\beta, y=α+βy=\alpha+\beta, the series AA turns out to be the motivic generating series of the quiver with adjacency matrix (1111)\left(\begin{smallmatrix}1&1\\1&1\end{smallmatrix}\right). This allows one to compare (2) with the quiver-series expressions for area-weighted Schröder paths [10, 11], although by itself it does not give a knot interpretation of Riordan paths.

The rest of the paper is organized as follows. In § 2 we define the area polynomials and list the first examples. In § 3 we prove the functional equation (1) and derive a recurrence for the polynomials SnS_n. In § 4 we obtain the continued fraction and the closed form (2), including the case of bounded height. In § 5 we give explicit formulas for the coefficients in terms of path profiles. In § 6 we derive the asymptotics of the number of paths and a linear recurrence with partition-theoretic coefficients. In § 7 we study the limit laws of additive statistics and of the height. We conclude with remarks and open problems.2

nnP(Hn≤2)\mathbb{P}(H_n \le2)P(Hn≤3)\mathbb{P}(H_n \le3)P(Hn>4)\mathbb{P}(H_n > 4)
3000.54515367700.99768929191.598915753⋅10−61.598915753 \cdot10^{-6}
6000.29197394760.99525395173.345151784⋅10−63.345151784 \cdot10^{-6}
15000.04485589950.98798354068.583841582⋅10−68.583841582 \cdot10^{-6}

Table 1. Height probabilities for a random Riordan path of area nn, from exact bounded-height counts.

Riordan paths and area polynomials

In this section we fix the notation and state the problem. Let us first explain how the area of a path is computed. A step from height hh to height h′h' contributes (h+h′)/2(h+h')/2 to the area. In other words, an up or down step between heights hh and h+1h+1 contributes h+12h+\frac{1}{2}, while a horizontal step at height hh contributes hh. Note that the total area is an integer, since the numbers of up and down steps are equal. Every allowed step contributes at least 12\frac{1}{2}, so a Riordan path of area nn has length at most 2n2n, and in particular there are only finitely many such paths.3 For n≥1n\geq1 we define

Sn(x,y)=∑area⁡(P)=nx#U(P)y#H(P),S0=1,(3)S_n(x,y)=\sum_{\operatorname{area}(P)=n}x^{\#U(P)}y^{\#H(P)},\qquad S_0=1, \tag*{(3)}

where the sum runs over Riordan paths of area nn, and #U(P)\#U(P) and #H(P)\#H(P) stand for the numbers of up and horizontal steps of PP. A path with ii up steps and jj horizontal steps has weight xiyjx^iy^j and length 2i+j2i+j. One can easily compute the first polynomials,

S1=x,S2=x2+xy,S3=x3+2x2y+xy2,S4=x4+3x3y+3x2y2+xy3+x2,S_1=x,\qquad S_2=x^2+xy,\qquad S_3=x^3+2x^2y+xy^2,\qquad S_4=x^4+3x^3y+3x^2y^2+xy^3+x^2,
S5=x5+4x4y+6x3y2+4x2y3+xy4+2x3+2x2y,S_5=x^5+4x^4y+6x^3y^2+4x^2y^3+xy^4+2x^3+2x^2y,

and S6,…,S10S_6,\ldots,S_{10} are listed in Appendix A. For instance, the path UHUDDUHUDD in Figure 1 has area 55 and weight x2yx^2y; it is one of the two paths giving the term 2x2y2x^2y of S5S_5. The numbers rn=Sn(1,1)r_n=S_n(1,1) of Riordan paths of area nn are, starting at n=1n=1,

The path UHUDD

Figure 1. The path UHUDDUHUDD, of area 12+1+32+32+12=5\frac{1}{2}+1+\frac{3}{2}+\frac{3}{2}+\frac{1}{2}=5.

1, 2, 4, 9, 20, 45, 101, 227, 511, 1150, 2589, 5829, 13124, 29550, …(4)1,\ 2,\ 4,\ 9,\ 20,\ 45,\ 101,\ 227,\ 511,\ 1150,\ 2589,\ 5829,\ 13124,\ 29550,\ \ldots \tag*{(4)}

with r0=1r_0=1. The Dyck sequence Sn(1,0)S_n(1,0) begins, for n≥1n\geq1, with 1,1,1,2,3,4,6,9,14,21,…1,1,1,2,3,4,6,9,14,21,\ldots and is recorded as OEIS A143951 [19].4

The functional equation

In this section we derive the functional equation (1). The key observation is very simple. If one lifts a path by one level, every step gains area 11, so the area increases by the length of the path. Since a path of weight xiyjx^iy^j has length 2i+j2i+j, the lift is represented by the substitution x↦xq2x\mapsto xq^2, y↦yqy\mapsto yq. In what follows we write F↑=F(xq2,yq;q)F^\uparrow=F(xq^2,yq;q).

Theorem 3.1. The generating function satisfies

F−1=qF↑[(x+y)F−y].(5)F-1=qF^\uparrow\bigl[(x+y)F-y\bigr]. \tag*{(5)}

For x≠0x\ne0 this can be rearranged as

F(xq2,yq;q)=F(x,y;q)−1q[(x+y)F(x,y;q)−y].F(xq^2,yq;q)=\frac{F(x,y;q)-1}{q\bigl[(x+y)F(x,y;q)-y\bigr]}.

with the factor qq cancelled formally. At x=0x=0 one has F=1F=1, and the undivided identity remains valid.

Proof. A nonempty Riordan path starts with UU. Let us read it up to the first subsequent step which either returns to the axis or is horizontal at height 11. The segment R^\widehat{R} in between is a Riordan path lifted by one level and contributes F↑F^\uparrow. If the distinguished step is DD, one has P=UR^DP′P=U\widehat{R}DP' with an arbitrary Riordan path P′P', which contributes xqF↑FxqF^\uparrow F. If the distinguished step is HH, one has P=UR^HWP=U\widehat{R}HW, and removing R^H\widehat{R}H leaves the nonempty Riordan path UWUW; this case contributes yqF↑(F−1)yqF^\uparrow(F-1). Adding the two contributions one obtains (5).

For nonzero xx, (5) is an equation of qq-Riccati type: the lifted function F↑F^\uparrow is a linear fractional transform of FF. For y=0y=0 it reduces to the equation F=1+xqF(xq2)FF=1+xqF(xq^2)F for Dyck paths counted by area, which goes back to Flajolet [17], see also [1, 18]; the Motzkin analogue was obtained by Polychronakos [2].5

Extracting the coefficient of qnq^n in (5) one obtains the following recurrence for the area polynomials,

Sn=[tn−1](∑m<ntmSm(xt2,yt))((x+y)∑p<ntpSp(x,y)−y),n≥1.(6)S_n=[t^{n-1}]\left(\sum_{m<n}t^mS_m(xt^2,yt)\right)\left((x+y)\sum_{p<n}t^pS_p(x,y)-y\right),\qquad n\geq1. \tag*{(6)}

For example, the first factor is 1+xt3+⋯1+xt^3+\cdots and the second one is x+x(x+y)t+x(x+y)2t2+x(x+y)3t3+⋯x+x(x+y)t+x(x+y)^2t^2+x(x+y)^3t^3+\cdots, so that S4=x(x+y)3+x2S_4=x(x+y)^3+x^2. Actually, the substitution Sm(xt2,yt)S_m(xt^2,yt) retains the information about the length, which is needed for the lift, and as a result (6) does not close on the numbers rnr_n alone. A scalar recurrence for rnr_n will be given in Theorem 6.3.

Continued fraction and closed form

In this section we obtain the continued fraction expansion of FF and, from it, the closed form (2); we only need the simplest ingredients of the approach of Flajolet [17]. Let MhM_h be the generating function of Motzkin paths based at height h≥1h \ge1, with the area measured from the xx-axis. Such a path is a sequence of horizontal steps and excursions above height hh, and therefore Mh=1/(1−yqh−xq2h+1Mh+1)M_h=1/(1-yq^h-xq^{2h+1}M_{h+1}) and F=1/(1−xqM1)F=1/(1-xqM_1). In other words,

F=11−xq1−yq−xq31−yq2−xq51−yq3−⋯(7)F=\frac{1}{1-\cfrac{xq}{1-yq-\cfrac{xq^3}{1-yq^2-\cfrac{xq^5}{1-yq^3-\cdots}}}} \tag*{(7)}

Paths of bounded height

Let us first look at the convergents of (7). Truncating the continued fraction at level k≥1k \ge1 one obtains the generating function F[k]F^{[k]} of paths of height at most kk; for k=0k=0 one has F[0]=1F^{[0]}=1. We write F[k]=R1(k)/R0(k)F^{[k]}=R_1^{(k)}/R_0^{(k)}, where

Rk+1(k)=1,Rk(k)=1−yqk,Rh(k)=(1−yqh)Rh+1(k)−xq2h+1Rh+2(k)(0≤h<k),(8)R_{k+1}^{(k)}=1,\qquad R_k^{(k)}=1-yq^k,\qquad R_h^{(k)}=(1-yq^h)R_{h+1}^{(k)}-xq^{2h+1}R_{h+2}^{(k)}\quad(0\le h<k), \tag*{(8)}

with the factor 1−yq01-yq^0 replaced by 11 at h=0h=0. Expanding this recurrence one recovers the standard interpretation of the convergents in terms of matchings, which also goes back to [17]. Namely, Rh(k)R_h^{(k)} is the generating polynomial of monomer-dimer configurations on the path graph with vertices h,…,kh,\ldots,k, where a monomer on the vertex vv has weight −yqv-yq^v and a dimer on the edge {v,v+1}\{v,v+1\} has weight −xq2v+1-xq^{2v+1}.6 Since every occupied vertex vv contributes qvq^v, one can write, for 1≤h≤k1\le h\le k,

Rh(k)=∑S⊆{h,…,k}q∑S∏Im∣I∣(x,y),mr(x,y)=∑d=0⌊r/2⌋(r−dd)(−x)d(−y)r−2d,(9)R_h^{(k)}=\sum_{S\subseteq\{h,\ldots,k\}}q^{\sum S}\prod_I m_{|I|}(x,y),\qquad m_r(x,y)=\sum_{d=0}^{\lfloor r/2\rfloor}\binom{r-d}{d}(-x)^d(-y)^{r-2d}, \tag*{(9)}

where the product runs over the maximal runs II of consecutive integers in SS, and mrm_r stands for the matching polynomial of the path with rr vertices. At the boundary h=0h=0 we use R0(k)=R1(k)−xqR2(k)R_0^{(k)}=R_1^{(k)}-xqR_2^{(k)}. Equivalently, in the subset formula the run containing 00, if present, has weight b1=0b_1=0 and br=−x mr−2(x,y)b_r=-x\,m_{r-2}(x,y) for r≥2r\ge2, since the vertex 00 must be covered by the dimer {0,1}\{0,1\}.

Two special cases can be written in a closed form. The dimer-only part, valid also at h=0h=0, is a q2q^2-binomial sum,

Rh(k)∣y=0=∑m=0⌊(k−h+1)/2⌋(−x)mqm(2m+1)+2m(h−1)(k−h+1−mm)q2,R_h^{(k)}\big|_{y=0}=\sum_{m=0}^{\lfloor(k-h+1)/2\rfloor}(-x)^m q^{m(2m+1)+2m(h-1)}\binom{k-h+1-m}{m}_{q^2},

which at h=1h=1 agrees with the formula obtained by Owczarek and Prellberg for Dyck paths of bounded height [1]. The monomer-only part is (yqh;q)k−h+1(yq^h;q)_{k-h+1} for h≥1h\ge1 and (yq;q)k(yq;q)_k for h=0h=0. It seems that the mixed contributions do not factor in a similar way.

At x=y=1x=y=1 the exponential growth rate of the number of paths of height at most kk is 1/q0(k)1/q_0^{(k)}, where q0(k)q_0^{(k)} denotes the smallest positive zero of R0(k)R_0^{(k)}. One finds

1q0(k)=2,2.2469796…,2.2516428…,2.2516611…(k=1,2,3,4).\frac{1}{q_0^{(k)}}=2,\quad2.2469796\ldots,\quad2.2516428\ldots,\quad2.2516611\ldots\qquad(k=1,2,3,4).

Paths of height one contribute x(x+y)n−1x(x+y)^{n-1} at area n≥1n\geq1, which explains the first value. For height at most two, 1/q0(2)=1+2cos⁡(2π/7)1/q_0^{(2)}=1+2\cos(2\pi/7) is the largest root of t3−2t2−t+1t^3-2t^2-t+1. The rapid convergence to the limit 1/q0=2.2516612…1/q_0=2.2516612\ldots is a curious phenomenon, which will be explained in Theorem 7.3.

The closed form

Let us now take k→∞k\to\infty. For each fixed h≥1h\geq1 one finds from (8) that Rh(k)→A(qh)R_h^{(k)}\to A(q^h), where

A(z)=(1−yz)A(zq)−xqz2A(zq2),A(0)=1.(10)A(z)=(1-yz)A(zq)-xqz^2A(zq^2),\qquad A(0)=1. \tag*{(10)}

We usually suppress the dependence on x,y,qx,y,q and write A(z)A(z) for A(z;x,y;q)A(z;x,y;q). At the boundary one has R0(k)→A(q)−xqA(q2)R_0^{(k)}\to A(q)-xqA(q^2). Comparing coefficients, the solution of (10) is the series AA in (1.2), where the polynomials pnp_n are determined by

p0=1,p1=y,pn=ypn−1−x(1−qn−1)pn−2.(11)p_0=1,\qquad p_1=y,\qquad p_n=yp_{n-1}-x(1-q^{n-1})p_{n-2}. \tag*{(11)}

Then Mh=A(qh+1)/A(qh)M_h=A(q^{h+1})/A(q^h) and F=1/(1−xqM1)=A(q)/(A(q)−xqA(q2))F=1/(1-xqM_1)=A(q)/(A(q)-xqA(q^2)), which proves (1.2). Equivalently, 1/F=y+A(1)/A(q)1/F=y+A(1)/A(q).

Lemma 4.1. For fixed complex x,yx,y, the series A(z;x,y;q)A(z;x,y;q) is entire in zz and holomorphic in qq for ∣q∣<1|q|<1. For each h≥1h\geq1, the continuants Rh(k)R_h^{(k)} converge to A(qh)A(q^h) locally uniformly in this disc. In particular, (1.2) defines a meromorphic function of qq there.

Proof. Fix 0<r<10<r<1. The recurrence (11) gives ∣pn∣≤Kn|p_n|\leq K^n for ∣q∣≤r|q|\leq r, with KK depending only on x,yx,y. Also ∣(q;q)n∣≥∏j≥1(1−rj)>0|(q;q)_n|\geq\prod_{j\geq1}(1-r^j)>0. The factor q(n2)q^{\binom{n}{2}} therefore ensures local uniform convergence of the series for AA in (z,q)(z,q).

For the continuants, ignore the exclusion constraints in the matching expansion. The sum of the absolute weights of all configurations on the infinite path is bounded by

∏v≥h(1+∣y∣rv+∣x∣r2v+1)<∞.\prod_{v\geq h}(1+|y|r^v+|x|r^{2v+1})<\infty.

The weights of configurations involving vertices beyond kk tend to zero uniformly on ∣q∣≤r|q|\leq r. Hence the finite continuants converge locally uniformly. Their formal limit, already identified above, is A(qh)A(q^h). The denominator in (1.2) is holomorphic and equals 1 at q=0q=0, which proves the last assertion. □

Remark 4.2. Let us write x=αβx=\alpha\beta and y=α+βy=\alpha+\beta. Then the solution of (11) takes the form

pn=∑k=0n(nk)qαn−kβk.p_n=\sum_{k=0}^{n}\binom{n}{k}_q\alpha^{n-k}\beta^k.

which is a homogeneous form of the continuous qq-Hermite polynomial of Rogers. Namely, one has pn=xn/2Hn(y/(2x)∣q)p_n=x^{n/2}H_n(y/(2\sqrt{x})\mid q) for x≠0x\neq0, with its polynomial extension at x=0x=0. Moreover, one can write

A(z)=(αz;q)∞ 1ϕ1(0αz;q,βz).A(z)=(\alpha z;q)_\infty\,{}_1\phi_1\left(\begin{matrix}0\\ \alpha z\end{matrix};q,\beta z\right).

which is a qq-Bessel type function, see e.g. [22]. At apparent singularities of the product representation, the identity is understood by analytic continuation.

Remark 4.3 (An algebraic quiver-series representation). Let us introduce the so-called symmetric-quiver series

PC(x1,x2)=∑d1,d2≥0(−q1/2)dTCdx1d1x2d2(q;q)d1(q;q)d2,C=(1111).P_C(x_1,x_2)=\sum_{d_1,d_2\geq0}\frac{(-q^{1/2})^{d^TCd}x_1^{d_1}x_2^{d_2}}{(q;q)_{d_1}(q;q)_{d_2}},\qquad C=\begin{pmatrix}1&1\\1&1\end{pmatrix}.

Since dTCd=(d1+d2)2d^TCd=(d_1+d_2)^2 and (−q1/2)n2=(−1)nqn2/2(-q^{1/2})^{n^2}=(-1)^nq^{n^2/2}, grouping the terms with d1+d2=nd_1+d_2=n one obtains the formal identities

A(z)=PC(αzq−1/2,βzq−1/2),1F−y=PC(αq−1/2,βq−1/2)PC(αq1/2,βq1/2).(12)A(z)=P_C(\alpha zq^{-1/2},\beta zq^{-1/2}),\qquad\frac{1}{F}-y=\frac{P_C(\alpha q^{-1/2},\beta q^{-1/2})}{P_C(\alpha q^{1/2},\beta q^{1/2})}. \tag*{(12)}

Ratios of quiver series at qq-shifted arguments occur in the enumeration of area-weighted Schröder paths [10, 11], where the corresponding qq-difference equations are related to the so-called quantum AA-polynomials; combinatorial derivations of such equations appear in [14], and the coefficient formulas of [12] may be compared with Theorem 5.1 below. In the conventions of [11], the Schröder-path quiver of slope 1/f1/f has the matrix (ffff+1)\begin{pmatrix} f & f \\ f & f+1 \end{pmatrix}, so that our matrix differs from its f=1f=1 case by one diagonal entry. For y=0y=0 the specialization (13) below can similarly be written as F(x,0;q)=P(2)(−xQ1/2;Q)/P(2)(−xQ−1/2;Q)F(x,0;q)=P_{(2)}(-xQ^{1/2};Q)/P_{(2)}(-xQ^{-1/2};Q) with Q=q2Q=q^2, and the one-node quiver (2) appears in the formulas for the reduced unknot in framing two [11]. We stress that these are comparisons of formal series and adjacency matrices, not of knot invariants.

For y=0y=0, i.e. β=−α\beta=-\alpha, the closed form becomes the Rogers–Ramanujan type identity

F(x,0;q)=∑k≥0(−x)kqk(2k+1)/(q2;q2)k∑k≥0(−x)kqk(2k−1)/(q2;q2)k,(13)F(x,0;q)=\frac{\sum_{k\geq0}(-x)^kq^{k(2k+1)}/(q^2;q^2)_k}{\sum_{k\geq0}(-x)^kq^{k(2k-1)}/(q^2;q^2)_k}, \tag*{(13)}

in agreement with [1, 18]. Finally, taking k→∞k\to\infty in (9) one obtains a second interpretation of the auxiliary series: for h≥1h\geq1, A(qh)A(q^h) enumerates partitions into distinct parts at least hh, with each maximal run of rr consecutive parts weighted by mr(x,y)m_r(x,y). We will need this interpretation in § 6.

Explicit formulas for the coefficients

In this section we give explicit formulas for the coefficients of SnS_n. Let us start with a simple observation. Deleting the horizontal steps of a Riordan path leaves its Dyck skeleton. Conversely, one can insert an arbitrary run of horizontal steps at each skeleton vertex vv of positive height h(v)h(v). Each inserted step has weight yqh(v)yq^{h(v)}, and therefore

F=∑D Dyckx#U(D)qarea⁡(D)∏v11−yqh(v),(14)F=\sum_{D\ \mathrm{Dyck}}x^{\#U(D)}q^{\operatorname{area}(D)}\prod_v\frac{1}{1-yq^{h(v)}}, \tag*{(14)}

where the product runs over the vertices of DD of positive height. For fixed mm, the coefficient Fm=[xm]FF_m=[x^m]F is a rational function of qq whose denominator divides ∏h=1m(1−yqh)m+1−h\prod_{h=1}^{m}(1-yq^h)^{m+1-h}. For example, F1=q/(1−yq)F_1=q/(1-yq) and F2=q2(1−yq)2+q4(1−yq)2(1−yq2)F_2=\frac{q^2}{(1-yq)^2}+\frac{q^4}{(1-yq)^2(1-yq^2)}. In particular, the paths of height one contribute exactly x(x+y)n−1x(x+y)^{n-1} to SnS_n, which is the leading row visible in Appendix § 9.

In order to obtain a positive formula for all coefficients, we will need also the following profiles. The Dyck skeleton count used below is the lowest-floor case of [4, Eq. (18)]; that work also treats horizontal-step profiles. We include a direct proof to make the fixed-area constraint explicit. For a path PP, let tht_h be the number of its interior vertices at height hh, and let uhu_h be the number of its up steps from height hh to h+1h+1. Summing the contributions of the endpoints of each step one finds

area⁡(P)=∑h≥1h th,(15)\operatorname{area}(P)=\sum_{h\geq1}h\,t_h, \tag*{(15)}

i.e. the area is the sum of the heights of the interior vertices. If PP has height HH, its up-profile (u0,…,uH−1)(u_0,\ldots,u_{H-1}) is a composition of #U(P)\#U(P), and its skeleton has vh=uh−1+uhv_h=u_{h-1}+u_h vertices at each height 1≤h≤H1\leq h\leq H, where uH=0u_H=0.

Theorem 5.1. Let u=(u0,…,uH−1)u=(u_0,\ldots,u_{H-1}) be a composition and let t=(t1,…,tH)t=(t_1,\ldots,t_H) be a sequence of positive integers, and set uH=0u_H=0. Here a binomial coefficient is zero when its lower argument exceeds its nonnegative upper argument. The number of Riordan paths with up-profile uu and vertex profile tt is

∏h=1H(uh−1+uh−1uh)(th−1uh−1+uh−1).\prod_{h=1}^{H}\binom{u_{h-1}+u_h-1}{u_h}\binom{t_h-1}{u_{h-1}+u_h-1}.

Consequently,

F=1+∑ux∣u∣∏h=1H(uh−1+uh−1uh)(qh1−yqh)uh−1+uhF = 1 + \sum_{u} x^{|u|} \prod_{h=1}^{H} \binom{u_{h-1}+u_h-1}{u_h} \left(\frac{q^h}{1-yq^h}\right)^{u_{h-1}+u_h}

where the sum runs over all nonempty compositions uu and HH denotes the number of parts. For m≥1m \ge1, the number of paths of area nn with mm up steps and jj horizontal steps is

c(n,m,j)=∑u⊨m, t∑hth=2m−u0+j, ∑hhth=n∏h=1H(uh−1+uh−1uh)(th−1uh−1+uh−1).c(n,m,j) = \sum_{\substack{u \models m,\ t\\ \sum_{h} t_h=2m-u_0+j,\ \sum_h h t_h=n}} \prod_{h=1}^{H} \binom{u_{h-1}+u_h-1}{u_h} \binom{t_h-1}{u_{h-1}+u_h-1}.

Proof. Let us first count the Dyck skeletons with profile uu. At level hh, the uhu_h excursions above height hh are distributed among the uh−1u_{h-1} excursions rising from height h−1h-1. This is a weak composition into uh−1u_{h-1} parts, counted by (uh−1+uh−1uh)\binom{u_{h-1}+u_h-1}{u_h}, and applying this construction at successive levels one obtains the first factor.

Next, at height hh, one distributes th−vht_h-v_h horizontal steps among the vhv_h skeleton vertices; there are (th−1vh−1)\binom{t_h-1}{v_h-1} choices, which gives the second factor. The area is then determined by (15). Since the skeleton has u0u_0 primitive components, exactly u0−1u_0-1 of its interior vertices lie on the axis, and therefore it has 2m−u02m-u_0 vertices of positive height. Inserting jj horizontal steps gives ∑h=1Hth=2m−u0+j\sum_{h=1}^{H}t_h=2m-u_0+j, which proves the formula for c(n,m,j)c(n,m,j). Summing over the insertions at each height one obtains the generating function, where the term 1 represents the empty path. □

Asymptotics and a linear recurrence

In this section we determine the growth of the numbers rnr_n and obtain a recurrence for them. The point of departure is the decomposition of a path into its primitive components, i.e. the pieces between consecutive returns to the axis. Every nonempty Riordan path decomposes uniquely into primitive paths, which touch the axis only at their endpoints. At x=y=1x=y=1 their generating function is

g(q)=∑P primitiveqarea⁡(P)=q+q2+q3+2q4+3q5+5q6+⋯ .g(q)=\sum_{P\ \mathrm{primitive}}q^{\operatorname{area}(P)}=q+q^2+q^3+2q^4+3q^5+5q^6+\cdots.

Therefore F(1,1;q)=1/(1−g)F(1,1;q)=1/(1-g) and, by (2), g=qA(q2)/A(q)g=qA(q^2)/A(q). Each primitive component contributes one return to the axis, including the final one, so marking the returns by uu one obtains F(u;q)=1/(1−ug)=F/(u+(1−u)F)F(u;q)=1/(1-ug)=F/(u+(1-u)F).

Theorem 6.1. Let ρ\rho be the radius of convergence of gg. The equation g(q)=1g(q)=1 has a unique root q0∈(0,ρ)q_0\in(0,\rho), which is also the smallest positive root of A(q)=qA(q2)A(q)=qA(q^2) at x=y=1x=y=1. For some θ<1\theta<1,

rn=Cq0−n(1+O(θn)),C=1q0g′(q0).r_n=Cq_0^{-n}(1+O(\theta^n)),\qquad C=\frac{1}{q_0g'(q_0)}.

with

q0=0.44411654605086…,q0−1=2.25166121121160…,C=0.34315827064…q_0=0.44411654605086\ldots,\qquad q_0^{-1}=2.25166121121160\ldots,\qquad C=0.34315827064\ldots

Proof. The series gg has nonnegative coefficients and a positive radius of convergence, since a path of area nn has length at most 2n2n. By Lemma 4.1, gg is meromorphic in ∣q∣<1|q|<1. The primitive paths UHjDUH^jD give g(t)≥t/(1−t)g(t)\ge t/(1-t) wherever both sides converge, so ρ≤1\rho\le1. If ρ<1\rho<1, Pringsheim’s theorem together with meromorphicity implies that ρ\rho is a pole and g(t)→∞g(t)\to\infty as t↑ρt\uparrow\rho. If ρ=1\rho=1, the same divergence follows from the lower bound. Since gg is strictly increasing on [0,ρ)[0,\rho), it reaches 1 at a unique point q0<ρq_0<\rho.

For ∣q∣≤q0|q|\le q_0 one has ∣g(q)∣≤g(∣q∣)≤1|g(q)|\le g(|q|)\le1. On ∣q∣=q0|q|=q_0, equality in the triangle inequality requires the terms of degrees 1 and 2 to have the same argument, and their positive coefficients force q=q0q=q_0. Thus 1−g1-g has a unique zero in the closed disc, and this zero is simple because g′(q0)>0g'(q_0)>0. Analyticity in

a larger disc and isolation of zeros give an exponentially smaller remainder after subtraction of the simple pole, and the residue gives C=1/(q0g′(q0))C = 1/(q_0g'(q_0)).

It remains to rule out a cancellation in the quotient for gg. Let us display the base parameter of AA explicitly. If, for some 0<t<10 < t < 1, both A(t;1,1;t)A(t;1,1;t) and A(t2;1,1;t)A(t^2;1,1;t) vanished, the recurrence for Bh=A(th;1,1;t)B_h = A(t^h;1,1;t),

Bh=(1−th)Bh+1−t2h+1Bh+2,B_h = (1-t^h)B_{h+1}-t^{2h+1}B_{h+2},

would force Bh=0B_h=0 for every h≥1h\ge1, which contradicts Bh→A(0;1,1;t)=1B_h \to A(0;1,1;t)=1. Consequently a zero of A(t;1,1;t)A(t;1,1;t) cannot cancel in g(t)g(t), so A(t;1,1;t)>0A(t;1,1;t)>0 for 0≤t<ρ0\le t<\rho. On this interval the denominator is A(q)(1−g(q))A(q)(1-g(q)), and its first positive zero is q0q_0. □

Let us make a few comments. The leading asymptotics is already accurate at modest area; namely, r22/(Cq0−22)=1+4.8722⋅10−7r_{22}/(Cq_0^{-22})=1+4.8722\cdot10^{-7}. A further positive pole is found numerically at q1=0.77091704183…q_1=0.77091704183\ldots, and the argument principle applied numerically on the circles ∣q∣=0.6|q|=0.6, 0.70.7, 0.80.8 gives 1, 1, 2 zeros of A(q)−qA(q2)A(q)-qA(q^2). These computations suggest that any θ∈(q0/q1,1)\theta\in(q_0/q_1,1) is admissible in Theorem 6.1; we do not use this sharper, uncertified estimate. We do not know closed forms for q0q_0 and CC; the Dyck constants qD=0.6629014851…q_D=0.6629014851\ldots and CD=0.3377611503…C_D=0.3377611503\ldots recorded in OEIS A143951 [19] are likewise only known numerically. For positive weights x,yx,y the same argument applies whenever the primitive generating function reaches 1 strictly inside its radius of convergence, which holds near (x,y)=(1,1)(x,y)=(1,1).

A recurrence for rnr_n

Let us now come back to the partition interpretation of § 4. We write A(q)∣x=y=1=∑nνnqnA(q)|_{x=y=1}=\sum_n \nu_nq^n and A(q2)∣x=y=1=∑nνn′qnA(q^2)|_{x=y=1}=\sum_n \nu'_nq^n. Then νn\nu_n counts partitions of nn into distinct parts, with each maximal run of rr consecutive parts weighted by mr(1,1)=∑d(−1)r−d(r−dd)m_r(1,1)=\sum_d(-1)^{r-d}\binom{r-d}{d}, and νn′\nu'_n counts the same partitions with the additional restriction that every part is at least 2. The run weights turn out to be periodic, namely mr(1,1)=1,−1,0m_r(1,1)=1,-1,0 for r≡0,1,2(mod3)r\equiv0,1,2\pmod3, respectively. The following simple cancellation explains this periodicity.

Lemma 6.2. Let us write a perfect monomer-dimer cover of the path with rr vertices as a word in the letters MM and DD, with sign (−1)#letters(-1)^{\#\text{letters}}. The map exchanging a leading DD with a leading MMMM, and fixing the words with neither prefix, is an involution which reverses the sign on its nonfixed pairs. Its fixed points are the words MDwMDw, together with MM and the empty word. Hence mr(1,1)=mr−3(1,1)m_r(1,1)=m_{r-3}(1,1) for r≥3r\ge3, with the initial values 1,−1,01,-1,0.

Theorem 6.3. Let r0=1r_0=1, set ν−1′=0\nu'_{-1}=0, and let dn=νn−νn−1′d_n=\nu_n-\nu'_{n-1} for n≥0n\ge0. Then

rn=νn−∑k=1ndkrn−k,n≥1,r_n=\nu_n-\sum_{k=1}^{n}d_kr_{n-k},\qquad n\ge1,

where νn=∑λ(−1)#{runs of length≡1(mod3)}\nu_n=\sum_{\lambda}(-1)^{\#\{\text{runs of length}\equiv1\pmod3\}}, the sum being over partitions λ\lambda of nn into distinct parts with no run of length ≡2(mod3)\equiv2\pmod3, and νn′\nu'_n is the same sum over partitions with parts ≥2\ge2. The first values are

(νn)n≥0=1,−1,−1,−1,0,0,2,1,2,2,1,0,1,−2,−2,−3,−3,−5,−3,−5,−3,…(\nu_n)_{n\ge0}=1,-1,-1,-1,0,0,2,1,2,2,1,0,1,-2,-2,-3,-3,-5,-3,-5,-3,\ldots
(νn′)n≥0=1,0,−1,−1,−1,−1,0,0,1,2,2,3,2,1,1,0,−2,−2,−4,−5,…(\nu'_n)_{n\ge0}=1,0,-1,-1,-1,-1,0,0,1,2,2,3,2,1,1,0,-2,-2,-4,-5,\ldots
(dn)n≥0=1,−2,−1,0,1,1,3,1,2,1,−1,−2,−1,−5,−4,−4,−4,−5,−1,−3,1,…(d_n)_{n\ge0}=1,-2,-1,0,1,1,3,1,2,1,-1,-2,-1,-5,-4,-4,-4,-5,-1,-3,1,\ldots

Proof. This is the identity F(1,1;q)(A(q)−qA(q2))=A(q)F(1,1;q)(A(q)-qA(q^2))=A(q) written out coefficientwise. □

It is worth mentioning that the coefficients of the recurrence are small compared with rnr_n, since their absolute values are bounded by partition counts; for example, ∣νn∣≤1167|\nu_n|\le1167 for n≤120n\le120, whereas r120≈1042r_{120}\approx10^{42}.

Limit laws

In this section we describe a typical Riordan path of large area. In a few words, such a path looks like a long sequence of small primitive components, and the statistics we are interested in are sums over the components. The point of departure is again the decomposition into primitive paths. Since g(q0)=1g(q_0)=1, one can assign the probability q0area⁡(P)q_0^{\operatorname{area}(P)} to each primitive path PP; this defines a probability distribution on primitive paths, which we call the Boltzmann distribution. Let NN be the area of a Boltzmann primitive path and let RR be an additive statistic, namely its number of returns, of horizontal steps or of up steps. Note that EN=q0g′(q0)=1/C\mathbb{E}N=q_0g'(q_0)=1/C. In other words, the constant CC of Theorem 6.1 is the inverse of the mean area of a primitive component.

Additive statistics

Let us first consider the statistics which are additive over the components. The following theorem says that they behave like sums of independent random variables, and that the constants are the ones of the classical renewal-reward theorem.

Theorem 7.1. Let a Riordan path of area nn be chosen uniformly at random, and let XnX_n, YnY_n, ZnZ_n be its numbers of returns to the axis, of horizontal steps and of up steps. Each of these is asymptotically Gaussian. Namely, for any one of them, denoted by WnW_n,

EWn=μn+O(1),Var⁡(Wn)=σ2n+O(1),Wn−μnσn→dN(0,1),\mathbb{E}W_n=\mu n+O(1),\qquad\operatorname{Var}(W_n)=\sigma^2n+O(1),\qquad\frac{W_n-\mu n}{\sigma\sqrt{n}}\xrightarrow{d}\mathcal{N}(0,1),

where

μ=EREN,σ2=Var⁡(R−μN)EN>0.(16)\mu=\frac{\mathbb{E}R}{\mathbb{E}N},\qquad\sigma^2=\frac{\operatorname{Var}(R-\mu N)}{\mathbb{E}N}>0. \tag*{(16)}

Numerically,

Xn:μX=C≈0.343158270645,σX2≈0.344199446374,Yn:μY≈0.365093862590,σY2≈0.292149839727,Zn:μZ≈0.431620789070,σZ2≈0.225725860430.\begin{aligned} X_n &: \quad\mu_X=C\approx0.343158270645,\quad\sigma_X^2\approx0.344199446374,\\ Y_n &: \quad\mu_Y\approx0.365093862590,\quad\sigma_Y^2\approx0.292149839727,\\ Z_n &: \quad\mu_Z\approx0.431620789070,\quad\sigma_Z^2\approx0.225725860430. \end{aligned}

For the returns one has σX2=Var⁡(N)/(EN)3\sigma_X^2=\operatorname{Var}(N)/(\mathbb{E}N)^3.

Proof. Let g(v;q)g(v;q) be the generating function of primitive paths with the statistic marked by vv. Then the bivariate generating function is 1/(1−g(v;q))1/(1-g(v;q)), i.e. we are dealing with the so-called supercritical sequence schema of Flajolet and Sedgewick [18 Chapter IX]. Let us choose r>q0r>q_0 and ε>0\varepsilon>0 with (1+ε)r<ρ(1+\varepsilon)r<\rho. Each statistic satisfies 0≤R≤N0\le R\le N, so the marked series is dominated by g((1+ε)r)g((1+\varepsilon)r) for ∣q∣≤r|q|\le r, ∣v∣≤1+ε|v|\le1+\varepsilon, and is therefore jointly analytic in a neighbourhood of (1,q0)(1,q_0). As a result, the simple dominant pole persists for vv near 11, with uniform asymptotics of the coefficients, and the quasi-powers theorem of Hwang [18 Chapter IX] gives a Gaussian law with μ=−q′(1)/q(1)\mu=-q'(1)/q(1) and σ2=−q′′(1)/q(1)−q′(1)/q(1)+(q′(1)/q(1))2\sigma^2=-q''(1)/q(1)-q'(1)/q(1)+(q'(1)/q(1))^2, where q(v)q(v) is the root of g(v;q(v))=1g(v;q(v))=1 near q(1)=q0q(1)=q_0, provided that σ2≠0\sigma^2\ne0. Differentiating g(v;q(v))=1g(v;q(v))=1 twice at v=1v=1 and writing the derivatives of gg as Boltzmann moments one obtains (16). It remains to check that the variance is positive. Actually, this is clear, since R−μNR-\mu N is not almost surely constant. Indeed, the primitive paths UDUD, UHDUHD and UUDDUUDD have (N,R)=(1,1),(2,1),(4,1)(N,R)=(1,1),(2,1),(4,1) for returns, (1,0),(2,1),(4,0)(1,0),(2,1),(4,0) for horizontal steps and (1,1),(2,1),(4,2)(1,1),(2,1),(4,2) for up steps, and in each case R−μNR-\mu N takes at least two values. □\square

It is worth mentioning that the mean number of returns per unit area coincides with the prefactor CC of Theorem 6.1, and that the mean length of a path of area nn is (2μZ+μY)n+O(1)≈1.228n(2\mu_Z+\mu_Y)n+O(1)\approx1.228n.7

Corollary 7.2. Let Wn=(Xn,Yn,Zn)T\mathbf{W}_n=(X_n,Y_n,Z_n)^T and μ=(μX,μY,μZ)T\boldsymbol{\mu}=(\mu_X,\mu_Y,\mu_Z)^T. For a Boltzmann primitive path, write R=(1,#H,#U)T\mathbf{R}=(1,\#H,\#U)^T. Then

Wn−nμn→dN3(0,Σ),Cov⁡(Wn)=nΣ+O(1),\frac{\mathbf{W}_n-n\boldsymbol{\mu}}{\sqrt{n}}\xrightarrow{d}\mathcal{N}_3(0,\boldsymbol{\Sigma}),\qquad\operatorname{Cov}(\mathbf{W}_n)=n\boldsymbol{\Sigma}+O(1),

where the matrix

Σ=E[(R−μN)(R−μN)T]EN(17)\boldsymbol{\Sigma}=\frac{\mathbb{E}\left[(\mathbf{R}-\boldsymbol{\mu}N)(\mathbf{R}-\boldsymbol{\mu}N)^{T}\right]}{\mathbb{E}N} \tag*{(17)}

is positive definite.

Proof. Mark the three statistics by v=(v1,v2,v3)\mathbf{v}=(v_1,v_2,v_3) in the primitive series g(v;q)g(\mathbf{v};q). Each component of R\mathbf{R} is at most NN, so joint analyticity follows by choosing r>q0r>q_0 and ε>0\varepsilon>0 with (1+ε)3r<ρ(1+\varepsilon)^3r<\rho. The simple pole persists at an analytic root q(v)q(\mathbf{v}) near q0q_0, with uniform coefficient asymptotics. Consequently, for s\mathbf{s} near zero,

EesTWn=c(es)C(q0q(es))n(1+O(θn)),\mathbb{E}e^{\mathbf{s}^{T}\mathbf{W}_n}=\frac{c(e^{\mathbf{s}})}{C}\left(\frac{q_0}{q(e^{\mathbf{s}})}\right)^n(1+O(\theta^n)),

where cc is analytic, c(1)=Cc(\mathbf{1})=C, and θ<1\theta<1. Differentiating g(es;q(es))=1g(e^{\mathbf{s}};q(e^{\mathbf{s}}))=1 gives the gradient μ\boldsymbol{\mu} and the Hessian (7.2) of log⁡(q0/q(es))\log(q_0/q(e^{\mathbf{s}})) at zero. The Taylor expansion at s=it/n\mathbf{s}=i\mathbf{t}/\sqrt{n} gives the joint Gaussian limit; differentiation gives the covariance estimate.

To check nondegeneracy, suppose a+b#H+c#U=dNa+b\mathbin{\#}H+c\mathbin{\#}U=dN for every primitive path. Applying this relation to UDUD, UHDUHD, UUDDUUDD and UUHDDUUHDD gives

a+c=d,a+b+c=2d,a+2c=4d,a+b+2c=6d.a+c=d,\qquad a+b+c=2d,\qquad a+2c=4d,\qquad a+b+2c=6d.

These equations imply a=b=c=d=0a=b=c=d=0. Thus no nonzero linear combination of R−μN\mathbf{R}-\boldsymbol{\mu}N has zero variance, and Σ\boldsymbol{\Sigma} is positive definite. □

The height

Let us now turn to the height HnH_n, which is not additive and behaves quite differently. The idea is the following. The height of a path is the maximum of the heights of its components, and a primitive component of height larger than kk is very rare under the Boltzmann distribution, since the smallest such path is the pyramid Uk+1Dk+1U^{k+1}D^{k+1} of area (k+1)2(k+1)^2. Therefore the height of a path of area nn is determined by the balance between the number of components, which is of order nn, and this small probability. To make this precise, for k≥1k\geq1 let g[k]g^{[k]} be the generating function of primitive paths of height at most kk, and let q0(k)q_0^{(k)} be the positive root of g[k]=1g^{[k]}=1 within its disc of convergence. We set λk=log⁡(q0(k)/q0)\lambda_k=\log(q_0^{(k)}/q_0) and τk=1−g[k](q0)\tau_k=1-g^{[k]}(q_0), so that τk\tau_k is the Boltzmann probability that a primitive path has height greater than kk. The following theorem gives an exact formula for τk\tau_k and the resulting law of the height.

Theorem 7.3. Let Mh=A(qh+1)/A(qh)M_h=A(q^{h+1})/A(q^h) and let Mh(k)M_h^{(k)} be its truncation at height kk. At x=y=1x=y=1 one has, for k≥1k\geq1,

τk=q0(k+1)2Mk+1(q0)∏h=1kMh(q0)Mh(k)(q0)∼q0(k+1)2A(q0)2,(18)\tau_k=q_0^{(k+1)^2}M_{k+1}(q_0)\prod_{h=1}^{k}M_h(q_0)M_h^{(k)}(q_0)\sim\frac{q_0^{(k+1)^2}}{A(q_0)^2}, \tag*{(18)}

and

λk=Cτk(1+O(k2τk)).\lambda_k=C\tau_k(1+O(k^2\tau_k)).

There exist k0k_0, θ<1\theta<1 and constants ck→Cc_k\to C such that, uniformly in k≥k0k\geq k_0,

P(Hn≤k)=ckCe−λkn+O(θn).\mathbb{P}(H_n\leq k)=\frac{c_k}{C}e^{-\lambda_kn}+O(\theta^n).

Consequently, with Λ=C/A(q0)2=3.9586573854…\Lambda=C/A(q_0)^2=3.9586573854\ldots,

sup⁡k∈Z≥0∣P(Hn≤k)−exp⁡(−Λnq0(k+1)2)∣⟶0(n→∞),\sup_{k\in\mathbb{Z}_{\geq0}}\left|\mathbb{P}(H_n\leq k)-\exp\left(-\Lambda nq_0^{(k+1)^2}\right)\right|\longrightarrow0\qquad(n\to\infty),

and

Hn=log⁡nlog⁡(1/q0)+OP(1).H_n=\sqrt{\frac{\log n}{\log(1/q_0)}}+O_{\mathbb{P}}(1).

The proof, which is based on an exact telescoping formula for τk\tau_k, is somewhat technical and is given in Appendix § 10.

Corollary 7.4. Put

bn=log⁡(Λn)log⁡(1/q0),mn=⌊bn+12⌋.b_n = \sqrt{\frac{\log(\Lambda n)}{\log(1/q_0)}}, \qquad m_n = \left\lfloor b_n + \frac{1}{2} \right\rfloor.

Then P(Hn∈{mn−1,mn})→1\mathbb{P}(H_n \in\{m_n - 1,m_n\}) \to1 as n→∞n \to\infty.

Proof. Write a=log⁡(1/q0)>0a = \log(1/q_0) > 0. Since ∣mn−bn∣≤12|m_n-b_n| \le\frac{1}{2},

bn2−(mn−1)2≥bn−14,(mn+1)2−bn2≥bn+14b_n^2-(m_n-1)^2 \ge b_n-\frac{1}{4}, \qquad(m_n+1)^2-b_n^2 \ge b_n+\frac{1}{4}

for all sufficiently large nn. In the approximation of Theorem 7.3, the exponent Λnq0(k+1)2=exp⁡{a[bn2−(k+1)2]}\Lambda n q_0^{(k+1)^2} = \exp\{a[b_n^2-(k+1)^2]\} therefore tends to infinity at k=mn−2k=m_n-2 and to zero at k=mnk=m_n. Hence P(Hn≤mn−2)→0\mathbb{P}(H_n \le m_n-2) \to0 and P(Hn≤mn)→1\mathbb{P}(H_n \le m_n) \to1. □

Remark 7.5. Let us stress that the double-exponential form in Theorem 7.3 describes the distribution at integer thresholds only and should not be interpreted as a continuous Gumbel limit. Indeed, (Hn+1)2−Ln(H_n+1)^2-L_n with Ln=log⁡(Λn)/log⁡(1/q0)L_n=\log(\Lambda n)/\log(1/q_0) is not tight: choosing integers nmn_m with Lnm=m2+m+12+o(1)L_{n_m}=m^2+m+\frac{1}{2}+o(1), every integer square is at distance at least m+12−o(1)m+\frac{1}{2}-o(1) from LnmL_{n_m}.

Numerically, one finds λk=0.1185211\lambda_k=0.1185211, 2.08134⋅10−32.08134\cdot10^{-3}, 8.14655⋅10−68.14655\cdot10^{-6} and 5.82080⋅10−95.82080\cdot10^{-9} for k=1,…,4k=1,\ldots,4, and exact bounded-height counts give the probabilities in Table 1. At area 1500, the probability of height exactly three is about 0.9431. The slow growth and two-height concentration differ sharply from the square-root height scale of uniformly chosen Motzkin paths of fixed length.

Concluding remarks

In this work, we have studied Riordan paths enumerated by area. We have shown that the enumeration is governed by a single auxiliary qq-series. Its continued fraction representation gives the generating functions of paths of bounded height, while its expansion over partitions into distinct parts yields a linear recurrence for the area counts. The decomposition into primitive paths determines the dominant pole and the joint Gaussian law for additive statistics. It also gives the tail of the height distribution, whose leading term is fixed by the area (k+1)2(k+1)^2 of the smallest path reaching height k+1k+1. The uniform estimate implies concentration on two adjacent heights.

The auxiliary series admits an algebraic representation as the motivic generating series of the symmetric quiver (1111)\left(\begin{smallmatrix}1&1\\1&1\end{smallmatrix}\right), after the substitution x=αβx=\alpha\beta, y=α+βy=\alpha+\beta, and the Dyck specialization admits a one-node representation. These identities allow a comparison with the quiver generating series appearing in knot theory, but we do not identify a knot invariant for Riordan paths; it seems that this would require additional structure beyond the identities obtained here.

The path decomposition and the continued fraction extend to horizontal steps Hℓ=(ℓ,0)H_\ell=(\ell,0) with integer ℓ≥1\ell\ge1, forbidden on the axis; the case ℓ=2\ell=2 gives Schröder-type paths. Such a step at height hh has area ℓh\ell h. Writing Fℓ†=Fℓ(xq2,yqℓ;q)F_\ell^\dagger=F_\ell(xq^2,yq^\ell;q), the functional equation takes the form

Fℓ−1=xqFℓ†Fℓ+yqℓFℓ†(Fℓ−1),F_\ell-1=xqF_\ell^\dagger F_\ell+yq^\ell F_\ell^\dagger(F_\ell-1),

and the continued fraction has 1−yqℓh1-yq^{\ell h} in place of 1−yqh1-yq^h. The corresponding auxiliary function satisfies

Aℓ(z)=(1−yzℓ)Aℓ(qz)−xqz2Aℓ(q2z),Aℓ(0)=1.A_{\ell}(z)=(1-yz^{\ell})A_{\ell}(qz)-xqz^2A_{\ell}(q^2z),\qquad A_{\ell}(0)=1.

For general ℓ\ell the qq-Hermite and quiver representations require a separate analysis. At x=y=1x=y=1 the growth constants for ℓ=1,2,3,4\ell=1,2,3,4 are 2.2516612, 1.8656543, 1.7182811 and 1.6413284; they decrease to the Dyck value 1.5085198 . . ., since increasing ℓ\ell decreases the primitive weights and the simple-root argument gives the convergence of the poles.

Several questions remain. The signed partition recurrence in Theorem 6.3 suggests a direct sign-reversing involution on suitable pairs of paths and partitions. For the additive statistics, local limit laws and quantitative error estimates would refine Corollary 7.2. Step sets with several jump sizes may require more general continued fractions. It also remains to understand whether the two-node quiver representation has a meaning beyond the algebraic identity established here.

Acknowledgements

Acknowledgements. Large language models were used in the literature search, computer-assisted checks and preparation of the manuscript. The original derivation of § 7 and Appendix § 10 was obtained entirely with the assistance of Claude (Anthropic). ChatGPT (OpenAI) assisted with subsequent mathematical and editorial refinements, including the joint Gaussian and two-height corollaries, and with independent numerical checks. The work of Ilmar Gahramanov is partially supported by the Istanbul Integrability and Stringy Topics Initiative (istringy.org).

The polynomials S6,…,S10S_6,\ldots,S_{10}

Here we list the polynomials S6,…,S10S_6,\ldots,S_{10}; terms are grouped by decreasing total degree.

S6=x6+5x5y+10x4y2+10x3y3+5x2y4+xy5+3x4+6x3y+3x2y2+x2y\begin{aligned} S_6={}&x^6+5x^5y+10x^4y^2+10x^3y^3+5x^2y^4+xy^5+3x^4+6x^3y+3x^2y^2+x^2y \end{aligned}
S7=x7+6x6y+15x5y2+20x4y3+15x3y4+6x2y5+xy6+4x5+12x4y+12x3y2+4x2y3+2x3y+2x2y2+x3\begin{aligned} S_7={}&x^7+6x^6y+15x^5y^2+20x^4y^3+15x^3y^4+6x^2y^5+xy^6\\ &+4x^5+12x^4y+12x^3y^2+4x^2y^3+2x^3y+2x^2y^2+x^3 \end{aligned}
S8=x8+7x7y+21x6y2+35x5y3+35x4y4+21x3y5+7x2y6+xy7+5x6+20x5y+30x4y2+20x3y3+5x2y4+3x4y+6x3y2+3x2y3+3x4+3x3y+x2y2\begin{aligned} S_8={}&x^8+7x^7y+21x^6y^2+35x^5y^3+35x^4y^4+21x^3y^5+7x^2y^6+xy^7\\ &+5x^6+20x^5y+30x^4y^2+20x^3y^3+5x^2y^4+3x^4y+6x^3y^2+3x^2y^3+3x^4+3x^3y+x^2y^2 \end{aligned}
S9=x9+8x8y+28x7y2+56x6y3+70x5y4+56x4y5+28x3y6+8x2y7+xy8+6x7+30x6y+60x5y2+60x4y3+30x3y4+6x2y5+4x5y+12x4y2+12x3y3+4x2y4+6x5+12x4y+8x3y2+2x2y3+2x3y+x3\begin{aligned} S_9={}&x^9+8x^8y+28x^7y^2+56x^6y^3+70x^5y^4+56x^4y^5+28x^3y^6+8x^2y^7+xy^8\\ &+6x^7+30x^6y+60x^5y^2+60x^4y^3+30x^3y^4+6x^2y^5\\ &+4x^5y+12x^4y^2+12x^3y^3+4x^2y^4+6x^5+12x^4y+8x^3y^2+2x^2y^3+2x^3y+x^3 \end{aligned}
S10=x10+9x9y+36x8y2+84x7y3+126x6y4+126x5y5+84x4y6+36x3y7+9x2y8+xy9+7x8+42x7y+105x6y2+140x5y3+105x4y4+42x3y5+7x2y6+5x6y+20x5y2+30x4y3+20x3y4+5x2y5+10x6+30x5y+33x4y2+16x3y3+3x2y4+6x4y+6x3y2+x2y3+3x4+2x3y\begin{aligned} S_{10}={}&x^{10}+9x^9y+36x^8y^2+84x^7y^3+126x^6y^4+126x^5y^5+84x^4y^6+36x^3y^7+9x^2y^8+xy^9\\ &+7x^8+42x^7y+105x^6y^2+140x^5y^3+105x^4y^4+42x^3y^5+7x^2y^6\\ &+5x^6y+20x^5y^2+30x^4y^3+20x^3y^4+5x^2y^5\\ &+10x^6+30x^5y+33x^4y^2+16x^3y^3+3x^2y^4+6x^4y+6x^3y^2+x^2y^3+3x^4+2x^3y \end{aligned}

The numbers of paths of area nn with r=1,2,…r=1,2,\ldots returns are, for n=1,…,8n=1,\ldots,8: 1; 1, 1; 1, 2, 1; 2, 3, 3, 1; 3, 6, 6, 4, 1; 5, 11, 13, 10, 5, 1; 8, 20, 27, 24, 15, 6, 1; 13, 36, 54, 55, 40, 21, 7, 1.

Proof of Theorem 7.3

Proof of Theorem 7.3. Let us first prove the formula for τk\tau_k. To this end we write Tk(q)=g(q)−g[k](q)T_k(q)=g(q)-g^{[k]}(q) and δh=Mh−Mh(k)\delta_h=M_h-M_h^{(k)}. Subtracting the recursions for MhM_h and Mh(k)M_h^{(k)}, with Mk+1(k)=0M_{k+1}^{(k)}=0, one finds

δh=q2h+1MhMh(k)δh+1,δk+1=Mk+1.\delta_h=q^{2h+1}M_hM_h^{(k)}\delta_{h+1},\qquad\delta_{k+1}=M_{k+1}.

Since g=qM1g=qM_1, iteration gives

Tk(q)=q(k+1)2Bk(q),Bk(q)=Mk+1(q)∏h=1kMh(q)Mh(k)(q).T_k(q)=q^{(k+1)^2}B_k(q),\qquad B_k(q)=M_{k+1}(q)\prod_{h=1}^{k}M_h(q)M_h^{(k)}(q).

Note that the exponent 1+∑h=1k(2h+1)=(k+1)21+\sum_{h=1}^{k}(2h+1)=(k+1)^2 is precisely the area of the pyramid of height k+1k+1. On a sufficiently small complex neighbourhood of q0q_0 the factors are analytic and nonzero. Moreover, for some r<1r<1 one has Mh=1+O(rh)M_h=1+O(r^h) and Mh(k)=1+O(rh)M_h^{(k)}=1+O(r^h) uniformly in k≥hk\ge h, and for each fixed hh the latter converges locally uniformly to MhM_h. These summable bounds justify the convergence of the products and of their derivatives. Since

∏h=1∞Mh(q)=lim⁡H→∞A(qH+1)A(q)=1A(q),\prod_{h=1}^{\infty}M_h(q)=\lim_{H\to\infty}\frac{A(q^{H+1})}{A(q)}=\frac{1}{A(q)},

one obtains Bk(q)→A(q)−2B_k(q)\to A(q)^{-2} locally uniformly. Evaluating at q0q_0 one gets (18), and logarithmic differentiation gives

Tk′(q0)=τk((k+1)2q0+O(1)).(19)T_k'(q_0)=\tau_k\left(\frac{(k+1)^2}{q_0}+O(1)\right). \tag*{(19)}

Next, let us compare the roots q0(k)q_0^{(k)} and q0q_0. The coefficients of g[k]g^{[k]} increase to those of gg, which gives uniform convergence on every closed disc strictly inside ∣q∣<ρ|q|<\rho. Let us choose r∈(q0,ρ)r\in(q_0,\rho) such that q0q_0 is the only zero of 1−g1-g in ∣q∣≤r|q|\le r. By Rouché’s theorem, for all sufficiently large kk the function 1−g[k]1-g^{[k]} has exactly one zero in this disc. It is the positive simple root q0(k)q_0^{(k)}, and q0(k)→q0q_0^{(k)}\to q_0. Put Δk=q0(k)−q0\Delta_k=q_0^{(k)}-q_0. The derivatives (g[k])′(g^{[k]})' are uniformly bounded below near q0q_0 on the real axis, and the second derivatives are uniformly bounded there. The mean value theorem gives Δk=O(τk)\Delta_k=O(\tau_k). Taylor expansion and (B.1) then yield

τk=(g[k])′(q0)Δk+O(Δk2),(g[k])′(q0)=g′(q0)+O(k2τk).\tau_k=(g^{[k]})'(q_0)\Delta_k+O(\Delta_k^2),\qquad(g^{[k]})'(q_0)=g'(q_0)+O(k^2\tau_k).

Thus Δk=τk/g′(q0)(1+O(k2τk))\Delta_k=\tau_k/g'(q_0)\left(1+O(k^2\tau_k)\right), and expanding log⁡(1+Δk/q0)\log(1+\Delta_k/q_0) one obtains the estimate for λk\lambda_k.

The uniform estimate for the probability is obtained in the same way as in Theorem 6.1. On ∣q∣=r|q|=r, ∣1−g[k](q)∣|1-g^{[k]}(q)| is bounded below uniformly in large kk. Subtracting the simple pole and applying Cauchy’s formula one finds

rn[k]=ck(q0(k))−n+O(r−n),ck=1q0(k)(g[k])′(q0(k))⟶C,r_n^{[k]}=c_k\left(q_0^{(k)}\right)^{-n}+O(r^{-n}),\qquad c_k=\frac{1}{q_0^{(k)}(g^{[k]})'(q_0^{(k)})}\longrightarrow C,

uniformly in kk, and it remains to divide by the asymptotic formula for rnr_n.

Finally, let us prove the distributional approximation. Put ak=Λq0(k+1)2a_k=\Lambda q_0^{(k+1)^2}. We have λk/ak→1\lambda_k/a_k\to1 and ck/C→1c_k/C\to1. For each fixed finite set of kk, both the probabilities and e−nake^{-na_k} tend to zero; indeed q0(k)>q0q_0^{(k)}>q_0, and the bounded-height generating function is analytic in a disc of radius larger than q0q_0. For large kk one uses the uniform pole estimate and

sup⁡t≥0∣e−(1+ϵ)t−e−t∣⟶0as ϵ→0.\sup_{t\ge0}\left|e^{-(1+\epsilon)t}-e^{-t}\right|\longrightarrow0\qquad\text{as }\epsilon\to0.

Splitting the supremum into these two ranges one obtains the claim; the case k=0k=0 is immediate, since P(Hn≤0)=0\mathbb{P}(H_n\le0)=0 for n≥1n\ge1. For the last statement, let bn=log⁡(Λn)/log⁡(1/q0)b_n=\sqrt{\log(\Lambda n)/\log(1/q_0)}. At k=⌊bn⌋−2k=\lfloor b_n\rfloor-2 the exponential approximation tends to zero, whereas at k=⌊bn⌋+1k=\lfloor b_n\rfloor+1 it tends to one, which proves the OP(1)O_{\mathbb{P}}(1) bound.

References

  1. [1]A. L. Owczarek and T. Prellberg, Enumeration of area-weighted Dyck paths with restricted height, Australas. J. Combin. 54 (2012), 13–18.
  2. [2]A. P. Polychonakos, Length and area generating functions for height-restricted Motzkin meanders, Phys. Rev. E 105 (2022), 024102.
  3. [3]L. Gan, Lattice random walks and quantum A-period conjecture, SciPost Phys. 19 (2025), 053.DOI
  4. [4]L. Gan, S. Ouvry and A. P. Polychronakos, Combinatorics of generalized Dyck and Motzkin paths, Phys. Rev. E 106 (2022), 044123.DOI
  5. [5]S. Ouvry and A. P. Polychronakos, Hamiltonian and exclusion statistics approach to discrete forward-moving paths, Phys. Rev. E 104 (2021), 014143.DOI
  6. [6]I. Gahramanov and E. T. Musaev, Integrability properties of Motzkin polynomials, J. Math. Phys. 61 (2020), 033509.arxiv.org/abs/1706.00197
  7. [7]F. Aydogmus and M. Mullahasanoglu, Arithmetic selection rules in dispersionless Hamiltonian systems, arXiv:2608.11179 (2026).arxiv.org/abs/2608.11179
  8. [8]M. Mullahasanoglu, Liouville integrable binomial Hamiltonian system, J. Phys. Conf. Ser. 2667 (2023), 012041.arxiv.org/abs/2304.04500
  9. [9]P. Kucharski, M. Reineke, M. Stosić and P. Sułkowski, Knots-quivers correspondence, Adv. Theor. Math. Phys. 23 (2019), 1849–1902.DOI
  10. [10]M. Panfil, M. Stosić and P. Sułkowski, Donaldson-Thomas invariants, torus knots, and lattice paths, Phys. Rev. D 98 (2018), 026022.DOI
  11. [11]M. Stosić and P. Sułkowski, Torus knots and generalized Schröder paths, Nuclear Phys. B 1012 (2025), 116814.arxiv.org/abs/2405.10161
  12. [12]D. Đorđević and M. Stosić, Lattice paths and quiver generating series with higher level generators, arXiv:2408.01832 (2024).
  13. [13]A. Dwivedi and R. Pichai, Double twist knots and lattice paths, arXiv:2605.02786 (2026).arxiv.org/abs/2605.02786
  14. [14]C. Ji, Q. Tang and C. Yang, Schröder paths, their generalizations and knot invariants, arXiv:2407.20010 (2024).arxiv.org/abs/2407.20010
  15. [15]M. Stosić, Generalized knots-quivers correspondence, J. Knot Theory Ramifications 34 (2025), 25500053.arxiv.org/abs/2402.03066
  16. [16]P. Kucharski and D. Noschenko, Knot-quiver correspondence: a brief review, arXiv:2505.05668 (2025).arxiv.org/abs/2505.05668
  17. [17]P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32 (1980), 125–161.
  18. [18]P. Flajolet and R. Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009.
  19. [19]OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A143951.
  20. [20]A. J. Bu, Explicit generating functions for the sum of the areas under Dyck and Motzkin paths (and for their powers), Discrete Math. Lett. 14 (2024), 1–6.arxiv.org/abs/2310.17026
  21. [21]D. Merlini, Generating functions for the area below some lattice paths, Discrete Math. Theor. Comput. Sci. Proc. AC (2003), 217–228.DOI
  22. [22]G. Gasper and M. Rahman, Basic hypergeometric series, 2nd ed., Cambridge University Press, Cambridge, 2004.

Paper details

vlnc:W_ajvz39fx
Version
v1 · latest
Published
Fresh — published within the last 30 days
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Anthropic Claude Fable, OpenAI ChatGPT

View statement
Looking for related papers…
Contents