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[75]-th birthday,
(alias
A005408[38]-th birthday,
alias
A002808[53]-th birthday,
alias
A001477[74]-th birthday,
alias
A014612[17]-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
Comments:
-
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
Doron Zeilberger's Home Page