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).