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 (19162020)
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

If you want to see an article with 16 theorems enumerating Dyck paths of semilength n
obeying certain restrictions about the heights of peaks and valleys and length of
upward and downward runs where the sets of restrictions are finite
The input gives you
the output.

If you want to see a much longer such article with 256 theorems enumerating Dyck paths of semilength n
obeying certain restrictions about the heights of peaks and valleys and length of
upward and downward runs
The input gives you
the output.

If you want to see an article where the set of restrictions is avoiding the infinite arithmetical
progression 2r+3 . Note that Theorem 9 (featuring the Motzkin numbers) answers Vladimir Retakh's question that inspired this
whole project.
The input gives you
the output.

If you want to see an article where the set of restrictions is avoiding the infinite arithmetical
progression 3r+1
The input gives you
the output.

If you want to see an article where the set of restrictions is avoiding the infinite arithmetical
progression 4r+3
The input gives you
the output.

If you want to see an article where the set of restrictions is avoiding the infinite arithmetical
progression 5r+1
The input gives you
the output.
Sample Input and Output Files for DyckClever.txt

If you want to see algebraic equations satisfied by the ordinary generating functions
of sequences enumerating Dyck paths that avoid peakheights in a given set A
and valleyheights in another given set B, as well explicit expressions in terms of C:=(1sqrt(14*x))/(2x),
for all pairs (A,B) of subsets of {1, ..., 5},
the
The input gives you
the output.

If you want to see, in addition to the above, linear recurrences for the enumerating sequences,
the first fifty terms and the exact value for n=1000,the
The input gives you
the output.

If you want to see algebraic equations satisfied by the ordinary generating functions
of sequences enumerating Dyck paths that avoid peakheights in a given set A
and valleyheights in another given set B,
for many pairs (A,B) of affine linear expressions of the form c1*r+c2 where c1 and c2 are nonnegative integers
and r is a symbol denoting an arbitrary nonnegative inetger and our Dyck paths avoid
peakheights in the range of A and valleyheights in the range of B
the
The input gives you
the output.

If you want to see the above, but also linear recurrences, the first few terms, and the value at n=1000
the
The input gives you
the output.

If you want to see algebraic equations satisfied by the ordinary generating functions
of sequences enumerating Dyck paths that avoid ascending runlenghts in a given set A
and descending runlengths in another given set B, for all pairs A, B that are subsets of
{1,2,3} (so altogether 64 pairs)
the
The input gives you
the output.

If you want to see algebraic equations satisfied by the ordinary generating functions
of sequences enumerating Dyck paths that avoid ascending runlengths in a given set A
and descending runlengths in another given set B,
for many pairs (A,B) of affine linear expressions of the form c1*r+c2 where c1 and c2 are nonnegative integers
and r is a symbol denoting an arbitrary nonnegative inetger and our Dyck paths avoid
peakheights in the range of A and valleyheights in the range of B
the
The input gives you
the output.
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page