%pamp.tex: Counting Permutations that Avoid Many Patterns
%Plain TeX
% In TeXShop, compile with XeTeX
%begin macros

\def\mod{\rm mod}
\def\Z{\bf Z}
\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\W{{\cal W}}
\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
{
Templates for Pattern Avoidance
}

\rm
\bigskip
\centerline
{\it
Yonah  BIERS-ARIEL
}

\bigskip

{\bf Abstract}: 

{\bf 1. } One approach to finding the sizes of permutation avoidance classes is to construct easily enumerated sets and then see if these sets avoid any interesting patterns. In this section, we develop a method of generating sets of permutations using {\bf templates} which both avoid certain patterns, and grow quickly as the lengths of the permutations increase. We will define two kinds of templates, but first will try to motivate their definition with a proof of the well-known fact that the number of permutations of length $n$ which avoid the pattern 132, a quantity which we will call $B_n$, is equal to $C_n$, then $n^{th}$ Catalan number.

{\bf Theorem 1}  The number of $132$-avoiding permutations of length $n$ is given by $C_n$.

{\it Proof:} The proof is by induction. When $n=0$, it is clear that $B_n=1$, so suppose that $B_m=C_m$ for all $m<n$. Consider a length-$n$ permutation $\pi$, and suppose that $n$ appears in position $i$. If $\pi$ avoids 132, it follows that the $i-1$ numbers which proceed $n$ must all be greater than all the $n-i$ numbers which follow $n$, and, moreover, the prefix of $\pi$ formed by the first $i-1$ numbers and the suffix formed by the last $n-i$ numbers must both avoid 132 themselves. Conversely, if these two conditions are met, then $\pi$ avoids 132. Any instance of 132 cannot have the 1 and the 2 on opposite sides of the number $n$ because every number preceding $n$ is greater than every number following it, but any instance of 132 also cannot have the 1 and the 2 on the same side of $n$ because both the prefix preceding $n$ and the suffix following $n$ avoid 132 (and, obviously, neither 1 nor 2 can be represented by $n$). It follows by induction that $B_n=\sum_{i=1}^n B_{i-1}\cdot B_{n-i}$ for all $n\ge 0$; since $B_n$ has the same initial condition as $C_n$ and follows the same recurrence, we conclude that $B_n=C_n$ for all $n\ge 0$.

In this proof, we showed that every 132-avoiding permutation of length $n$ has the form $LnS$ where $L$ and $S$ are 132-avoiding permutations such that every number in $L$ is larger than every number in $S$. We will generalize this idea in the following definition.

{\bf Definition 2:}
A {\bf template} of length $n\ge 1$ is a pair of strings $P$ and $B$ of length $n$. We require that $P$ be a permutation of length $n$ and $B$ be a binary string of length $n$. We will denote the $i^{th}$ element of $P$ by $p_i$ and the $i^{th}$ element of $B$ by $b_i$.
%These strings have the following two properties: no two consecutive elements of $S_2$ can both be 1, and if the $i^{th}$ element of $S_2$ is 0, the $i^{th}$ element of $S_1$ is $m$, and $L$ and $S$ are the subsets of $[n]$ whose elements are greater than and less than $m$ respectively, then the $j^th$ element of $S_2$ is 0 either for every $j \in L$ or for every $j \in S$.

%We will assign to every template an {\bf unrestricted set} and a {\bf restricted set}. The unrestricted sets will have good pattern avoidance properties, in particular, many of them are equal to the sets of permutations avoiding particular patterns. Unfortunately, it is difficult to count the elements of unrestricted sets. Restricted sets, on the other hand, will be easy to count (due to the seemingly unintuitive properties of a template), but will not have such nice pattern avoidance properties.

%The {\bf unrestricted set} of length $n$ corresponding to the template $T=(S_1,S_2)$, which we will call $U_{n,T}$, is defined recursively as follows. First, $U_{0,T}$ is the empty string and $U_{1,T}=\{1\}$ regardless of $T$. Then, $U_{n,T}$ is the set of permutations $\pi$ of length $n$ which can be divided into $|S_1|$ subwords (i.e. strings of consecutive elements of $\pi$) such that if the $i^{th}$ element of $S_1$ is greater than the $j^{th}$ element of $S_1$, then every element of $i^{th}$ subword of $\pi$ is greater than every element of the $j^{th}$ subword. Moreover, we require that each subword of length $l$ be an element of $U_{l,T}$, if the $i^{th}$ element of $S_1$ is 0, then the $i^{th}$ subword must have no more than 1 element, and no subword can have length $n$ (i.e. be all of $\pi$). We now provide an example of the unrestricted set of a template.

%{\bf Example 2:}
%Let $T=(132,100)$; then $U_{1,T}=\{1\}, U_{2,T}=\{12,21\}, U_{3,T}=\{123,132,213\}$. To find the elements of $U_{3,T}$ we consider a permutation $\pi$ of length 3, and divide it up into subwords $W1,W2,W3$. To have $\pi \in U_{3,T}$, we must have at least one of $W_2,W_3$ be nonempty. If just one of $W_2,W_3$ is nonempty, then $W_1$ will have length 2, and every element of $W_1$ must be less than the single element of $W_2$ or $W_3$. We can pick any element of $U_{2,T}$ to be $W_1$, and so we get that $123, 213 \in U_{3,T}$. If both $W_2$ and $W_3$ are nonempty, then each subword has length 1, and we see that $132 \in U_{3,T}$ and that these three are the only permutations in $U_{3,T}$.

For every positive integer $n$ and template $T=(P, B)$, we define a set of permutations of length $n$, which we will call $R_{n,T}$, as follows. First, $R_{0,T}$ is the empty string and $R_{1,T}=\{1\}$ regardless of $T$. Then, $R_{n,T}$ is the set of permutations $\pi$ of length $n$ which can be divided into subwords (i.e. strings of consecutive elements of $\pi$) called $W_1,...,W_t$ (with $t=|P|=|B|$) such that if $p_i > p_j$, then every of $W_i$ greater than every element of $W_j$. Moreover, we require that each $W_i$ of length $l$ be an element of $U_{l,T}$, and, if $B_i=0$, then $W_i$ must have exactly one element. If these conditions are met, we say that $W_1,...,W_t$ {\bf fit} the template $T$, so a permutation of length $n$ is an element of $R_{n,T}$ if it can be decomposed into subwords which fit $T$. We now provide an example of the set of a template.

{\bf Example 3:}
Let $T=(231,101)$; then $R_{1,T}=\{1\}, R_{2,T}=\{12,21\},$ and $R_{3,T}=\{123,213,231,312,321\}$. To find the elements of $R_{3,T}$ we consider a permutation $\pi$ of length 3 and divide it up into subwords $W1,W2, W3$. We know that $W2$ is the string 3, and so we can choose $W1 \in R_{2,T}$ and $W3$ empty, $W3 \in R_{2,T}$ and $W1$ empty, or $W1,W3 \in R_{1,T}$. Because $|R_{2,T}|=2$, each of the first two options gives two distinct permutations in $R_{3,T}$ (123, 213, 312, and 321), while the last option gives one permutation (231). Note that $R_{3,T}$ is exactly the set of length 3 permutations which avoid 132. In fact $R_{n,T}$ is the set of length $n$ permutations which avoid 132; this fact can be checked by reviewing the proof of Theorem 1. Therefore, considering sets corresponding to templates does generalize the argument of Theorem 1.

Once we begin looking at permutations with length greater than 3 it becomes much harder (and likely impossible) to find templates which produce entire pattern avoidance classes. However, it is not too difficult to find templates which produce only permutations avoiding some set of patterns, which is to say subsets of pattern avoidance classes. Therefore, looking at templates lets us find lower bounds on the size of certain avoidance classes. The following proposition shows an application of this method.

{\bf Proposition 4:} Let $Q_n$ be the set of all permutations of $n$ which avoid every element of $\{2143, 2413, 3142\}$ and let $q_n=|Q_n|$. Then, if the sequence $(r_n)_{n=0}^\infty$ is defined by $r_0=r_1=1$, and $r_n= \sum_{i=1}^{n-1}\sum_{j=i+1}^n r_{i-1}r_{j-i-1}r_{n-j}$ for $n>1$, it holds that $q_n \ge r_n$ for all $n$.

{\it Proof:} The proof is complicated and not especially enlightening, and Theorem 5 will allow a computer to quickly prove the proposition (the last paragraph of this proof, which is simple and straightforward is still necessary). This proof is included to illustrate the headache that Theorem 5 will help alleviate. The main step of the proof is to show that $Q_n$ contains $R_{n, T}$ where $T=(45312,10101)$. We will show that every permutation in $R_{n,T}$ avoids 2143, 2413, and 3142. First, note that for 2413, and 3142, no proper subword with length greater than 2 contains only consecutive numbers. When we divide a permutation into subwords to fit into the template, each subword must contain only consecutive numbers. Thus we can conclude that if a pattern is present in a permutation in $R_{n,T}$, then it is contained entirely in a single subword or each element is in a different subword. The second case cannot occur because the permutation 45312 avoids both patterns. To see that the first case cannot occur, suppose by way of contradiction that it does, and pick $n$ minimally so that a permutation of $R_{n,T}$ contains one of the two patterns under consideration. When we divide up this permutation into subwords so that it fits into $T$, we must choose some subword to contain pattern, but then this subword is a shorter permutation which contains the pattern, providing a contradiction. This shows that every permutation in $R_{n,T}$ avoids 2413 and 3142.

Next we will see that every permutation also avoids 2143. Again suppose by way of contradiction that there is a permutation in $R_{n,T}$ which contains 2143, and pick $n$ minimally so that this occurs. Then, if we divide up the permutation into 5 subwords, $W_1,...,W_5$, which fit the template $T$ the occurrence of 2143 cannot be contained entirely in any one subword. Therefore, $W_1$ either contains no part of the occurrence, contains the 2, or contains the 21. In the first two cases $W_2$ must not contain any part of the occurrence either; it cannot contain the 2 or 1 because it is the largest element of the permutation. If $W_1$ was empty, then we must fit 2143 into $W_3W_4W_5$, which is impossible because either the 2 will go in $W_3$ even though each element of $W_3$ must be greater than each element of $W_4$ and $W_5$, or else we would need to fit 143 into $W_5$ which can't happen because they are not consecutive integers (the 2 is missing). If $W_1$ contained 2, then $W_2$ must contain 4 and 3 because all the elements of every other subword must be less than the elements of $W_1$. Therefore, the permutations in $R_{n,T}$ avoid 2143, and so $R_{n,T} \subseteq Q_n$.

Now, we just need to show that $|R_{n,T}|=r_n$. First, it follows from the definition of $R_{n,T}$ that $|R_{0,T}|=|R_{1,T}|=1$. Then, for a permutation in $R_{n,T}$, we will say that $n$ occurs at position $i$ and 1 at position $j$. We get that $1\le i \le n-1$ and $i+1 \le j \le n$. Then, $W_1$ can be any of the $r_{i-1}$ elements of $R_{i-1,T}$, $W_3$ can be any of the $r_{j-i-1}$ elements of $R_{j-i-1,T}$, and $W_5$ can be any of the $r_{n-j}$ elements of $R_{n-j,T}$. Therefore, $r_n= \sum_{i=1}^{n-1}\sum_{j=i+1}^n r_{i-1}r_{j-i-1}r_{n-j}$ for $n>1$.

While this recurrence for $(r_n)$ is reminiscent of the Catalan recurrence, it does not appear to have a similarly nice closed form solution.

Fortunately, it is possible to prove results of this kind experimentally without the need for detailed write-ups. The following theorem establishes a sufficient condition for $R_{n,T}$ to avoid a set of patterns which is independent of $n$, and so can be tested for all $n$ at once using a computer.

{\bf Theorem 5:} Let $T=(P,B)$ be a template, let $B$ have $k$ 0's, and let $\sigma$ be a pattern of length $l>0$. Then, if there exists an $n$ such that $R_{n,T}$ contains a permutation which has $\sigma$ as a pattern, there also exists an $m \le (l-1)(k+1)+1$ such that $R_{m,T}$ also contains a permutation which has $\sigma$ as a pattern.

{\it Proof:} This Theorem will be an immediate corollary of Theorem 6, and, while it can be proved separately, the proof is almost identical to that of Theorem 6, so we omit it.

%Fix $k$ and $n$; we proceed by induction on $l$. If $l=1$, then $\sigma$ is the pattern 1 and is contained in the permutation 1 which is the element of $R_{1,T}$. Assume that the theorem holds for patterns of length up to $l-1$. Now let $\pi' \in R_{n,T}$ be the permutation which contains $\sigma$ as a pattern, and pick some occurrence of $\sigma$ in $\pi'$. We can divide $\pi'$ into subwords $W'_1,...,W'_t$ (where $t=|T|$) such that the $W'_i$ fit the template $T$. We can similarly divide $\sigma$ into subwords $U_1, ..., U_t$ so that $U_i$ is the portion of the chosen occurrence of $\sigma$ which lies in $W'_i$. If there exists $i$ such that only $U_i$ is nonempty, then $W'_i$ contains $\sigma$ and is shorter than $\pi$, so set $\pi=W'_i$ and repeat the decomposition for the new $\pi$. Repeat until either at least two $U_i$ are nonempty or $|\pi| \le (l-1)(k+1)+1$. In the second case we are done, so assume that the first case holds.

%We will now find $m$ and construct a permutation $\pi \in R_{m}$ which contains $\sigma$. Like $\pi'$ we need to be able to divide $\pi$ into $W_1,...,W_t$ to fit $T$, so we will construct the $W_i$ individually. For each $i$, let $u_i=|U_i|$. By the induction hypothesis, there exist $W_i$ such that $|W_i| =w_i \le (u_i-1)(k+1)+1$, $W_i \in R_{w_i,T}$, and $U_i$ is a pattern in $W_i$. It may be that for some $i$, $W_i$ is empty even though $B_i=0$; if this is the case, we must add up to $k$ new $W_i$ to ensure that each $W_i$ has length 1 whenever $B_i=0$. Lastly, we choose $i$ so that $P_i=1$ and $j$ so that $P_j=2$ and increase every element of $W_j$ by the same amount so that every element of $W_j$ is greater than every element of $W_i$, and we repeat this with $j=3..t$ and $i=j-1$. Now, concatenating all the $W_i$ gives a permutation $\pi$ of length $m$ in $R_{m,T}$ which contains the pattern $\sigma$.

%It remains to show that $m \le (l-1)(k+1)+1$. Let $I=\{i : u_i>0\}$; using the construction of $\pi$ and the induction hypothesis, we find that $m \le \sum_{i\in I} ((u_i-1)(k+1)+1) + k = (k+1)(\sum_{i\in I} u_i) - k\cdot |I|+k=(k+1)(l)-k|I|+k \le (k+1)(l-1)+1$ because we found at the end of the first paragraph that $|I| \ge 2$. Therefore, the proof is complete by induction.

With this result in hand, the author's laptop was able to prove Proposition 4 in 16 seconds using Maple.

There is no particular reason to consider templates just one at a time. Analogously to how we originally defined templates, we define the set of length $n$ permutations corresponding to the set of templates ${\cal {T}}=\{T_1,...,T_r\}$. We will call this set of permutations $S_{n, \cal{T}}$, and define it recursively as follows. First, $S_{0,\cal T}$ is the empty string and $S_{1,\cal T}=\{1\}$ regardless of $\cal T$. Then, $S_{n,\cal T}$ is the set of permutations $\pi$ of length $n$ such that, for some $T=(P,B) \in \cal T$, we can divide $\pi$ into subwords $W_1,...,W_t$ such that if $p_i > p_j$, then every element of $W_i$ greater than every element of $W_j$. Moreover, we require that each $W_i$ of length $l$ be an element of $S_{l,\cal T}$ (rather than of $R_{l,T}$), and, if $B_i=0$, then $W_i$ must have exactly one element.

We will finish this section by proving a generalization of Theorem 5 for sets of templates, and giving an example of its application.

{\bf Theorem 6:} Let ${\cal T} = \{(P_1, B_1),...,(P_r,B_r)\}$ be a set of templates, suppose that for all $i$ $B_i$ has no more than $k$ 0's, and let $\sigma$ be a pattern of length $l>0$. Then, if there exists an $n$ such that $S_{n,\cal T}$ contains a permutation which has $\sigma$ as a pattern, there also exists an $m \le (l-1)(k+1)+1$ such that $S_{m, \cal T}$ also contains a permutation which has $\sigma$ as a pattern.

{\it Proof:} Fix $k$ and $n$; we proceed by induction on $l$. If $l=1$, then $\sigma$ is the pattern 1 and is contained in the permutation 1 which is the element of $S_{1,\cal T}$. Assume that the theorem holds for patterns of length up to $l-1$. Now let $\pi' \in S_{n, \cal T}$ be the permutation which contains $\sigma$ as a pattern, and pick some occurrence of $\sigma$ in $\pi'$. We can choose $T = (P,B) \in \cal T$ and divide $\pi'$ into subwords $W'_1,...,W'_t$ (where $t=|P|$) such that the $W'_i$ fit the template $T$. We can similarly divide $\sigma$ into subwords $U_1, ..., U_t$ so that $U_i$ is the portion of the chosen occurrence of $\sigma$ which lies in $W'_i$. If there exists $i$ such that only $U_i$ is nonempty, then $W'_i$ contains $\sigma$ and is shorter than $\pi'$, so set $\pi'=W'_i$ and repeat the decomposition for the new $\pi'$. Repeat until either at least two $U_i$ are nonempty or $|\pi'| \le (l-1)(k+1)+1$. In the second case we are done, so assume that the first case holds.

We will now find $m$ and construct a permutation $\pi \in S_{m,\cal T}$ which contains $\sigma$. Like $\pi'$ we need to be able to divide $\pi$ into $W_1,...,W_t$ to fit $T$, so we will construct the $W_i$ individually. For each $i$, let $u_i=|U_i|$. By the induction hypothesis, there exist $W_i$ such that $|W_i| =w_i \le (u_i-1)(k+1)+1$, $W_i \in S_{w_i,\cal T}$, and $U_i$ is a pattern in $W_i$. It may be that for some $i$, $W_i$ is empty even though $B_i=0$; if this is the case, we must add up to $k$ new $W_i$ to ensure that each $W_i$ has length 1 whenever $B_i=0$. Lastly, we choose $i$ so that $p_i=1$ and $j$ so that $p_j=2$ and increase every element of $W_j$ by the same amount so that every element of $W_j$ is greater than every element of $W_i$, and we repeat this with $j=3..t$ and $i=j-1$. Now, concatenating all the $W_i$ gives a permutation $\pi$ of length $m$ in $S_{m, \cal T}$ which contains the pattern $\sigma$.

It remains to show that $m \le (l-1)(k+1)+1$. Let $I=\{i : u_i>0\}$; using the construction of $\pi$ and the induction hypothesis, we find that $m \le \sum_{i\in I} ((u_i-1)(k+1)+1) + k = (k+1)(\sum_{i\in I} u_i) - k\cdot |I|+k=(k+1)(l)-k|I|+k \le (k+1)(l-1)+1$ because we found at the end of the first paragraph that $|I| \ge 2$. Therefore, the proof is complete by induction.

Theorem 6 can give lower bounds on the sizes of many sets of avoidance classes. As an example, we offer the following proposition:

{\bf Proposition 7:} Let $Q_n$ be the set of all permutations of $n$ which avoid every element of $\{2341, 2413, 2431, 3241\}$ and let $q_n=|Q_n|$. Then, if the sequence $(s_n)_{n=0}^\infty$ is defined by $s_0=s_1=1$, and $s_n= \sum_{i=1}^{n-1}\sum_{j=i+1}^n 2 \cdot s_{i-1}s_{j-i-1}s_{n-j}$ for $n>1$, it holds that $q_n \ge s_n$ for all $n$.

{\it Proof:} Let $T_1=(14253, 10101), T_2=(15243,10101),$ and ${\cal T}=\{T_1,T_2\}$. Using Maple, one can generate $S_{n,\cal T}$ for $1 \le n \le 10$, and confirm that every permutation in each of these sets avoids 2341, 2413, 2431, and 3241 (we did this on a laptop in less than 7 minutes). Because these patterns all have length 4, both $B_1$ and $B_2$ have two 0's, and $(4-1)\cdot (2+1)+1=10$, Theorem 6 promises that, for all $n$, every permutation in $S_{n,\cal T}$ avoids 2341, 2413, 2431, and 3241.

Now we show that $|S_{n, \cal T}| = s_n$ by induction. Certainly $|S_{0, \cal T}|=|S_{1, \cal T}|=1$. When picking a permutation in $S_{n, \cal T}$, we first choose whether this permutation will follow the template $T_1$ or $T_2$. This will not cause us to count any permutation twice because if a permutation has $n-1$ appear before $n$, then it can only follow $T_1$, and if it has $n$ appear before $n-1$ then it can only follow $T_2$. Now, for $T_1$, we must choose the location of $n-1$, call this $i$, and the location of $n$, call it $j$. For $T_2$, we will call the location of $n$ $i$ and the location of $n-1$ $j$. For either template, we have $1 \le i \le n-1$, $i+1 \le j \le n$. Once $i$ and $j$ are chosen, we can fill in the portion of the permutation before position $i$ in any of $s_{i-1}$ ways, the portion between positions $i$ and $j$ in $s_{j-i-1}$ ways, and the portion following position $j$ in $s_{n-j}$ ways. Therefore, $|S_{n,\cal T}|=\sum_{i=1}^{n-1}\sum_{j=i+1}^n 2 \cdot s_{i-1}s_{j-i-1}s_{n-j} = s_n$ for  $n >1$.

\end



