By Andrew Baxter, Brian Nakamura, and Doron Zeilberger
If you want to see a ranked list of single patterns of length 3
according to the number of permutations that they avoid, followed by the first
100 terms of the (called P31 in the file)
If you want to see a ranked list of sets of two patterns each of length 3
according to the number of permutations that they avoid, followed by the first
50 terms of the (called P32 in the file)
If you want to see a ranked list of sets of three patterns each of length 3
according to the number of permutations that they avoid, followed by the first
50 terms of the (called P33 in the file)
If you want to see a ranked list of sets of four patterns each of length 3
according to the number of permutations that they avoid, followed by the first
50 terms of the (called P34 in the file)
If you want to see a ranked list of sets of five patterns each of length 3
according to the number of permutations that they avoid, followed by the first
50 terms of the (called P35 in the file)
If you want to see a ranked list of sets of six patterns each of length 3
(there is only one such set obviously!, and you don't need a computer for this one!)
according to the number of permutations that they avoid, followed by the first
50 terms of the (called P36 in the file)
If you want to see a ranked list of single patterns of length 4
according to the number of permutations that they avoid, followed by the first
40 terms of the (called P41 in the file)
If you want to see a ranked list of sets of two patterns each of length 4
according to the number of permutations that they avoid, followed by the first
40 terms of the (called P42 in the file)
If you want to see a ranked list of sets of three patterns each of length 4
according to the number of permutations that they avoid, followed by the first
40 terms of the (called P43 in the file)
If you want to see a ranked list of single patterns of length 5
according to the number of permutations that they avoid, followed by the first
30 terms of the (called P51 in the file)
If you want to see a ranked list of sets of two patterns each of length 5
according to the number of permutations that they avoid, followed by the first
30 terms of the (called P52 in the file)
If you want to see the theorem that produces the system of functional equations
for the weight-enumeration according to pattern pf length 2,
If you want to see the theorem that produces the system of functional equations
for the weight-enumeration according to pattern pf length 3,
If you want to see the theorem that produces the system of functional equations
for the weight-enumeration according to pattern pf length 4,
If you want to see the theorem that produces the system of functional equations
for the weight-enumeration of permutations avoiding the consecutive pattern [1,2,3]
If you want to see the theorem that produces the system of functional equations
for the weight-enumeration of permutations avoiding the consecutive patterns [1,2,3] and [1,3,2],
If you want to see the theorem that produces the system of functional equations
for the weight-enumeration of permutations avoiding the consecutive patterns [1,2,3,4] and [1,3,2,4],
.pdf
.ps
.tex
[Appeared in "Advances in Combinatorics: Waterloo Workshop in Computer Algebra, W80, May 26-29, 2011",
(edited by Ilias Kotsireas and Eugene Zima), 121-138].
Written: Jan. 20, 2011.
To W from Z (et. al.), a gift for his (2/3)|S5|-th birthday
This article, describes two complementary approaches to enumeration, the positive and
the negative, each with its advantages and disadvantages. Both approaches are amenable
to automation, and when applied to the currently active subarea, initiated in 2003 by
Sergi Elizalde and Marc Noy, of enumerating consecutive-Wilf classes
(i.e. consecutive pattern-avoidance )in permutations, were successfully
pursued by DZ's two current PhD students, Andrew Baxter and Brian Nakamura.
The Maple packages
SERGI
and ELIZALDE,
implementing the algorithms enable the computer to "do research" by
deriving, "all by itself", functional equations for the generating functions
that enable polynomial-time enumeration for any set of patterns.
In the case of ELIZALDE (the "negative" approach), these functional equations can be
sometimes (automatically!) simplified, and imply "explicit" formulas, that
previously were derived by humans using ad-hoc methods. We also get lots of
new "explicit" results, beyond the scope of humans, but we have to admit, that we still
need humans to handle "infinite families" of patterns, but this too, no doubt will
soon be automatable, and we leave it as a challenge to the (human and/or computer) reader.
Maple Packages
Important: This article is accompanied by Maple
packages
Sample Input and Output for the Maple package ELIZALDE: Number-Crunching
the input
gives the output.
the input
gives the output.
the input
gives the output.
the input
gives the output.
Sample Input and Output for the Maple package ELIZALDE: Automatic Generation of Theorems and Proofs
the input
gives the output.
the input
gives the output.
the input
gives the output.
the input
gives the output.
[As you can see most of these theorems become very complicated for human eyes].
the input
gives the output.
the input
gives the output.
the input
gives the output.
Sample Input and Output for the Maple package SERGI: Number Crunching
the input
gives the output.
the input
gives the output.
the input
gives the output.
the input
gives the output.
the input
gives the output.
the input
gives the output.
the input
gives the output.
the input
gives the output.
the input
gives the output.
the input
gives the output.
the input
gives the output
Sample Input and Output for the Maple package SERGI: Auotomatic Generation of Theorems
the input
gives the output
the input
gives the output
the input
gives the output
the input
gives the output
the input
gives the output
the input
gives the output
Doron Zeilberger's List of Papers