%posneg.tex:
%Positive and Negative (Automated!) Thinking in Enumerating Permutations Avoiding 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
{
Positive and Negative (Automated!) Thinking in Enumerating Permutations Avoiding Consecutive Patterns 
}
\centerline
{
(According to Andrew Baxter and Brian Nakamura [and implemented by S.B. Ekhad]) 
}
\rm
\bigskip
\centerline{ {\it
By 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 zeilberg@math.rutgers.edu} ,
{\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:
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/posneg.html} \quad ,
\hfill \break
where  the reader can find lots of sample input and output.
Supported in part by the United States of America National Science Foundation.
\hfill \break 
Exclusively published in the Personal Journal of S.B. Ekhad and Doron Zeilberger
\hfill \break 
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/pj.html}
and {\eighttt arxiv.org}.
}
}


{\bf Preface}  

This expository article, describes two complementary approaches to enumeration, the {\it positive}
and the {\it negative}, each with its advantages and disadvantages. Both approaches are amenable
to {\it automation}, and when applied to the currently active subarea, initiated in 2003 by
Sergi Elizalde, of {\it consecutive pattern-avoidance} in permutations, were successfully
pursued by my two current PhD students, Andrew Baxter[B] and Brian Nakamura[N]. In addition to
briefly explaining what they did, I also, as an independent check, developed two Maple
packages, {\tt SERGI} and {\tt ELIZALDE}
implementing the algorithms that 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 I leave it as a challenge to the (human and/or computer) reader.

{\bf Consecutive Pattern Avoidance}

Inspired by the very active research in pattern-avoidance, pioneered by Herb Wilf, Rodica Simion,
Frank Schmidt, Richard Stanely, Don Knuth and others, Sergi Elizalde, in his PhD thesis (written under the
direction of Richard Stanley)
introduced the study of permutations avoiding consecutive patterns.

Recall that an $n$-{\it permutation} is a  sequence of integers $\pi=\pi_1 \dots \pi_n$ 
of length $n$ where each integer in $\{1, \dots , n\}$ appears exactly once.
It is well-known and very easy to see (today!) that the number of $n$-permutations is $n!:= \prod_{i=1}^{n} i \quad $.

The {\it reduction} of a list of different (integer or real) numbers (or members of any totally ordered set) $[i_1, i_2, \dots, i_k]$,
to be denoted by $R([i_1, i_2, \dots, i_k])$, is the permutation of $\{1,2, \dots, k \}$ that preserves the relative rankings of the entries.
In other words, if $p=p_1 \dots p_k$ is the reduction of $q=q_1 \dots q_k$ then $q_i$ is the $p_i$-th largest entry in $q$.
For example the reduction of $[4,2,7,5]$ is $[2,1,4,3]$ and the reduction of $[\pi, e, \gamma, \phi]$ is $[4,3,1,2]$.

Fixing a pattern $p=[p_1, \dots , p_k]$, a permutation $\pi=[\pi_1, \dots , \pi_n]$ {\it avoids} the consecutive pattern
$p$ if for  all $i$, $1 \leq i \leq n-k+1$, the reduction of the list $[\pi_i,\pi_{i+1}, \dots, \pi_{i+k-1}$ is {\it not} $p$.
More generally a permutation $\pi$ avoids a set of patterns $\P$ if it avoids each and
every pattern $p \in \P$.

The central problem is to answer the question: ``Given a pattern or a set of patterns, find a ``formula'',
or at least an efficient algorithm, that inputs a positive integer $n$ and outputs the number of
permutations of length $n$ that avoid that pattern (or set of patterns)''.

{\bf Human Research}

After the pioneering work of Elizalde and Noy [EN], quite a few people contributed significantly,
including
Anders Claesson, Toufik Mansour,  Sergey Kitaev, Anthony Mendes, Jeff Remmel,
and the more recently, Vladimir Dotsenko and Anton Khoroshkin and Boris Shapiro.
Also recently we witnessed the beautiful resolution of the Warlimont conjecture by
Richard Ehrenborg, Sergey Kitaev, and Peter Perry [EKP].
The latter paper also contains extensive references.

{\bf Recommended Reading}

While the present expository article is self-contained, the readers would get more out of  it if
they are familiar with [Z1], and its sequels [EZ][Z1][Z2][Z3][Z4].


{\bf Outline of the Positive Approach (according to Andrew Baxter[B])}

Instead of dealing with {\it avoidance} (the number of permutations that have zero occurrences of the given pattern(s))
we will deal with the more general problem of enumerating the number of permutations that have specified numbers
of occurrences  of {\it any} pattern of length $k$.

Fix a positive integer $k$, and let $\{ t_p: p \in S_k\}$ be $k!$ {\it commuting indeterminates} (alias variables).
Define the {\it weight} of an $n$-permutation $\pi=[\pi_1, \dots, \pi_n]$, to be denoted by $w(\pi)$, by:
$$
w([\pi_1, \dots , \pi_n] :=
\prod_{i=1}^{n-k+1} t_{R([p_i,p_{i+1}, \dots, p_{i+k-1}])} \quad .
$$
For example, with $k=3$,
$$
w([2,5,1,4,6,3] :=
t_{R([2,5,1])}t_{R([5,1,4])}t_{R([1,4,6])}t_{R([4,6,3])}=
$$
$$
t-{231}t_{312}t_{123}t_{231}=t_{123}t_{231}^2t_{312} \quad .
$$
We are interested in an {\it efficient} algorithm for computing  the sequenec of polynomials
in $k!$ variables
$$
P_n(t_{1, \dots, k}, \dots, t_{k, \dots , 1 }):=
\sum_{\pi \in S_n} w(\pi) \quad ,
$$
or equivalently, as many terms as desired in the formal power series
$$
F_k(t_{1, \dots, k}, \dots, t_{k, \dots , 1 };z)=
\sum_{n=0}^{\infty} P_n z^n \quad .
$$

Note that once we have computed the $P_n$ (or $F_k$), we can answer {\it any} question about pattern avoidance
by specializing the $t$'s. For example  to get the number of $n$-permutations avoiding the single pattern
$p$, of length $k$, first compute $P_n$, and then plug-in $t_p=0$ and all the other t's to be 1.
If you want the number of $n$-permutations avoiding the set of patterns $\P$ (all of the same length $k$),
set $t_p=0$ for all $p \in \P$ and the other t's to be $1$. Another advantage of the
$P_n(t_p)$'s is that we can extract {\it statistical information}, averages, variance, and higher moments
of the random variable(s) ``number of occurrences of the consectutive pattern(s) $p$ ($\P$))'' by
differentiating with respect to the relevant $t_p$'s and plugging-in $1$ latter, but we will not
pursue this option here.



First let's recall one of the many proofs that the number of $n$-permutations, let's denote it by $a(n)$, satisfies
the recurrence
$$
a(n+1)=(n+1)a(n) \quad .
$$
Given a typical member of $S_n$, let's call it $\pi=\pi_1 \dots \pi_n$, it can  be continued in $n+1$ ways, by
deciding on $\pi_{n+1}$. If $\pi_{n+1}=i$, then we have to ``make room'' for the new entry by incrementing
by $1$ all entries $\geq i$, and then append $i$. This gives a bijection between
$S_n \times [1,n+1]$ and $S_{n+1}$ and taking cardinalities yields the recurrence. Of course $a(0)=1$,
and ``solving'' this recurrence yields $a(n)=n!$. Of course this solving is ``cheating'', since
$n!$ is just shorthand for the solution of this recurrence subject to the initial condition $a(0)=1$, but
from now on it is considered ``closed form'' (just by convention!).


When we do {\it weighted counting} with respect to the weight $w$ with a given pattern-length $k$,
we have to keep track of the last $k-1$ entries of $\pi$:
$$
[\pi_{n-k+2} \dots \pi_{n}] \quad
$$
and when we append $\pi_{n+1}=i$, the new permutation
(let $a'=a$ if $a<i$ and $a'=a+1$ if $a \geq i$)
$$
\dots \pi_{n-k+2}' \dots \pi_{n}' i \quad ,
$$
has ``gained'' a factor  of $t_{R[\pi_{n-k+2}' \dots \pi_{n}' i]}$ to its weight.

This calls for the finite-state method, alas, the ``alphabet'' is indefinitely large, so we need
the umbral transfer-matrix method.

We introduce $k-1$ ``catalytic'' variables $x_1, x_2, \dots , x_{k-1}$, as well as a variable $z$
to keep track of the size of the permutation,
and $(k-1)!$ ``linear'' state variables $A[q]$ for each $q \in S_{k-1}$, to tell us
the state that the permutation is in.
and define the
generailzed weight $w'(\pi)$ of a permutation $\pi \in S_n$ to be:
$$
w'(\pi):=w(\pi) x_1^{j_1} x_2^{j_2} \dots x_{k-1}^{j_{k-1}} z^nA[q]\quad,
$$
where $[j_1, \dots , j_{k-1}]$, $(1 \leq j_1 < j_2 < \dots < j_{k-1} \leq n)$ is the {\it sorted}
list of the last $k-1$ entries of $\pi$, and $q$ is the reduction of its last $k-1$ entries.

For example, with $k=3$:
$$
w'([4,7,1,6,3,5,8,2])=
t_{231}t_{312}t_{132}t_{312}t_{123}t_{231}x_1^2x_2^8z^8A[21]=
$$
$$
t_{123}t_{132}t_{231}^2t_{312}^2x_1^2x_2^8 z^8 A[21]\quad .
$$

Let's give an example with $k=3$. There are two states: $[1,2],[2,1]$ corresponding
to the cases where the two last entries are $j_1 j_2$ or $j_2 j_1$ respectively (always
we assume $j_1<j_2$.

Suppose we are in state $[1,2]$, so our permutation looks like

$$
\pi= [ \dots , j_1 , j_2 ]\quad ,
$$
and $w'(\pi)= w(\pi)x_1^{j_1} x_2^{j_2}z^nA[1,2]$.
We want to append $i$ ($1 \leq i \leq n+1)$ to the end. There are three cases:

{\bf Case 1}: $1 \leq i \leq j_1$

The new permutation, let's call it $\sigma$, looks like
$$
\sigma= [ \dots j_1+1 , j_2+1 , i] \quad .
$$
Its state is $[2,1]$ and 
$w'(\sigma)=w(\pi)t_{231}x_1^{i}x_2^{j_2+1}zA[2,1]$.



{\bf Case 2}: $j_1+1 \leq i \leq j_2$

The new permutation, let's call it $\sigma$, looks like
$$
\sigma= [ \dots j_1 , j_2+1 , i] \quad .
$$
Its state is also $[2,1]$ and $w'(\sigma)=w(\pi)t_{132}x_1^{i}x_2^{j_2+1}zA[2,1]$.




{\bf Case 3}: $j_2+1 \leq i \leq n+1$

The new permutation, let's call it $\sigma$, looks like
$$
\sigma= [ \dots j_1 , j_2 , i] \quad .
$$
Its state is now $[1,2]$ and $w'(\sigma)=w(\pi)t_{123}x_1^{j_2}x_2^{i}zA[1,2]$.

It follows that any {\it individual} permutation of size $n$, and state $[1,2]$, gives rise to
$n+1$ children, and regarding weight, we have the ``umbral evolution'' (here $W$ is the fixed part of the
weight, that does not change):
$$
Wx_1^{j_1} x_2^{j_2} z^n A[1,2]
\rightarrow
Wt_{231} zA[2,1] \left ( \sum_{i=1}^{j_1}   x_1^i x_2^{j_2+1} \right ) z^n
$$
$$
+
W t_{132} zA[2,1] \left ( \sum_{i=j_1+1}^{j_2}   x_1^i x_2^{j_2+1} \right )  z^n
$$
$$
+
W t_{123} zA[1,2]  \left ( \sum_{i=j_2+1}^{n+1}   x_1^{j_2} x_2^{i} \right ) z^n
$$
Taking out whatever we can out of the $\sum$-signs, we have:
$$
Wx_1^{j_1} x_2^{j_2} z^n A[1,2]
\rightarrow
Wt_{231} zA[2,1] \left ( \sum_{i=1}^{j_1}   x_1^i  \right ) x_2^{j_2+1} z^n
$$
$$
+
W t_{132} zA[2,1] \left ( \sum_{i=j_1+1}^{j_2}   x_1^i  \right ) x_2^{j_2+1} z^n
$$
$$
+
W t_{123} zA[1,2]  \left ( \sum_{i=j_2+1}^{n+1}    x_2^{i} \right ) x_1^{j_2} z^n
$$

Now summing up the geometrical series, using the ancient formula:
$$
\sum_{i=a}^{b} Z^i =\frac{Z^a-Z^{b+1}}{1-Z} \quad ,
$$
we get
$$
Wx_1^{j_1} x_2^{j_2} z^n A[1,2]
\rightarrow
Wt_{231} zA[2,1] \left ( \frac{x_1-x_1^{j_1+1}}{1-x_1} \right ) x_2^{j_2+1} z^n
$$
$$
+
W t_{132} zA[2,1] \left ( \frac{x_1^{j_1+1}-x_1^{j_2+1}}{1-x_1} \right ) x_2^{j_2+1} z^n
$$
$$
+
W t_{123} zA[1,2]  \left ( \frac{x_2^{j_2+1}-x_2^{n+2}}{1-x_2} \right ) x_1^{j_2} z^n
$$
This is the same as:
$$
Wx_1^{j_1} x_2^{j_2} z^n A[1,2]
\rightarrow
Wt_{231} zA[2,1] \left ( \frac{x_1 x_2^{j_2+1} -x_1^{j_1+1}x_2^{j_2+1}}{1-x_1} \right ) z^n
$$
$$
+
W t_{132} zA[2,1] \left ( \frac{x_1^{j_1+1}x_2^{j_2+1}-x_1^{j_2+1}x_2^{j_2+1}}{1-x_1} \right ) z^n
$$
$$
+
W t_{123} zA[1,2]  \left ( \frac{x_1^{j_2} x_2^{j_2+1}-x_1^{j_2} x_2^{n+2}}{1-x_2} \right ) z^n
$$
This is what I called in [Z1] and its many sequels a ``pre-umbra''. The above evolution
can be expressed for a general {\it monomial} $M(x_1,x_2,z)$ as:
$$
M(x_1,x_2,z)A[1,2]
\rightarrow
t_{231} zA[2,1] \left ( \frac{x_1 x_2 M(1,x_2,z) -x_1x_2M(x_1,x_2,z)}{1-x_1} \right ) 
$$
$$
+
 t_{132} zA[2,1] \left ( \frac{x_1x_2M(x_1,x_2,z)-x_1x_2M(1,x_1x_2,z)}{1-x_1} \right ) 
$$
$$
+
 t_{123} zA[1,2]  \left ( \frac{x_2M(1,x_1x_2,z)-x_2^{2}M(1,x_1,x_2,z}{1-x_2} \right )  \quad .
$$
But by {\it linearity} this means that the coeff. of A[1,2] (the weight-enumerator of all permutations of
state $[1,2]$ obeys the evolution equation:
$$
f_{12}(x_1,x_2,z)A[1,2]
\rightarrow
t_{231} zA[2,1] \left ( \frac{x_1 x_2 f_{12}(1,x_2,z) -x_1x_2f_{12}(x_1,x_2,z)}{1-x_1} \right ) 
$$
$$
+
 t_{132} zA[2,1] \left ( \frac{x_1x_2f_{12}(x_1,x_2,z)-x_1x_2f_{12}(1,x_1x_2,z)}{1-x_1} \right ) 
$$
$$
+
 t_{123} zA[1,2]  \left ( \frac{x_2f_{12}(1,x_1x_2,z)-x_2^{2}f_{12}(1,x_1,x_2z)}{1-x_2} \right )  \quad .
$$



%%%%%%%%%%%begin be edited 12->21
Now we have to do it all over for a permutation in state $[2,1]$.
Suppose we are in state $[2,1]$, so our permutation looks like
$$
\pi= [ \dots , j_2 , j_1 ]\quad ,
$$
and $w'(\pi)= w(\pi)x_1^{j_1} x_2^{j_2}z^nA[2,1]$.
We want to append $i$ ($1 \leq i \leq n+1)$ to the end. There are three cases:

{\bf Case 1}: $1 \leq i \leq j_1$

The new permutation, let's call it $\sigma$, looks like
$$
\sigma= [ \dots j_2+1 , j_1+1 , i] \quad .
$$
Its state is $[2,1]$ and 
$w'(\sigma)=w(\pi)t_{321}x_1^{i}x_2^{j_1+1}zA[2,1]$.



{\bf Case 2}: $j_1+1 \leq i \leq j_2$

The new permutation, let's call it $\sigma$, looks like
$$
\sigma= [ \dots j_2+1 , j_1 , i] \quad .
$$
Its state is also $[1,2]$ and $w'(\sigma)=w(\pi)t_{312}x_1^{j_1}x_2^{i}zA[2,1]$.




{\bf Case 3}: $j_2+1 \leq i \leq n+1$

The new permutation, let's call it $\sigma$, looks like
$$
\sigma= [ \dots j_2 , j_1 , i] \quad .
$$
Its state is now $[1,2]$ and $w'(\sigma)=w(\pi)t_{213}x_1^{j_1}x_2^{i}zA[1,2]$.

It follows that any {\it individual} permutation of size $n$, and state $[2,1]$, gives rise to
$n+1$ children, and regarding weight, we have the ``umbral evolution'' (here $W$ is the fixed part of the
weight, that does not change):
$$
Wx_1^{j_1} x_2^{j_2} z^n A[2,1]
\rightarrow
Wt_{321} zA[2,1] \left ( \sum_{i=1}^{j_1}   x_1^i x_2^{j_1+1} \right ) z^n
$$
$$
+
W t_{312} zA[1,2] \left ( \sum_{i=j_1+1}^{j_2}   x_1^{j_1} x_2^{i} \right )  z^n
$$
$$
+
W t_{213} zA[1,2]  \left ( \sum_{i=j_2+1}^{n+1}   x_1^{j_1} x_2^{i} \right ) z^n
$$

Taking out whatever we can out of the $\sum$-signs, we have:
$$
Wx_1^{j_1} x_2^{j_2} z^n A[2,1]
\rightarrow
Wt_{321} zA[2,1] \left ( \sum_{i=1}^{j_1}   x_1^i  \right )  x_2^{j_1+1} z^n
$$
$$
+
W t_{312} zA[1,2] \left ( \sum_{i=j_1+1}^{j_2}    x_2^{i} \right ) x_1^{j_1} z^n
$$
$$
+
W t_{213} zA[1,2]  \left ( \sum_{i=j_2+1}^{n+1}    x_2^{i} \right ) x_1^{j_1} z^n \quad .
$$
Now summing up the geometrical series, using the ancient formula:
$$
\sum_{i=a}^{b} Z^i =\frac{Z^a-Z^{b+1}}{1-Z} \quad ,
$$
we get
$$
Wx_1^{j_1} x_2^{j_2} z^n A[2,1]
\rightarrow
Wt_{321} zA[2,1] \left ( \frac{x_1-x_1^{j_1+1}}{1-x_1} \right ) x_2^{j_1+1} z^n
$$
$$
+
W t_{312} zA[1,2] \left ( \frac{x_2^{j_1+1}-x_2^{j_2+1}}{1-x_2} \right ) x_1^{j_1} z^n
$$
$$
+
W t_{213} zA[1,2]  \left ( \frac{x_2^{j_2+1}-x_2^{n+2}}{1-x_2} \right ) x_1^{j_1} z^n
$$
This is the same as:
$$
Wx_1^{j_1} x_2^{j_2} z^n A[2,1]
\rightarrow
Wt_{321} zA[2,1] \left ( \frac{x_1 x_2^{j_1+1} -x_1^{j_1+1}x_2^{j_1+1}}{1-x_1} \right ) z^n
$$
$$
+
W t_{312} zA[1,2] \left ( \frac{x_1^{j_1}x_2^{j_1+1}-x_1^{j_1}x_2^{j_2+1}}{1-x_2} \right ) z^n
$$
$$
+
W t_{213} zA[1,2]  \left ( \frac{x_1^{j_1} x_2^{j_2+1}-x_1^{j_1} x_2^{n+2}}{1-x_2} \right ) z^n
$$
The above evolution
can be expressed for a general {\it monomial} $M(x_1,x_2,z)$ as:
$$
M(x_1,x_2,z)A[2,1]
\rightarrow
t_{321} zA[2,1] \left ( \frac{x_1 x_2 M(x_2,1,z) -x_1x_2M(x_1x_2,1,z)}{1-x_1} \right ) 
$$
$$
+
 t_{312} zA[1,2] \left ( \frac{x_2M(x_1x_2,1,z)-x_2M(x_1,x_2,z)}{1-x_2} \right ) 
$$
$$
+
 t_{213} zA[1,2]  \left ( \frac{x_2M(x_1,x_2,z)-x_2^{2}M(x_1,1,x_2z}{1-x_2} \right )  \quad .
$$
But by {\it linearity} this means that the coeff. of A[2,1] (the weight-enumerator of all permutations of
state $[2,1]$ obeys the evolution equation:
$$
f_{21}(x_1,x_2,z)A[2,1]
\rightarrow
t_{321} zA[2,1] \left ( \frac{x_1 x_2 f_{21}(x_2,1,z) -x_1x_2f_{21}(x_1x_2,1,z)}{1-x_1} \right ) 
$$
$$
+
t_{312} zA[1,2] \left ( \frac{x_2f_{21}(x_1x_2,1,z)-x_2f_{21}(x_1,x_2,z)}{1-x_2} \right ) 
$$
$$
+
t_{213} zA[1,2]  \left ( \frac{x_2f_{21}(x_1,x_2,z)-x_2^{2}f_{21}(x_1,1,x_2z)}{1-x_2} \right )  \quad .
$$
Combining we have the ``evolution'':
$$
f_{12}(x_1,x_2,z)A[1,2]+ f_{21}(x_1,x_2,z)A[2,1] \rightarrow
$$
$$
t_{231} zA[2,1] \left ( \frac{x_1 x_2 f_{12}(1,x_2,z) -x_1x_2f_{12}(x_1,x_2,z)}{1-x_1} \right ) 
$$
$$
+ t_{132} zA[2,1] \left ( \frac{x_1x_2f_{12}(x_1,x_2,z)-x_1x_2f_{12}(1,x_1x_2,z)}{1-x_1} \right ) 
$$
$$
+
 t_{123} zA[1,2]  \left ( \frac{x_2f_{12}(1,x_1x_2,z)-x_2^{2}f_{12}(1,x_1,x_2z)}{1-x_2} \right )  \quad .
$$
$$
+t_{321} zA[2,1] \left ( \frac{x_1 x_2 f_{21}(x_2,1,z) -x_1x_2f_{21}(x_1x_2,1,z)}{1-x_1} \right ) 
$$
$$
+ t_{312} zA[1,2] \left ( \frac{x_2f_{21}(x_1x_2,1,z)-x_2f_{21}(x_1,x_2,z)}{1-x_2} \right ) 
$$
$$
+ t_{213} zA[1,2]  \left ( \frac{x_2f_{21}(x_1,x_2,z)-x_2^{2}f_{21}(x_1,1,x_2z)}{1-x_2} \right )  \quad .
$$
Now the ``evolved'' (new) $f_{12}(x_1,x_2,z)$ and $f_{21}(x_1,x_2,z)$ are the coeff. of $A[1,2]$, $A[2,1]$
respectively, and since the ``initial weight of both'' of them is $x_1x^2z^2$, we have the
established the following system of functional equations:
$$
f_{12}(x_1,x_2,z)=x_1x_2^2z^2+
$$
$$
t_{123} z \left ( \frac{x_2f_{12}(1,x_1x_2,z)-x_2^{2}f_{12}(1,x_1,x_2z)}{1-x_2} \right ) +
$$
$$
+ t_{312} z\left ( \frac{x_2f_{21}(x_1x_2,1,z)-x_2f_{21}(x_1,x_2,z)}{1-x_2} \right ) 
$$
$$
+ t_{213} z  \left ( \frac{x_2f_{21}(x_1,x_2,z)-x_2^{2}f_{21}(x_1,1,x_2z)}{1-x_2} \right )  \quad ,
$$
and
$$
f_{21}(x_1,x_2,z)=x_1x_2^2z^2+
$$
$$
t_{231} z \left ( \frac{x_1 x_2 f_{12}(1,x_2,z) -x_1x_2f_{12}(x_1,x_2,z)}{1-x_1} \right ) 
$$
$$
+ t_{132} z \left ( \frac{x_1x_2f_{12}(x_1,x_2,z)-x_1x_2f_{12}(1,x_1x_2,z)}{1-x_1} \right ) 
$$
$$
+t_{321} z \left ( \frac{x_1 x_2 f_{21}(x_2,1,z) -x_1x_2f_{21}(x_1x_2,1,z)}{1-x_1} \right )  \quad .
$$

{\bf Let the computer do it!}

All the above was only done for {\it pedagogical} reasons. The computer can do it all auomatically, much
faster and more reliably. Now of we want to find functional equations for the number of
permumations avoiding a given set of consecutive patterns $\P$, all we have to do is plug-in
$t_p=0$ for $p in \P$ and $t_p=1$ for $p \not \in \P$. This gives a polynomial-time algorithm
for computing any desired number of terms. This is all done automatically in the
Maple package {\tt SERGI}. See the webpage of this article for lots of sample input and output.


{\bf Outline of the Negative Approach (According to Brian Nakamura)}

Suppose that we want to compute fast the first $100$ terms (or whatever) of the sequence enumerating
$n$-permutations avoiding the pattern $1 2 \dots 20$. Using the ``positive'' approach, we would need to
set-up a system of functional equations with $19!$ power-series! While the algorithm is still
{\it polynomial} in $n$, it is not very practical! (This is yet another illustation why the
ruling paradigm in theoretical computer science, of equating ``polynomial time'' with ``fast'' is absurd).

This is analogous to computing words in a {\it finite} alphabet, say of $a$ letters,
avoiding a given word (or words) as
{\it factors} (consecutive subwords). If the word-to-avoid has length $k$, then the naive transfer-matrix
method would require to set-up a system of $a^{k-1}$ equations and  $a^{k-1}$ unknowns.
The elegant and powerful {\it Goulden-Jackson method} [GJ1][GJ2], beautifully exposited and extended in
[NZ], and even further extended in [KY] enables to do it with just solving one equation and
one unknown. We assume that the reader is familiar with it, and briefly describe the
analog for the present problem, where the alphabet is ``infinite''. This is also the approach
pursued in the beautiful human-generated papers [DK] and [KS]. I repeat that the {\it focus} and
{\it novelty} in the present work of my students (and most of my work in at least the last ten years)
is in {\it automating} enumeration (and the rest of mathematics), and the current topic of
consecutive pattern-avoidance is used as a {\it case-study}.

One again, in order to illustate the method.
I will use two specific, simple examples, (the patterns $321$ and $231$ already considered, using human
ingenuity, in the pioneering paper [EN].)
The general algorithm, written
in Maple, is contained in the Maple package {\it ELIZALDE}. Out of laziness, so far, I only treat 
single patterns, but Brian Nakaumra's [N] work  deals with the general case.

But first generalities. For the sake of exposition, focusing on a single pattern $p$
(the case of several patterns is analogous, see [DK]).

Using the inclusion-exclusion ``negative'' philosophy for counting,
Fix a pattern $p$. For any $n$-permutation, let $Patt_p(\pi)$ be the set
of occurrences of the pattern $p$ in $\pi$. For example
$$
Patt_{123} (179234568)=\{ 179, 234,345,456,568\} \quad ,
$$
$$
Patt_{231} (179234568)=\{ 792\} \quad ,
$$
$$
Patt_{312} (179234568)=\{ 923\} \quad ,
$$
$$
Patt_{132}=Patt_{213}=Patt_{321}= \emptyset \quad .
$$


consider the much larger set of pairs
$$
\{ (\pi, S) | S \quad is \quad a \quad a \quad subset \quad of \quad Patt_p(\pi) \}
$$
set of {\it all} permutations of length $n$, and define a  new weight
$weight(\pi):=(t-1)^{\# occurrences of the pattern p}$. For example, the








{\bf References}

[B] Andrew Baxter, {\it in preparation}.

[DK] V. Dotsenko and A. Khoroshkin, {\it Anick-type resolutions and consecutive pattern-avoidance},
arXiv:1002.2761v1[Math.CO]

[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] Sergi Elizalde and Marc 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.

[GJ1] I. Goulden  and D.M. Jackson,
{\it An inversion theorem for cluster decompositions of
sequences with distinguished subsequences},
J. London Math. Soc.(2){\bf 20} (1979), 567-576.
 
[GJ2] I. Goulden  and D.M. Jackson,
{\it "Combinatorial Enumeration"}, John  Wiley, 1983, New York.

[KS] Anton Khoroshkin and  Boris Shapiro, {\it Using homological duality in consecutive pattern avoidance},
arXiv:1009.5308v1 [math.CO].


[KY]  Elizabeth J. Kupin, Debbie S. Yuster,
{\it Generalizations of the Goulden-Jackson Cluster Method}, J. Difference Eq. Appl. {\bf 16} (2010), 1563-5120.
(Also avialable  in arXiv:0810.5113v1[math.CO].)

[N] Brian Nakamura, {\it in preparation}.

[NZ] John Noonan and Doron Zeilberger,
{\it The Goulden-Jackson Cluster Method: Extensions, Applications, and Implementations},
J. Difference Eq. Appl. {\bf 5} (1999), 355-377.

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

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

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

[Z4] Doron 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








 
 

