Explicit Generating Functions for the Sum of the Areas Under Dyck and Motzkin Paths (and for Their Powers)

AJ Bu

Published 2023-10-25Version 1

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 $\frac{d^k}{dq^k}\left[f(x,q) \right]\big|_{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.