Some Presents to Neil SLOANE for his 75th Birthday: Sequences Counting 12 ... d-Avoiding Words of Various Kinds
By
Shalosh B. Ekhad and Doron Zeilberger
.pdf
.ps
.tex
First Written: Dec. 2, 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)
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
Note:
-
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 cases r=2 as not in the OEIS on Oct. 21, 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 as not in the OEIS on Oct. 21, 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 is neither on the OEIS (Oct. 21, 2014), and nowhere else for that matter.
-
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