Explicit Expressions for the First 20 Moments of the Area Under Dyck and Motzkin Paths AJ BU, Shalosh B. EKHAD, and Doron ZEILBERGER

Abstract: We show the utility of AJ Bu’s recent article for computing explicit expressions for the generating functions of sums of powers of areas under Dyck and Motzkin paths, by deducing from them explicit expressions for the actual sequences. This leads to explicit expressions for the scaled moments, and to the elementary verification, up to any specific moment, that they tend to those of the area under Brownian excursion. Maple package and Output Files This article is accompanied by a Maple package, qEWplus.txt, and two output files. They are obtainable from the front of this article

https://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/qew.html .

The Power of Symbolic Computation In [B], the first author harnessed the power of symbolic computation to generate generating functions for the sum of r^{th} powers of areas under Dyck and Motzkin paths, by interfacing algebra and calculus. Once you have these sequences themselves, you can immediately derive the actual moments (by dividing by the total number of paths, i.e. the Catalan and Motzkin numbers respectively), that in turn would give you the moments about the mean and the scaled moments. Alas, getting generating functions for these quantities is awkward. It would be much more helpful to have explicit expressions for the actual sequences, not just their generating functions. The power of guessing Recall that a Dyck path (respectively Motzkin path) is a sequence of atomic steps of the form (x, y) → (x+1, y−1), (x, y) → (x+1, y+1) (respectively of the form (x, y) → (x+1, y−1), (x, y) → (x + 1, y + 1), (x, y) → (x + 1, y)) that

• Start at the origin (0, 0).

• End somewhere on the x axis, i.e. y = 0 .

• Never go strictly below the x axis, i.e. always stay in y ≥ 0. Equivalently sequences in {1, −1} (respectively {−1, 0, 1}) whose total sum is 0 and whose partial sums are non-negative. See [B] for details. It turns out (the proofs are left to the reader) that the following facts hold. Fact 1: Let C_{r}(n) be the sum of the r^{th} powers of the areas under Dyck paths from (0, 0) to (2n, 0):

C_{r}(n) := ∑_{P ∈Dyck(n)} Area(P)^{r} .

Also let C_{n} be the Catalan numbers (2n)!/(n!(n + 1)!) (same as C_{0}(n)).

There exist polynomials in n, P_{1}(n) and P_{2}(n) such that

C_{r}(n) = P_{1}(n) C_{n} + P_{2}(n) 4^{n} .

Fact 2: Let M_{r}(n) be the sum of the r^{th} powers of the areas under Motzkin paths from (0, 0) to (n, 0):

M_{r}(n) := ∑_{P ∈Motzkin(n)} Area(P)^{r} .

Also let M_{n} be the Motzkin numbers ∑_{r=0}^{n} \frac{n!(2r)!}{r!^{2}(r+1)!(n−r)!} (same as M_{0}(n)).

There exist polynomials Q_{1}(n), Q_{2}(n) , Q_{3}(n) , Q_{4}(n) such that

M_{r}(n) = Q_{1}(n) M_{n} + Q_{2}(n) M_{n+1} + Q_{3}(n) 3^{n} + Q_{4}(n) (−1)^{n} .

Since we know the format of these closed-form expressions for C_{r}(n) and M_{r}(n), we can crank out sufficiently many terms, use undetermined coefficients, and ask Maple to solve the resulting system of linear equations. Note that once conjectured, the proof is purely routine, even if you don’t believe that the facts always hold. Maple can all by itself find the generating functions for the conjectured expressions (they all are derivable from those for the Catalan and Motzkin numbers), and check that they coincide with those found in [B].

Once we have explicit expressions for C_{r}(n), we get an explicit expression for the r^{th}-moment m_{r}(n) = \frac{C_{r}(n)}{C_{n}}, and from them the moments about the mean, and in turn, the scaled moments. Similarly for the Motzkin numbers (and any of their ilk). Then we take the limit as n → ∞.

To our great delight, they coincided, up to the 20-th moment with those of the area under Brownian Excursion B_{ex}([T], and see [J] for a great exposition). Of course one can go much further.

According to [J] (Equations (6) and (7) there),

EB_{ex}^{k} = \frac{4\sqrt{π}2^{−k/2}k!}{Γ((3k − 1)/2)} K_{k} , k ≥ 0 ,

where K_{k} is the sequence of rational numbers defined by the recurrence, K_{0} = −\frac{1}{2} and

K_{k} = \frac{3k − 4}{4}K_{k−1} + ∑_{j=1}^{k−1} K_{j} K_{k−j} , k ≥ 0 .

Once you centralize and scale them, you get exactly what we got for the corresponding limits of the first (centralized-scaled) 20 moments for the Dyck paths and Motzkin paths, by fully elementary and finitistic means.

But we can do much more than just find the limit. Since we have explicit expressions, we can take the asymptotics to any desired order.

Explicit expressions for the sum of the powers of areas under Dyck paths from (0, 0) to (2n.0) for all powers from 1 to 20.

C_{1}(n) = \frac{(2n)! (−2n − 1)}{n! (1 + n)!} + 4^{n} ,

C_{2}(n) = \frac{(2n)! (\frac{10}{3}n^{3} + 11n^{2} + \frac{26}{3}n + 2)}{n! (1 + n)!} + 4^{n} (−4n − 2) ,

C_{3}(n) = \frac{(2n)! (−20n^{4} − 60n^{3} − 61n^{2} − 26n − 4)}{n! (1 + n)!} + 4^{n} (\frac{15}{4}n^{3} + \frac{75}{4}n^{2} + \frac{33}{2}n + 4) ,

C_{4}(n) = \frac{(2n)! (\frac{884}{63}n^{6} + \frac{4568}{35}n^{5} + \frac{108043}{315}n^{4} + \frac{14016}{35}n^{3} + \frac{74332}{315}n^{2} + \frac{2416}{35}n + 8)}{n! (1 + n)!}

+4^{n} (−30n^{4} − 101n^{3} − 111n^{2} − 50n − 8) ,

C_{5}(n) = \frac{(2n)! (−\frac{8840}{63}n^{7} − \frac{53044}{63}n^{6} − \frac{128174}{63}n^{5} − \frac{162091}{63}n^{4} − \frac{116888}{63}n^{3} − \frac{48520}{63}n^{2} − \frac{3608}{21}n − 16)}{n! (1 + n)!}

+4^{n} (\frac{565}{32}n^{6} + \frac{6495}{32}n^{5} + \frac{18485}{32}n^{4} + \frac{22825}{32}n^{3} + \frac{7035}{16}n^{2} + \frac{535}{4}n + 16) .

For the explicit expressions for C_{r}(n) for 6 ≤ r ≤ 20, see the output file:

http://sites.math.rutgers.edu/~zeilberg/tokhniot/oqEWplus1.txt .

Explicit expressions for the sum of the powers of areas under Motzkin paths from (0, 0) to (n, 0) for all powers from 1 to 20.

As above M_{n} (same as M_{0}(n)) denote the Motzkin numbers.

M_{1}(n) = (−n − 1) M_{n} + \frac{3^{n+1}}{4} + \frac{(−1)^{n}}{4} ,

M_{2}(n) =

(\frac{25}{36}n^{3} + \frac{11}{3}n^{2} + \frac{191}{36}n + \frac{7}{3}) M_{n}+(−\frac{5}{36}n^{3} − \frac{2}{3}n^{2} − \frac{31}{36}n − \frac{1}{3}) M_{n+1}+(−\frac{3n}{2} − \frac{3}{2}) 3^{n}+(−\frac{n}{2} − \frac{1}{2}) (−1)^{n} ,

M_{3}(n) =

(−\frac{25}{12}n^{4} − \frac{133}{12}n^{3} − \frac{251}{12}n^{2} − \frac{203}{12}n − 5) M_{n} + (\frac{5}{12}n^{4} + \frac{29}{12}n^{3} + \frac{55}{12}n^{2} + \frac{43}{12}n + 1) M_{n+1}

+ (\frac{15}{64}n^{3} + \frac{207}{64}n^{2} + \frac{1521}{256}n + \frac{1503}{512}) 3^{n} + (\frac{15}{64}n^{3} + \frac{93}{64}n^{2} + \frac{585}{256}n + \frac{545}{512}) (−1)^{n} ,

M_{4}(n) = (\frac{221}{324}n^{6} + \frac{31441}{3780}n^{5} + \frac{411613}{11340}n^{4} + \frac{72251}{945}n^{3} + \frac{34189}{405}n^{2} + \frac{59401}{1260}n + \frac{3314}{315}) M_{n}

+ (−\frac{221}{1134}n^{6} − \frac{1409}{630}n^{5} − \frac{27248}{2835}n^{4} − \frac{10781}{540}n^{3} − \frac{122653}{5670}n^{2} − \frac{6349}{540}n − \frac{794}{315}) M_{n+1}

+ (−\frac{15}{16}n^{4} − \frac{63}{8}n^{3} − \frac{1197}{64}n^{2} − \frac{2241}{128}n − \frac{735}{128}) 3^{n}+(−\frac{15}{16}n^{4} − \frac{19}{4}n^{3} − \frac{573}{64}n^{2} − \frac{947}{128}n − \frac{289}{128}) (−1)^{n} .

For the explicit expressions of M_{r}(n), for 5 ≤ r ≤ 20, see the output file:

https://sites.math.rutgers.edu/~zeilberg/tokhniot/oqEWplus2.txt .

Acknowledgment: Many thanks to Svante Janson for educating us on Brownian excursions. References

[B] AJ Bu, Explicit generating functions for the sum of the areas under Dyck and Motzkin paths and for their powers, to appear in Discrete Mathematics Letters.

arxiv: https://arxiv.org/abs/2310.17026 ;
front: https://ajbu1.github.io/Papers/MotzArea/MotzArea.html .

[J] Svante Janson, Brownian excursion area, Wright’s constants in graph enumeration, and other Brownian areas. Probability Surveys 3 (2007), 80-145.

https://www2.math.uu.se/~svante/papers/sj201.pdf

[T] Lajos Takacs, A Bernoulli excursion and its various applications, Adv. in Appl. Probab. 23 (1991), 557-585.

AJ Bu, Shalosh B. Ekhad and Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Email: aj dot bu131 at gmail dot com , ShaloshBEkhad at gmail dot com, DoronZeil
at gmail dot com .

Written: May 5, 2024.

Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilerger, AJ Bu’s web-site, and arxiv.org .