Explicit Generating Functions for the Sum of the Areas Under Dyck and Motzkin Paths and for Their Powers
By AJ Bu
PDF
Posted October 2023: arXiv:2310.17026
In this paper, we describe how to find the generating function for the sum of the areas under
Motzkin paths of length n through a method that uses dynamical programming, which we show
can be expanded for paths with any given set of steps that start and end at height zero and never
have a negative height. We then explore the case where, instead of a set of steps, we are given
the quadratic functional equation
f (x, q) = P (x, q) + Q(x, q)f (x, q) + R(x, q)f (x, q)f (qx, x).
We
present a fully automated method for finding perturbation expansions of the solutions f (x, q) to
such quadratic functional equations and demonstrate this method using Motzkin paths. More
importantly, we combine computer algebra with calculus to automatically find
d^k/dq^k[f(x,q)]|_{q=1}
explicitly expressed in terms of radicals. We use Dyck and Motzkin paths to exemplify how this
can be used to find explicit generating functions for the sum of the areas under such paths and
for the sum of a given power of the areas.
Maple package
Sample Input and Output Files for qEW.txt
- Suppose D(x,q) is the bivariate generating function for Dyck paths of length n and area m.
This provides:
- up to the 10th derivative of D(x,q) with respect to q evaluated at q=1
- The generating functions for
- the sum areas under Dyck paths of length n
- the sum of the squares of the areas under Dyck paths of length n
- the sum of the cubes of the areas under Dyck paths of length n
- the average area under Dyck paths of semi-length n for n=1,...,250 and the variances
The input gives you
the output.
Suppose M(x,q) is the bivariate generating function for Motzkin paths of length n and area m.
This provides:
- up to the 10th derivative of M(x,q) with respect to q evaluated at q=1
- The generating functions for
- the sum areas under Motzkin paths of length n
- the sum of the squares of the areas under Motzkin paths of length n
- the sum of the cubes of the areas under Motzkin paths of length n
- the average area under Motzkin paths of length n for n=1,...,250 and the variances
The input gives you
the output.
This uses the procedure qnwdK to verify the outputs given by the procedures SeqF1 and DerK for Dyck paths
The input gives you
the output.
This uses the procedure qnwdK to verify the outputs given by the procedures SeqF1 and DerK for Motzkin paths
The input gives you
the output.
This uses the procedure qnwdK to provide the enumerating function for the total area under paths of lengths 0 to 20 with steps from a given set S
The input gives you
the output.
AJ Bu's Papers
AJ Bu's Home Page