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)2   .

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 Cr in front of the conjectured asymptotic expression for wr(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