(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

• Dyck.txt

• DyckClever.txt

Sample Input and Output Files for Dyck.txt

• If you want to see an article with 16 theorems enumerating Dyck paths of semi-length 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 semi-length 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 peak-heights in a given set A and valley-heights in another given set B, as well explicit expressions in terms of C:=(1-sqrt(1-4*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 peak-heights in a given set A and valley-heights 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 non-negative integers and r is a symbol denoting an arbitrary non-negative inetger and our Dyck paths avoid peak-heights in the range of A and valley-heights 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 run-lenghts in a given set A and descending run-lengths 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 run-lengths in a given set A and descending run-lengths 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 non-negative integers and r is a symbol denoting an arbitrary non-negative inetger and our Dyck paths avoid peak-heights in the range of A and valley-heights in the range of B the
  The input gives you the output.

Doron Zeilberger's Home Page