The Generating Functions Enumerating 12..d-Avoiding Words with r occurrences of each of 1,2, ..., n are D-finite for all d and all r

By
Shalosh B. Ekhad and Doron Zeilberger

.pdf   .ps   .tex

Posted: Dec. 5, 2014

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

Dedicated to Neil James Alexander Sloane (born October 10, 1939), on his A000027-th birthday, (alias A005408-th birthday, alias A002808-th birthday, alias A001477-th birthday, alias A014612-th birthday, and 13520 other aliases)

In a recent beautiful article, Nathaniel Shar and Doron Zeilberger proved that the generating function of the sequence enumerating 123-avoiding words with r occurences of each of the letters 1,2, ..,n is always algebraic. It is well-known that this is no longer true for 12..d-avoiding words with d ≥ 4, even for r=1, but in 1990 Doron Zeilberger showed that (for the classical, r=1, case) it is the next best thing, that it is D-finite, i.e. for every d, the generating function satisfies a linear differential equation with polynomial coefficients, or equivalently, the enumerating sequence itself is P-recursrive, i.e. satisfies a linear recurrence equation with polynomial coefficients. Ira Gessel famously discovered (and proved) a beautiful determinant with Bessel functions, for the exponential generating function, (that also implies the above result), and Amitai Regev famously derived delicate and precise asymptotics (both for the permutation case (i.e. r=1)).

In the present article, dedicated to guru Neil Sloane on his 75-th birthday, we observe that the analogous generating functions for multi-set permutations, where every letter appears the same number of times, say r, are still always D-finite, (for every d and every r), and we actually crank out the first few terms of quite a few of them, many of whom are not yet in the OEIS. We also conjecture an asymptotic expression for this sequence (in terms of r and d), that reduces to Amitai Regev's famous formula when r=1, and pledge a 100 dollar donation to the OEIS in honor of the first one to prove it. We pldedge another 100 dollars for extending Ira Gessel's Bessel determinant, from the r=1 case to general r.

Added Dec. 19, 2014: Guillaume Chapuy beautifully proved our conjectured asymptotics, generalizing Regev's famous formula for r=1, and even did the "extra credit". DZ donated the promised amount of \$125.
Added May 12, 2015: Ferenc Balogh made great progress on the second challenge of this article, that was to generalize Ira Gessel's beautiful determinant expression from r=1 to general r. He found such expressions for r=2 and r=3, and his method indicates an algorithm to do it for an arbitrary, numeric r, but with increasingly complicated expressions. DZ donated 25 dollars to the OEIS in honor of Frerenc Balogh for this progress.

Added July 1, 2015: Ferenc Balogh fully solved the second challenge of this article, that was to generalize Ira Gessel's beautiful determinant expression from r=1 to general r. DZ donated the promised 100 dollars to the OEIS in honor of Frerenc Balogh for this impressive accomplishment.

Maple Packages

• SLOANE75: uses Zeilberger-style Enumeration schemes, extended to words, to compute 123-avoiding and 1234-avoiding words of various kinds.

• NEIL: Uses Robinson-Schenstead-Knuth (RSK) plus the Holonomic paradigm (dear to us) to enumerate 12...d-avoiding words with r 1's, r 2's, r n's for many d's and r's.

Some Input and Output files for the Maple package SLOANE75

• If you want to see, the first 20 terms (for the OEIS), linear recurrences with polynomial coefficients, (guessed, but easily made rigorous via the Holonomic Paradigm (see article)) and asymptotics to order 6, and the 1000-th term!, of the sequences sequences Enumerating 123-Avoiding rn-letter Words with r 1's, r 2's, ..., r n's, for r=1 to r=5, then

the input   yields the output

• This duplicates, from a holonomic standpoint, the data from the above mentioned Shar-Zeilberger article.

• The case r=1 is the famous A000108 (alias Catalan numbers) sequence, the hero of Guru Richard Stanley's forthcoming book.

• The case r=2 is A220097 entered by Lara Pudwell and considered by her and her collaborators in this article, where they conjectured a second-order recurrence that was proved by guru W. Y. C. Chen and his disciples A. Y. L. Dai and R. D. P. Zhou in this article, via a beautiful explicit algebraic generating function. By "general holonomic nonsense" (that can be justfied rigorously) our (and Lara et. al.'s) guessed recurrence can be given an alternative proof.

• The case r=3 is not yet (Oct. 21, 2014) in the OEIS, but is in this page produced by Lara Pudwell's computer. She only lists 10 terms, while we can list as many as desired, in particular we give the 1000-th term.

• The cases r=4, and r=5 are brand new!

• If you want to see, the first 20 terms (for the OEIS), linear recurrences with polynomial coefficients, (guessed, but easily made rigorous via the Holonomic Paradigm (see article)) and asymptotics to order 6 (only for r=3), and the 1000-th term!, of the sequences sequences Enumerating 123-Avoiding rn-letter Words with
n 1's, n 2's, ..., n r's,
for r=3 to r=5

the input   yields the output

Note: None of these sequnces were in the OEIS on Oct. 21, 2014, or for that matter, anywhere in the internet. We are hereby filling this much-needed gap.

• If you want to see, the first 20 terms (for the OEIS), linear recurrences with polynomial coefficients, (guessed, but easily made rigorous via the Holonomic Paradigm (see article)) and asymptotics to order 6, and the 1000-th term!, of the sequences sequences Enumerating ALL 123-Avoiding n-letter words in the letters {1, ..., n}

the input   yields the output

Note: This is sequence A239295, entered by Alois Heinz.

Some Input and Output files for the Maple package NEIL

• If you want to see, the first 20 terms (for the OEIS), linear recurrences with polynomial coefficients, (guessed, but easily made rigorous via the Holonomic Paradigm (see article)) and asymptotics to order 6, and the 1000-th term!, (using the RSK approach), of the sequences sequences Enumerating 123-Avoiding rn-letter Words with r 1's, r 2's, ..., r n's, for r=1 to r=6, then

the input   yields the output

Note: The cases 1 ≤ r ≤ 5 were done in above-mentioned file, the notes also apply to this case.

• If you want to see, the first 20 terms (for the OEIS) (for r=1,r=2,r=3,r=4), and for r=1 and r=2,linear recurrences with polynomial coefficients, (guessed, but easily made rigorous via the Holonomic Paradigm (see article)) and asymptotics to order 6, and the 1000-th term!, (using the RSK approach), of the sequences Enumerating 1234-Avoiding rn-letter Words with r 1's, r 2's, ..., r n's,

the input   yields the output

Notes:

• The case r=1 is A005802;
• the case r=2 was not in the OEIS on Dec. 5, 2014, but was in this page produced by Lara Pudwell's computer. She only lists 10 terms, while we can list as many as desired (20 in this file), and we also list the 1000-th term.
• the case r=3 was not in the OEIS on Dec. 5, 2014, but was in the above page produced by Lara Pudwell's computer. She only lists 7 terms, while we list 20 terms.
• The case r=4 was neither on the OEIS nor elsewhere on Dec. 5, 2014.
• If you want to see, for old-time's sake, the sequences enumerating 12...d-avoiding PERMUTATIONS (not words) for d from 2 to 6,

the input   yields the output

Notes:

• The case d=2 is A000012, "the simplest sequence of positive integers".
• The case d=3 is A00108, the Catalan sequence, already mentioned above.
• The case d=4 is A005802, also mentioned above.
• The case d=5 is A047889.
• The case d=6 is A047890.

• If you want to see the first 20 terms of the sequences enumerating words with
r 1's, r 2's, ..., r n's
that do not contain an increasing susequence of length d for d=3 to d=8, for r=1 to r=4,

the input   yields the output

Note: the cases d=3,4 are already in previous output files, as well as r=1 for d ≤ 6, but the other sequences are probably new.

Personal Journal of Shalosh B. Ekhad and Doron Zeilberger