.pdf
.ps
.tex
Exclusively published in the
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
First Written: Dec. 29, 2006.
This version (of this webpage NOT of the article): March 18, 2013.
[It adds links to the Maple package
ARV
and its output files, corroborating an amazing result of M. Albert, N. Ruksuc, and V. Vatter. See the bottom of this webpage.]
Previous Version: March 26, 2007 (incorporating referee Lara Pudwell's
comments.)
March 28, 2007 (incorporating some of referee Vince Vatter's comments.)
This is a modest improvement on
Vince Vatter's major improvement
of my
original enumeration schemes paper
My brilliant current student, Lara Pudwell, is currently extending this
to words (a.k.a. multiset permutations).
added March 26, 2007: Thoroughly refereed by Lara Pudwell.
Read
Lara Pudwell's report and
my response .
added March 28, 2007: Also thoroughly refereed by Vince Vatter.
Read
Vince Vatter's report and
my response .
Important: This article is accompanied by Maple
package
VATTER
that tries to find VatterZeilbergertype enumeration schemes
for any set of patterns.
Sample Input and Output for VATTER

In order to find enumeration schemes for single patterns of
length 3 the
input would yield the
output

In order to find enumeration schemes for a set of two patterns,
both of length 3, the
input would yield the
output

In order to find enumeration schemes for a set three patterns,
each of length 3 the
input would yield the
output

In order to find enumeration schemes for sets of four patterns of
each length 3 the
input would yield the
output

In order to find enumeration schemes for single patterns of
length 4 the
input would yield the
output

In order to find enumeration schemes for sets of two patterns
one of length 3 and the other of length 4, the
input would yield the
output

In order to find enumeration schemes for sets of two patterns
both of length 4, the
input would yield the
output

In order to find enumeration schemes for sets of two patterns ,
one of length 3 and the other of length 5, the
input would yield the
output

In order to find enumeration schemes for sets of three patterns ,
one of length 3 and the other two of length 4, the
input would yield the
output

In order to find enumeration schemes for sets of three patterns ,
one of length 4 and the other two of length 3, the
input would yield the
output

In order to find enumeration schemes for sets of three patterns ,
all of length 4 , the
input would yield the
output
Added March 18, 2013: On March 7, 2013, Vince Vatter gave a brilliant talk
[part 1,
part 2]
where he talked about, the still unwrittenup amazing result (joint with Michael Albert and Nik Ruskuc),
that the pattern 321 is "barely" algebraic, i.e., while it is true that its
enumerating generating function is algebraic (being counted by the famous Catalan numbers), if
you add any pattern(s), you would get rational generating functions.
Since I don't (completely) trust human reasoning, I adapted the package VATTER, and wrote
a new Maple package
that tested this empirically.
Sample Input and Output for ARV for the pattern 321

In order to find generating functions for the sequences enumerating permutations
that avoid the pattern 321 AND any ONE other pattern of length 4 (NOT containing it of course)
the
input would yield the
output

In order to find generating functions for the sequences enumerating permutations
that avoid the pattern 321 AND any ONE other pattern of length 5 (NOT containing it of course)
the
input would yield the
output

In order to find generating functions for the sequences enumerating permutations
that avoid the pattern 321 AND any TWO other patterns of length 4 (NOT containing it of course)
the
input would yield the
output

In order to find generating functions for the sequences enumerating permutations
that avoid the pattern 321 AND any TWO other patterns of length 5 (NOT containing it of course)
the
input would yield the
output
Vince Vatter also mentioned that the analogous result for the pattern 312 is already known,
and can be found (Example 2 on Page 12) of this
beautiful article
of Michael Albert and Mike Atkninson
entitled "Simple permutations and pattern restricted permutations",
officially published in Discrete Mathematics v. 300 (2005), 115.
Here is the empirical evidence for it.
Sample Input and Output for ARV for the pattern 312

In order to find generating functions for the sequences enumerating permutations
that avoid the pattern 312 AND any ONE other pattern of length 4 (NOT containing it of course)
the
input would yield the
output

In order to find generating functions for the sequences enumerating permutations
that avoid the pattern 312 AND any ONE other pattern of length 5 (NOT containing it of course)
the
input would yield the
output

In order to find generating functions for the sequences enumerating permutations
that avoid the pattern 312 AND any TWO other patterns of length 4 (NOT containing it of course)
the
input would yield the
output

In order to find generating functions for the sequences enumerating permutations
that avoid the pattern 312 AND any TWO other patterns of length 5 (NOT containing it of course)
the
input would yield the
output
[It ran out of memory in the middle, sorry!]
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page