%cpaw.tex: Consecutive Pattern-Avoidance in Words
%%a Plain TeX file by Shalosh B. Ekhad and 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
\centerline
{\bf  Consecutive Pattern-Avoidance in Words }
\bigskip
\centerline
{\it Mingjia Yang and Doron ZEILBERGER}

{\bf Abstract.} We use an extension of the celebrated Goulden-Jackson Cluster method, aided by symbolic computation,
to enumerate {\it words} avoiding a given set of consecutive patterns. Our approach also lends itself
to the enumeration of {\it permutations}, replicating, and giving a new approach to, results in this research area
pioneered, in 2003, by Sergi Elizalde and Marc Noy, but it also enables the efficient enumeration, for example,
of words in $1^s \dots n^s$, avoiding the consecutive pattern $1\dots r$, for {\it any} $s$, and {\it any} $r$. 
All the sequences for $s=1$, and $3 \leq r \leq 9$ are  in the On-Line Encyclopedia of Integer Sequences, with many
terms, using the explicit generating function of Elizalde and Noy.
Also, quite a few of theses sequences for $s>1$ are already there, but with very few terms.
Our implied algorithms are $O(n^s)$ and hence yield many more terms, and, of course, new sequences.
This article is accompanied by three Maple packages implementing our algorithms.


{\bf Introduction.} Rodica Simion and Herbert Wilf initiated the study of enumerating {\it classical} pattern-avoidance.
This is a very dynamic area with its own annual conference and Wikipedia page. 
Recall that 
a permutation $\pi=\pi_1 \dots \pi_n$ avoids a pattern $\sigma=\sigma_1 \dots \sigma_k$  if  none of the ${{n} \choose {k}}$ length-$k$ 
subsequence of  $\pi$, reduces to $\sigma$.

Alex Burstein([Bu]), in a 1998 PhD thesis, under the direction of Herb Wilf, pioneered the enumeration of
{\it words} avoiding a set of patterns. This field is also fairly active today, with notable contributions
by, {\it inter alia}, Toufik Mansour (e.g [BuM]), Lara Pudwell([P]).

The enumeration of permutations avoiding a given (classical) pattern, or a set of patterns, is notoriously difficult,
and it is widely believed to be intractable for most patterns, hence it would be nice to have other notions
for which the enumeration is more feasible. Such an analog was given, in 2003, by Sergi Elizalde
and Marc Noy, in a seminal paper ([EN]), that introduces the study of the enumeration of permutations
avoiding {\it consecutive} patterns. 
A permutation $\pi=\pi_1 \dots \pi_n$ avoids a pattern $\sigma=\sigma_1 \dots \sigma_k$  if  none of the $n-k+1$ length-$k$ 
{\it factors}, $\pi_i \pi_{i+1} \dots \pi_{i+k-1}$ of  $\pi$, reduces to $\sigma$.

Algorithmic approaches to the enumeration of {\it permutations} avoiding sets of consecutive patterns were given
by Brian Nakamura, Andrew Baxter, and Doron Zeilberger ([Na], [BaNaZ]). Our present approach 
may be viewed as an extension, from permutations to words, of Nakamura's paper, who was also inspired by
the Goulden-Jackson , but in a sense, is more straightforward, and closer in spirit to the original
Goulden-Jackson method ([GJ],that is beautifully exposited in [NZ]). 


{\bf Guessing General Generating Functions in $x_1, \dots, x_n$ (for arbitrary $n$) for Words avoiding a pattern (or set of patterns)}

Recall that the original Goulden-Jackson method ([GJ][NZ]) inputs a {\it finite} alphabet, $A$, 
that may be taken to be $\{1, ..., n\}$, and a finite set of `bad words', $B$.

It outputs a certain {\bf rational function}, let's call it $F(x_1, \dots, x_n)$, that is the multi-variable generating function,
in $x_1, \dots, x_n$,  for the discerte $n$-variable function
$$
G(m_1, \dots, m_n) \quad ,
$$
the counts the words in $1^{m_1} \dots n^{m_n}$ (there are totally $(m_1 + \dots + m_n)!/(m_1! \cdots m_n!)$ of them)
that {\bf never} contain, as {\it consecutive} subwords (aka {\it factors} in linguistics) any member of $B$.
In other words:
$$
F(x_1, \dots , x_n)= \sum_{(m_1, \dots, m_n) \in N^n}  G(m_1, \dots, m_n) \, x_1^{m_1} \cdots x_n^{m_n} \quad .
$$
This is nicely implemented in the Maple package {\tt DavidIan.txt}, that accompanies [NZ], and is freely available from

{\tt http://sites.math.rutgers.edu/~zeilberg/tokhniot/DavidIan.txt } \quad .



for example if $n=4$, so the alphabet if $\{1,2,3,4\}$ and the set of `bad words' to avoid is $\{1234,1432\}$, then,
starting a Maple session, and typing:

{\tt read `DavidIan.txt`: lprint(subs(t=0,GJgf({1,2,3,4},{[1,2,3,4],[1,4,3,2]},x,t)));}

immediately returns

{\tt 1/(1-x[1]-x[2]-x[3]-x[4]+ 2*x[1]*x[2]*x[3]*x[4])} \quad ,

that in Humanese reads
$$
\frac{1}{1-x_1-x_2-x_3-x_4 \, + \, 2\, x_1 x_2 x_3 x_4} \quad .
$$

{\bf Enumerating Words Avoiding Consecutive Patterns: Let the Computer Do the Guessing}

Now we are interested in words in an {\it arbitrarily large} alphabet $\{1, \dots n\}$ avoiding a set of patterns.
But each pattern, e.g. $123$, entails  {\it arbitrarily large} set of forbidden words, in this case the
${{n} \choose {3}}$ members of the set
$$
\{ i_1 \, i_2 \, i_3 \, |\, 1 \leq i_1 < i_2 < i_3 \leq n \} \quad .
$$
We can ask {\tt DavidIan.txt} to find the generating function for each specific $n$, and then hope to conjecture
a {\bf general} formula in terms of $x_1, \dots , x_n$.

This is accomplished by the Maple package {\tt GJpats.txt} available from the webpage of this article.
It used the original  {\tt DavidIan.txt} to produce the corresponding generating functions for increasing values for $n$.
For example for words avoiding the consecutive pattern $123$ for $n=3$

{\tt lprint(GFpats({[1,2,3]},x,3,0));} yields

{\tt 1/(x[1]*x[2]*x[3]-x[1]-x[2]-x[3]+1)} \quad .


This is simple enough. Moving right along

{\tt lprint(GFpats({[1,2,3]},x,4,0));} yields ,

{\tt 1/(x[1]*x[2]*x[3]*x[4]-x[1]*x[2]*x[3]-x[1]*x[2]*x[4]  \hfill\break
-x[1]*x[3]*x[4]-x[2]*x[3]*x[4]+x[1] + x[2]+x[3]+x[4]-1)}

while {\tt lprint(GFpats({[1,2,3]},x,4,0));} yields ,

{\tt
-1/(x[1]*x[2]*x[3]*x[4]+x[1]*x[2]*x[3]*x[5]+x[1]*x[2]*x[4]*x[5]+x[1]*x[3]*x[4]*x[5]  \hfill\break
+x[2]*x[3]*x[4]*x[5] -x[1]*x[2]*x[3]-x[1]*x[2]*x[4]-x[1]*x[2]*x[5]-x[1]*x[3]*x[4]- \hfill\break
x[1]*x[3]*x[5]-x[1]*x[4]*x[5]-x[2]*x[3]*x[4]-x[2]*x[3]*x[5]-x[2]*x[4]*x[5] \hfill\break
-x[3]*x[4]*x[5]+x[1]+x[2]+x[3]+x[4]+x[5]-1)
} \quad .

It looks like these are {\it symmetric} functions. Procedure {\tt  SPtoM(P,x,n,m)} expresses a polynomial, P, in the indexed variables
$x[1], \dots, x[n]$ in terms of the {\it monomial symmetric polynomials} $m_\lambda$. Applying this procedure we have

{\tt SPtoM(denom(GFpats({[1,2,3]},x,5,0)),x,5,m);} yields

{\tt  m[1, 1, 1, 1] - m[1, 1, 1] + m[1] - m[]} \quad ,

{\tt SPtoM(denom(GFpats({[1,2,3]},x,6,0)),x,6,m);} yields

{\tt m[1,1,1,1,1,1]-m[1,1,1,1]+m[1,1,1]-m[1]+m[]} 

{\tt SPtoM(denom(GFpats({[1,2,3]},x,7,0)),x,7,m);} yields

m[1,1,1,1,1,1,1]-m[1,1,1,1,1,1]+m[1,1,1,1]-m[1,1,1]+m[1]-m[]

Now you don't have to be a Ramanujan to conjecture the following Theorem

{\bf Fact} The generating function for words in $\{1, 2, \dots , n\}$ avoiding the consecutive pattern $123$, let's call it 
$F_3(x_1,\dots, x_n)$  is
$$
F_3(x_1, \dots , x_n) = \frac{1}{1-e_1+e_3-e_4+e_6-e_7+ e_9-e_{10}\dots } \quad ,
$$
where $e_i$ stands for the {\it elementary symmetric function}  of degree $i$ in $x_1, \dots, x_i$, i.e. the coefficient
of $z^i$ in $(1+x_1\,z)\dots (1_+ x_n\, z)$.

(Note that $e_i=m_{1^i}$).

Doing the analogous guessing for the consecutive patterns $1234$ and $12345$, a {\it meta-pattern} emerges, and we
are safe in formulating the following

{\bf Theorem} For $n \geq 1, r\geq 2$,
the generating function for words in $\{1, 2, \dots , n\}$ avoiding the consecutive pattern $12\dots r$, let's call it 
$F_r(x_1,\dots, x_n)$  is
$$
F_r(x_1, \dots , x_n) = \frac{1}{1-e_1+e_r-e_{r+1}+e_{2r}-e_{2r+1}+e_{3r}-e_{3r+1}+  \dots } \quad .
$$

Of course, so far, these are `only' guesses, but once we know them, the human can prove them, applying the cluster method to
a {\it general} alphabet. At this time of writing this still has to  be done by humans and will be given later.


{\bf Efficient Computations}

The Theorem immediately implies the following partial recurrence equation for the actual coefficients.

{\bf Fundamental Recurrence}: Let $f_r({\bf m})$ be the number of words in the alphabet $\{1, \dots , n \}$ with
$m_1$ $1$-s, $m_2$ $2$-s, \dots $m_n$ $n$-s (where we abbreviate ${\bf m}=(m_1, \dots, m_n)$). Also
let $V_i$ be the set of $0-1$ vectors of length $n$ with $i$ ones, then

$$
f_r({\bf m})= \sum_{ {\bf v} \in V_1} f({\bf m} - {\bf v}) \, - \,\sum_{ {\bf v} \in V_r} f({\bf m} - {\bf v}) 
$$
$$
+\sum_{ {\bf v} \in V_{r+1}} f({\bf m} - {\bf v}) \, - \,\sum_{ {\bf v} \in V_{2r}} f({\bf m} - {\bf v}) 
$$
$$
+\sum_{ {\bf v} \in V_{2r+1}} f({\bf m} - {\bf v}) \, - \,\sum_{ {\bf v} \in V_{3r}} f({\bf m} - {\bf v})  +\, \dots \quad  .
$$


Suppose that we want to compute $f_3(1^{100})$, i.e. the number of permutations of length $100$ that avoid the consecutive
pattern $123$. If we use the above recurrence literally, we would need about $2^{100}$ computations, but there is
a shortcut!

{\bf Enter Symmetry}

It follows from the generating function that $f_r(m_1, \dots, m_n)$ is symmetric, hence for any $0-1$ vector $v$
$f_r(v)$ only depends on the number of $1$'s. Hence the above fundamental recurrence implies the following

{\bf Fast Recurrence For Enumerating Permutations avoiding the consecutive pattern $1 \dots r$}: Let
$a_r(n)$ be the number of permutations of length $n$ that avoid the consecutive pattern $1\dots r$, then
$$
a_r(n)= n a_r(n-1) -{{n} \choose {r}} a_r(n-r) + {{n} \choose {r+1}} a_r(n-r-1) -{{n} \choose {2r}} a_r(n-2r) + {{n} \choose {2r+1}} a_r(n-2r-1)  
$$
$$
-{{n} \choose {3r}} a_r(n-3r)   +  {{n} \choose {3r+1}} a_r(n-3r-1)   + \dots \quad .
$$

This recurrence immediately implies the Elizalde-Noy exponential generating functions
$$
\sum_{n=0}^{\infty} a_r(n) \frac{x^n}{n!} \, = \,
\frac{1}{1-x+ \frac{x^r}{r!} - \frac{x^{r+1}}{(r+1)!} + \frac{x^{2r}}{(2r)!}   
-\frac{x^{2r+1}}{(2r+1)!}+ \frac{x^{3r}}{(3r)!} -  \frac{x^{3r+1}}/{3r+1)!} + \dots } \quad .
$$
While this `explicit' (exponential) generating function is `nice', it is more  efficient to use the fast recurrence. And
indeed, the OEIS has these sequences for $3 \leq 3 \leq 9$, with many terms (using the above recurrences, probably).
These are (in order): {\tt A049774, A117158, A177523, A177533, A177553, A230051, A230231}.

\bigskip

{\bf References}

[BaNZ]  Andrew Baxter, Brian Nakamura, and Doron Zeilberger, {\it Automatic Generation of Theorems and Proofs on Enumerating Consecutive-Wilf classes},
in: {\it "Advances in Combinatorics: Waterloo Workshop in Computer Algebra, W80, May 26-29, 2011"} [Volume in honor of Herbert S. Wilf], 
edited by Ilias Kotsireas and Eugene Zima, 121-138

[Bu] Alex Burstein, 
{\it "Enumeration of words with forbidden patterns"}, Ph.D. thesis, University of Pennsylvania, 1998.

[BuM] Alex Burstein and Toufik Mansour, {\it Words Restricted by Patterns with at Most 2 Distinct Letters},
The electronic journal of combinatorics 9(2) (2002), \#R3

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

[GJ] Ian Goulden and David Jackson, {\it An inversion theorem for cluster decomposition of sequences with distinguished 
subsequences},  J. London Math. Soc.(2) {\bf 20} (1979), 567-576.

[Na] Brian Nakamura, {\it Computational Approaches to Consecutive Pattern Avoidance in Permutations},
Pure Math. Appl. (PU.M.A.) {\bf 22}(2011), 253–268. \hfill\break
Also available from{\tt https://arxiv.org/abs/1102.2480}

[NoZ] John Noonan and Doron Zeilberger, {\it The Goulden-Jackson Cluster Method: Extensions, Applications, and Implementations},
J. Difference Eq. Appl. {\bf 5}(1999), 355-377.  \hfill\break
{\tt http://sites.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/gj.html} \quad .

[P] Lara Pudwell, {\it Enumeration schemes for pattern-avoiding words and permutations}, Rutgers University, May 2008, \hfill\break
{\tt http://faculty.valpo.edu/lpudwell/papers/pudwell\_thesis.pdf}

[Wi] The Wikipedia Foundation, {\it Permutation Pattern} [Initiated and largely written by Vince Vatter] \hfill\break
{\tt https://en.wikipedia.org/wiki/Permutation\_pattern} \quad .


\bigskip
\hrule
\bigskip
Mingjia Yang, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill\break
Email: {\tt my239 at math dot rutgers dot edu}   \quad .
\bigskip
Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. \hfill\break
Email: {\tt DoronZeil at gmail  dot com}   \quad .


\end
