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


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



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