The (Ordinary) Generating Functions Enumerating 123-Avoiding Words with r occurrences of each of 1,2, ..., n are Always Algebraic

The (Ordinary) Generating Functions Enumerating 123-Avoiding Words with r occurrences of each of 1,2, ..., n are Always Algebraic

By
Nathaniel Shar and Doron Zeilberger
.pdf .ps .tex
[Appeared in Annals of Combinatorics 20 (2016), 387-396]

First Written: Nov. 18, 2014 ; This version: Nov. 26, 2014 [Thanks to Robin Chapman]

The set of permutations (alias words in the alphabet {1, ..., n} with exactly 1 occurrence of each letter) that do not have an increasing subsequence of length 3 is famously enumerated by the ubiquitous Catalan numbers, whose generating function, C(x) famously satisfies the algebraic equation
C(x)=1+xC(x)² .
Recently, Bill Chen, together with his disciples Alvin Dai and Robin Zhou, discovered, and very elegantly proved, an algebraic equation satisfied by the generating function enumerating 123-avoiding words with two occurrences of each of 1, ..., n. [Sequence A220097 of the bible]
Inspired by the Chen-Dai-Zhou result, we present an algorithm for finding such an algebraic equation for the ordinary generating function enumerating 123-avoiding words with exactly r occurrences of each of 1, ... n for any positive integer r, thereby proving that they are algebraic and not merely D-finite (a fact that is promised by WZ theory). Our algorithm consists of presenting an algebraic enumeration scheme, combined with the Buchberger algorithm.

Added Nov. 26, 2014: This new version states Robin Chapman's conjectured expression for the constant C_r in front of the conjectured asymptotic expression for w_r(n) in the article. (Proved rigoroulsy for 1 ≤ r ≤ 5, except for the constant, that officially is still conjectured even for r=2, but could be easily proved rigorously using standard techniques described so nicely in the Flajolet-Sedgewick bible.]
Added Dec. 30, 2014. The $100 dollar conjecure was generalized, and this more general conjecture (that implies the conjecture made in the presend article) was proved by Guillaume Chapuy. A donation to the OEIS was made.

Maple Package

Words123: a Maple package to implement the algorithm of our paper

Some Input and Output files for the Maple package Words123

If you want to see the minimal algebraic equations satisfied by the generating functions enumerating 123-avoiding words with exactly r occurences of each of the letters {1, ...,n} for r=1, r=2, r=3, obtained directly from the algebraic scheme and the Gröbner bases algorithm
the input yields the output

If you want to see the minimal algebraic equations satisfied by the generating functions enumerating 123-avoiding words with exactly r occurences of each of the letters {1, ...,n} for r=2, r=3, and r=4 obtained by `guessing' (but of course it could be made fully rigorusly proved a posteriori)
Note: you also need the Maple package SCHUTZENBERGER
the input yields the output

If you want to see a linear recurrences, asymptotic expressions to order 6, the first 30 terms, and the 1000-th term of the sequences enumerating 123-avoiding words with exactly r occurences of each of the letters {1, ...,n} from r=1 to r=5
the input yields the output

Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page