Using Symbolic Computation to Explore Generalized Dyck Paths and Their Areas
By AJ Bu and Doron Zeilberger
.pdf
.tex
Written: May 15, 2023
Dedicated to Symbolic Computation pioneer Bruno Buchberger (b. 22 October, 1942) on his
80th birthday
[To appear in Palestinian Journal of Mathematics]
We show the power of Bruno Buchberger's seminal Groebner Basis algorithm, interfaced,
seamlessly, with what we call symbolic dynamical programming, to automatically generate algebraic
equations satisfied by the generating functions enumerating so-called Generalized Dyck Walks, i.e.
2D walks that start and end on the x-axis, and never dip below it, for an arbitrary set of steps.
More impressively, we combine it with calculus (that Maple knows very well!), to automatically
compute generating functions for the sum-of-the-areas of these generalized Dyck paths, and even
for the sum of any given power of the areas, enabling us to get statistical information about the
area under a random generalized Dyck path.
Maple packages
-
GDW.txt,
using Groebner basis to find rigorously algebaric equations satisfied by generating functions enumerating Generalized Dyck Paths,
and using them to generate many terms and obtain recurrences.
Not discussed in the paper, but of related interest are the following two Maple packages, that test Haglund's theorem
that the so-called Area and Bounce Statistics are symmetric for Dyck paths, and that tries for a combinatrial proof
-
AreaBounce.txt,
a Maple package for experimenting with the Area and Bounce statistics defined on Dyck Paths
-
BounceArea.txt,
An alternative Maple package for experimenting with the Area and Bounce statistics defined on Dyck Paths
Sample Input and Output for GDW.txt
If you want to see algebraic equations satisfied by generating functions enumerating generalized Dyck paths with set of steps subsets of {-2,-1,0,1,2} (exlucding trivial cases)
and sometimes linear recurrences with polynomial coefficients satisfied by the sequences themselves
the input gives the
output
If you want to see algebraic equations satisfied by generating functions enumerating generalized Dyck paths with set of steps subsets of {-3,-2,-1,0,1,2,3} (exlucding trivial cases)
and sometimes linear recurrences with polynomial coefficients satisfied by the sequences themselves
the input gives the
output
If you want to see the algebraic equation satisfied by the generating function enumerating generalized Dyck paths with set of steps {-4,-3,-2,-1,0,1,2,3,4}
the input gives the
output
If you want to see algebraic equations for the SYMBOLIC probability generating functions for staying in the casino with various loaded dice,
the input gives the
output
If you want to see algebraic equations for the SYMBOLIC probability generating functions for staying in the casino with other kinds of loaded dice,
the input gives the
output
If you want to see algebraic equations for a typical NUMERICAL distribution
the input gives the
output
The following output concerns procedures listed by ezraA(); and ezraA1(); in the Maple package GDW.txt.
If you want to see algebraic equations for the SUM OF THE AREAS under generalized Dyck paths for all non-trivial subsets of {-2,-1,0,1,2},
the input gives the
output
If you want to see algebraic equations for the SUM OF THE AREAS under generalized Dyck paths for seven subsets of {-3,-2,-1,0,1,2,3}
the input gives the
output
Note: it would have taken too long to let the program finish, so we terminated it, but these seven theorems give you the flavor.
If you want to see linear recurrences for the number, and sometimes, sum of squares, and less often sum of area-squared
for generalized Dyck paths for all subsets of {-2,-1,0,1,2} (for which it makes sense)
the input gives the
output
Sample Input and Output for AreaBounce.txt
-
If you want to see empirical verification that the area and bounce statistics are symmetic on Dyck paths of semi-length n for n from 1 to 30 (using Haglund's theorem )`0:
the input gives the
output (in about 11 seconds).
Doron Zeilberger's Home Page
AJ Bu's Home Page