%agt.tex:
%Automatic Generation of Theorems and Proofs on Enumerating Permutations that  Avoid Consecutive Patterns

%%a Plain TeX file by Doron Zeilberger (x pages)

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
AUTOMATIC GENERATION of THEOREMS and PROOFS On {\sixrm Enumerating Permutations that  Avoid Consecutive Patterns}
}
\rm
\bigskip
\centerline{ {\it
Brian NAKAMURA and
Doron 
ZEILBERGER}\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt [bnaka, zeilberg]  at math dot rutgers dot edu} ,
\hfill \break
{\eighttt http://www.math.rutgers.edu/\~{}bnaka/} , {\eighttt http://www.math.rutgers.edu/\~{}zeilberg/}  .
First version: Jan. 1, 2011.
Accompanied by Maple packages {\eighttt ELIZALDE} and {\eighttt SERGI}
downloadable from the webpage of this article:
\hfill \break
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/agt.html},
\hfill \break
where  the reader can find lots of sample input and output.
\hfill \break 
The second author was supported in part by the NSF.
\hfill \break 
Exclusively published in the Personal Journal of S.B. Ekhad and Doron Zeilberger
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/pj.html}
and {\eighttt arxiv.org}.
}
}

{\bf Preface}

The present article is a {\it case study} in automated generation of theorems and proofs in mathematics,
and its main goal is to present {\it by example} a research methodology, extensively pursued by
Zeilberger and his students, of ``teaching'' the computer to do research in mathematics.
Hence, we will focus on the {\it meta}-level and expect the reader to look up,
for human approaches,
the pioneering work of Elizalde and Noy [EN], and the subsequent exciting work of, 
Anders Claesson, Toufik Mansour,  Sergey Kitaev, Anthony Mendes, Jeff Remmel,
and the more recent work of Vladimir Dotsenko and Anton Khoroshkin and
Boris Shapiro, and the beautiful resolution of the Warlimont conjecture by
Richard Ehrenborg, Sergey Kitaev, and Peter Perry [EKP].
This paper also contains extensive references.
We will also assume that the reader is familiar with Zeilberger's Umbral Transfer Matrix method
[Z1]. See [EZ][Z1][Z2][Z3][Z4] for previous, computer-generated, appilcations.





The present {\it article}, and especially the accompanying Maple package {\tt ELIZALDE} downloadable


{\bf References}

[EKP] Richard Ehrenborg, Sergey Kitaev, and Peter Perry,
{\it A Spectral Approach to Consecutive Pattern-Avoiding Permutations},
arXiv: 1009.2119v1 [math.CO] 10 Sep 2010

[EN] S. Elizalde and M. Noy, {\it Consecutive patterns in permutations}, Advances in Applied Mathematics {\bf 30} (2003), 110-125.

[EZ] Shalosh B. Ekhad, and D. Zeilberger,
{\it Using Rota's Umbral Calculus to Enumerate Stanley's P-Partitions},
Advances in Applied Mathematics {\bf 41} (2008), 206-217.

[Z1] D. Zeilbeger,
{\it The Umbral Transfer-Matrix Method I. Foundations},
J. Comb. Theory, Ser. A {\bf 91} (2000), 451-463 .

[Z2] D. Zeilbeger,
{\it The Umbral Transfer-Matrix Method. III. Counting Animals}, 
 New Journal of Mathematics {\bf 7}(2001), 223-231 .

[Z3] D. Zeilbeger,
{\it The Umbral Transfer-Matrix Method V. The Goulden-Jackson Cluster Method for Infinitely Many Mistakes},
Integers {\bf 2} (2002), A5.

[Z4] D. Zeilbeger,
{\it In How Many Ways Can You Reassemble Several Russian Dolls?}, Personal Journal of S.B. Ekhad and
D. Zeilberger, 
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/pj.html}, Sept. 16, 2009.

\end






