Automatic Counting of Restricted Dyck Paths via (Numeric and Symbolic) Dynamic Programming

By Shalosh B. Ekhad and Doron Zeilberger


.pdf   .ps   .tex  

(Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org)

Written: June 3, 2020.

In memory of Richard Guy (1916-2020)

In his classic essay ``The Strong Law of Small Numbers", Richard Guy gave numerous cautionary tales where one can't `jump to conclusions' from the first few terms of a sequence. But if you are cautious enough you can find many families of enumeration problems where it is very safe to deduce the general pattern from the first few cases, obviating the need for either the human or the computer to think too hard, and by using the `Keep It Simple Stupid' principle ( KISS for short), one can easily derive many deep enumeration theorems by doing exactly what Richard Guy told us not to do, computing the first few terms of the sequence and deducing the formula for the general term. We admit that often "few" should be replaced by "quite a few", but it is still much less painful than trying to figure out the intricate combinatorial structure by `conceptual' means.

Alas, sooner or later, "keeping it simple" becomes impractical, since complicated answers require lots of data, that is generated via (very efficient) numeric dynamic programming, but guessing the pattern, for large problems, takes a long time. With a little bit of thought, by both the human programmer and the machine, using symbolic rather then numeric dynamic programming, one can get exact answers even faster.


Maple packages



Sample Input and Output Files for Dyck.txt



Sample Input and Output Files for DyckClever.txt


Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

Doron Zeilberger's Home Page