\documentclass[12pt]{amsart} \usepackage{xypic} \usepackage{amsfonts} \newcommand{\bintree}{\xymatrix@!R@!C@=2ex@M=0.3ex} \newcommand{\LEFT}{\ar@{-}[dl]} \newcommand{\RIGHT}{\ar@{-}[dr]} \newcommand{\DOWN}{\ar@{-}[d]} \newcommand{\LDR}{\LEFT\DOWN\RIGHT} \newcommand{\LR}{\LEFT\RIGHT} \newcommand{\LD}{\LEFT\DOWN} \newcommand{\DR}{\DOWN\RIGHT} \def\mn{\mbox{-}} \title[Pattern Avoidance with Additional Restrictions]{Generalized Pattern Avoidance with Additional Restrictions} \author{Sergey Kitaev} \email{kitaev@math.chalmers.se} % Note how to get underscore \address{Matematik, Chalmers tekniska h\"ogskola och G\"oteborgs universitet, S-412~96 G\"oteborg, Sweden} \newtheorem{prop}{Proposition} \newtheorem{lemma}[prop]{Lemma} \newtheorem{cor}[prop]{Corollary} \newtheorem{thm}[prop]{Theorem} \theoremstyle{definition} \newtheorem{defin}[prop]{Definition} \newtheorem{ex}[prop]{Example} \newtheorem{remark}[prop]{Remark} \def\newop#1{\expandafter\def\csname #1\endcsname{\mathop{\rm #1}\nolimits}} \newop{erf} \newcommand\mps[1]{\marginpar{\small\sf#1}} \begin{document} \begin{abstract} Babson and Steingr\'{\i}msson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. We consider $n$-permutations that avoid the generalized pattern $1\mn32$ and whose $k$ rightmost letters form an increasing subword. The number of such permutations is a linear combination of Bell numbers. We find a bijection between these permutations and all partitions of an $(n-1)$-element set with one subset marked that satisfy certain additional conditions. Also we find the e.g.f. for the number of permutations that avoid a generalized 3-pattern with no dashes and whose $k$ leftmost or $k$ rightmost letters form either an increasing or decreasing subword. Moreover, we find a bijection between $n$-permutations that avoid the pattern $132$ and begin with the pattern $12$ and increasing rooted trimmed trees with $n+1$ nodes. \end{abstract} \maketitle %First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire %--first part \thispagestyle{myheadings} \font\rms=cmr8 \font\its=cmti8 \font\bfs=cmbx8 \markright{\its S\'eminaire Lotharingien de Combinatoire \bfs 48 \rms (2003), Article~B48e\hfill} \def\thepage{} % % \section{Introduction and Background} All permutations in this paper are written as words $\pi=a_1 a_2\cdots a_n$, where the $a_i$ consist of all the integers $1,2,\ldots,n$. A {\em pattern} is a word on some alphabet of letters, where some of the letters may be separated by dashes. In our notation, the classical permutation patterns, first studied systematically by Simion and Schmidt \cite{SchSim}, are of the form $p=1\mn3\mn2$, the dashes indicating that the letters in a permutation corresponding to an occurrence of $p$ do not have to be adjacent. In the classical case, an occurrence of a pattern $p$ in a permutation $\pi$ is a subsequence in $\pi$ (of the same length as the length of $p$) whose letters are in the same relative order as those in~$p$. For example, the permutation~264153 has only one occurrence of the pattern $1\mn2\mn3$, namely the subsequence~245. Note that a classical pattern should, in our notation, have dashes at the beginning and end. Since most of the patterns considered in this paper satisfy this, we suppress these dashes from the notation. In \cite{BabStein} Babson and Steingr\'{\i}msson introduced {\em generalized permutation patterns (GPs)} where two adjacent letters in a pattern may be required to be adjacent in the permutation. Such an adjacency requirement is indicated by the absence of a dash between the corresponding letters in the pattern. Thus, a pattern with no dashes corresponds to a contiguous subword anywhere in a permutation. For example, the permutation $\pi=516423$ has only one occurrence of the pattern $2\mn31$, namely the subword 564, but the pattern $2\mn3\mn1$ occurs also in the subwords 562 and 563. The motivation for introducing these patterns in \cite{BabStein} was the study of Mahonian statistics. A number of interesting results on GPs were obtained by Claesson \cite{Claes}. Relations to several well studied combinatorial structures, such as set partitions, Dyck paths, Motzkin paths and involutions, were shown there. In \cite{Kit1} the present author investigated simultaneous avoidance of two or more 3-letter GPs with no dashes. Also there is a number of works concerning GPs by Mansour (see for example \cite{Mans1, Mans2}). In this paper we consider avoiding some generalized 3-patterns with additional restrictions. The restrictions consist of demanding that a permutation begin or end with the pattern $12\ldots k$ or the pattern $k(k-1)\ldots 1$. %First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire %--restoring the headers and pagenumbering \pagenumbering{arabic} \addtocounter{page}{1} \markboth{\SMALL SERGEY KITAEV}{\SMALL PATTERN AVOIDANCE WITH ADDITIONAL RESTRICTIONS} % % It turns out that the number of permutations that avoid the pattern $1\mn32$ and end with the pattern $12 \ldots k$ is a linear combination of the Bell numbers. The $n$-th Bell number is the number of ways a set of $n$ elements can be partitioned into nonempty subsets. We find a bijection between these permutations and all partitions of an $(n-1)$-element set with one subset marked that satisfy certain special conditions. In particular, in Theorem~\ref{correspondence1}, we investigate the case $k=2$. We get that the total number of partitions of an $(n-1)$-element set with one part marked, is equal to the number of $(1\mn32)$-avoiding $n$-permutations that end with a $12$-pattern. Lemma~\ref{theBinomialIdentity} gives us an identity involving the Bell numbers and the Stirling numbers of the second kind, which seems to be new. In Theorem~\ref{trees} we prove that the number of $132$-avoiding $n$-permutations that begin with the pattern $12$ is equal to the number of increasing rooted trimmed trees with $n+1$ nodes. In Sections 4 -- 7, we give a complete description (in terms of {\em exponential generating functions (e.g.f.)}) for the number of permutations that avoid a pattern of the form $xyz$ and begin or end with the pattern $12\ldots k$ or the pattern $k(k-1)\ldots 1$. We record all the results concerning these e.g.f. in the table in Section~7. The case $k=1$ is equivalent to the absence of the additional restriction. This case was considered in \cite{ElizNoy} and \cite{Kit2}. We observe that avoidance of some pattern with the additional restrictions described above, in fact is equivalent to simultaneous avoidance of several patterns. For example, beginning with the pattern $12$ is equivalent to the avoidance of the pattern $[21)$ in the Babson-Steingr\'{\i}msson notation. Thus avoidance of the pattern $132$ and beginning with the pattern $12$ is equivalent to simultaneous avoidance of the patterns $132$ and $[21)$. Also, ending with the pattern $123$ is equivalent to simultaneously avoiding the patterns $(132]$, $(213]$, $(231]$, $(312]$ and $(321]$. \section{Set partitions and pattern avoidance} We recall some basic definitions. A {\em partition} of a set $S$ is a family, $\pi = \{ A_1, A_2, \ldots , A_k \}$, of pairwise disjoint non-empty subsets of $S$ such that $S = \cup_{i} A_i$. The total number of partitions of an $n$-element set is called a {\em Bell number} and is denoted~$B_n$. The {\em Stirling number of the second kind} $S(n,k)$ is the number of ways a set with $n$ elements can be partitioned into $k$ disjoint, non-empty subsets. \begin{prop}\label{formulaForP(n,k)} Let $P(n,k)$ be the number of $n$-permutations that avoid the pattern $1\mn32$ and end with the pattern $12\ldots k$. Then $$P(n,k)=\displaystyle\sum_{i=0}^{n-k}{\binom {n-1} i}B_i.$$ \end{prop} \begin{proof} Suppose a permutation $\pi=\sigma 1 \tau$ avoids the pattern $1\mn32$ and ends with the pattern $12\ldots k$. The letters of $\tau$ must be in increasing order, since otherwise we have an occurrence of the pattern $1\mn32$ involving 1. Also, $\sigma$ must avoid $1\mn32$. If $|\sigma|=i$ then obviously $0\leq i \leq n-k$ and we can choose the letters of $\sigma$ in ${\binom {n-1 } i}$ ways. By \cite[Proposition 5]{Claes}, the number of $i$-permutations that avoid the pattern $1\mn32$ is equal to $B_i$, hence there are $B_i$ ways to form $\sigma$. \end{proof} \begin{lemma}\label{theBinomialIdentity} We have \ $\displaystyle\sum_{i=0}^{n-1}{\binom n i}B_i=\displaystyle\sum_{i=0}^{n}i\cdot S(n,i).$ \end{lemma} \begin{proof} The identity can be proved from the recurrences for $S(n,k)$ and $B_n$, but we give a combinatorial proof. The left-hand side of the identity is the number of ways to choose $i$ elements from an $n$-element set, and then to make all possible partitions of the chosen elements. The right-hand side is the number of ways to partition a set with $n$ elements into $i$ disjoint non-empty subsets ($i=1,2, \ldots ,n$) and mark one of the subsets. For example if $n=4$ then $\overline{1}- 24 - 3$ and $1-\overline{24}-3$ are two different partitions, where the marked subset is overlined. A bijective correspondence between these combinatorial interpretations is given by the following: For the left-hand side, after partitioning the $i$ chosen elements, let the remaining $n-i$ elements form the marked subset in the partition. \end{proof} The formula for $P(n,k)$ in Proposition~\ref{formulaForP(n,k)}, applied to $k = 2$, and Lemma~\ref{theBinomialIdentity} now give the following theorem: \begin{thm}\label{correspondence1} The total number of partitions of an $(n-1)$-element set with one part marked, is equal to the number of $(1\mn32)$-avoiding $n$-permutations that end with the pattern $12$. \end{thm} We give now a direct combinatorial proof of this theorem. \begin{proof} Suppose $P=S_1-S_2- \cdots -S_k$ is a partition of an $(n-1)$-element set into $k$ subsets with one marked subset and $T_i$ is the word that consists of all elements of $S_i$ in increasing order. We may, without loss of generality, assume that $\min(S_i)<\min(S_j)$ if $i>j$. In particular, $1 \in S_k$. There are two cases possible: \begin{itemize} \item[1)] $S_k=\{1\}$ ($S_k$ is not marked set); \item[2)] Either $S_k=\overline{1}$ or $1 \in S_k$ and $|S_k|\geq 2$. \end{itemize} In the first case, to a partition $P=S_1-S_2- \cdots -\overline{S_i}-\cdots -S_{k-1}-1$ we associate the permutation $\pi(P)=nT_1T_2 \ldots T_{i-1}T_{i+1} \ldots T_{k-1}1T_i$, which is $(1\mn32)$-avoiding and ends with the pattern $12$ since $S_i \neq \emptyset$. For example $4-\overline{23}-1 \mapsto 54123$. In the second case we adjoin $n$ to a marked subset, and then consider the permutation $\pi(P)=T_1T_2 \ldots T_k$. This permutation is obviously $(1\mn32)$-avoiding since $\min(S_i)<\min(S_j)$ if $i>j$ and the letters in $T_i$ are in increasing order. Also it ends with the pattern $12$. For example $5-\overline{34}-12 \mapsto 534612$, and $5-234-\overline{1} \mapsto 523416$. Obviously in both cases we have an injection. Now it is easy to see that the correspondence above is a surjection as well. Indeed, for any $(1\mn32)$-avoiding permutation $\pi$ that ends with the pattern $12$, we can check if $\pi$ begins with $n$ or not and according to this we have either case 1) or 2). In the first case, we remove $n$, then read $\pi$ from left to right and consider all maximal increasing intervals. The elements of each such interval correspond to some subset, and we let all the letters to the right of 1 constitute the marked subset. In the second case, we divide $\pi$ into maximal increasing intervals, and let the letters of each interval correspond to a subset. Then we let the interval containing $n$ be the marked subset. Thus we have a surjection. So the correspondence is a bijection and the theorem is proved. \end{proof} The following theorem generalizes Theorem~\ref{correspondence1}. \begin{thm}\label{correspondence2} Let $P=S_1-S_2- \cdots -S_{\ell}$ be a partition of $\{ 1,2, \ldots, n-1 \}$ into $\ell$ subsets with subset $S_i$ marked. We assume also that $1 \in S_{\ell}$. Then $P(n,k)$ counts all possible marked partitions of $\{ 1,2, \ldots, n-1 \}$ that satisfy the following conditions: \begin{itemize} \item[1)] if $i=\ell$ (the last subset is marked) then $|S_{\ell}| \geq k-1$; \item[2)] if $i \neq \ell$ and $|S_{\ell}| \neq 1$ then $|S_{\ell}| \geq k$; \item[3)] if $i \neq \ell$ and $|S_{\ell}|=1$ then $|S_i| \geq k-1$. \end{itemize} \end{thm} \begin{proof} A proof of this theorem is similar to the proof of Theorem~\ref{correspondence1}. We assume that $\min(S_i)<\min(S_j)$ for $i>j$ and consider three cases. If a partition satisfies 1), that is $P=S_1-S_2- \cdots -\overline{S_{\ell}}$ and $|S_{\ell}| \geq k-1$, then adjoining $n$ to $S_{\ell}$ guarantees that the permutation $\pi(P)=T_1T_2 \ldots T_{\ell}$, which is $(1\mn32)$-avoiding, ends with $k$ letters in increasing order. In case 2), we adjoin $n$ to the marked subset and consider $\pi(P)=T_1T_2 \ldots T_{\ell}$. This permutation avoids the pattern $1\mn32$ and ends with the pattern $12\ldots k$ since $|S_{\ell}| \geq k$. In case 3), to a partition $P=S_1-S_2- \cdots -\overline{S_i}-\cdots -S_{k-1}-1$ we associate the permutation $\pi(P)=nT_1T_2 \ldots T_{i-1}T_{i+1} \ldots T_{k-1}1T_i,$ which is $(1\mn32)$-avoiding and ends with at least $k$ letters in increasing order since $|S_i| \geq k-1$. That this correspondence is a bijection can be shown in a way similar to the proof of Theorem~\ref{correspondence1}. \end{proof} \section{Increasing rooted trimmed trees and pattern avoidance} In an {\em increasing rooted tree}, nodes are numbered and the numbers increase as we move away from the root (see~\cite[Chapter 1]{Stan}). These trees are foundational in the paper by Elizalde and Noy~\cite{ElizNoy}, results from which are cited in Sections 4--6. A {\em trimmed tree} is a tree where no node has a single leaf as a child (every leaf has a sibling). \begin{thm}\label{trees} Let $A_n$ denote the set of all $n$-permutations that avoid the pattern $132$ and begin with the pattern $12$. The number of permutations in $A_n$ is equal to the number of increasing rooted trimmed trees (IRTTs) with $n+1$ nodes. \end{thm} \begin{proof} A {\em right-to-left minimum} of a permutation $\pi$ is an element $a_i$ such that $a_ii$. We describe a bijective correspondence $F$ between the permutations in $A_n$ and IRTTs with $n+1$ nodes. Suppose $\pi\in A_n$ and $\pi=P_0a_0P_1a_1\ldots P_ka_k$, where $a_i$ are the right-to-left minima of $\pi$ and $P_j$ are (possibly empty) subwords of $\pi$. We construct a IRTT $T = F(\pi)$ with $n+1$ nodes as follows. The root of $T$ is labelled by $0$ and $a_0, a_1,\ldots , a_k$ are the labels of the root's children if we read them from left to right. Then we let the right-to-left minima of $P_i$ be the labels of the children of $a_i$ and so on. It is easy to see that, since $\pi$ avoids $132$ and begins with $12$, $T$ avoids limbs of length~2. Also, $T$ is an increasing rooted tree and hence $T$ is a IRTT. For instance, $$F(2\; 9\; 10\; 5\; 3\; 1\; 11\; 13\; 14\; 8\; 12\; 7\; 4\; 6) = \xymatrix@!R@!C@=2ex@M=0.6ex{ & & & 0\LDR \\ & & 1\LD & 4\DOWN & 6 \\ & 2 & 3\LEFT & 7\DR \\ & 5\LD & & 8\LDR & 12 \\ 9 & 10 & 11 & 13 & 14 \\ }$$ Obviously, the correspondence $F$ is an injection. To see, that $F$ is a surjection, we show how to construct the permutation $\pi\in A_n$ that corresponds to a given IRTT $T$. The main rule is the following: If $a_i$ and $a_j$ are siblings, and $a_i 0$. Let $\pi$ be such a permutation of length $n+1$. Also, suppose $k \neq 2$. If $\pi = \sigma 1 \tau$ then either $\sigma = \epsilon$ or $\sigma \neq \epsilon$ where $\epsilon$ denotes the empty word. If $\sigma = \epsilon$ then $\tau$ must avoid $132$ and begin with an increasing subword of length $k-1$. Otherwise $\sigma$ must avoid $132$ and begin with an increasing subword of length $k$, whereas $\tau$ must begin with the pattern $12$, or be a single letter (there are $n$ ways to choose this letter), or be $\epsilon$. This leads to the following: \begin{equation} E_{n+1,k} = E_{n,k-1} + \displaystyle\sum_{i\geq 0}{\binom n i}E_{i,k}E_{n-i,2} + nE_{n-1,k} + E_{n,k}. \label{equality1} \end{equation} Multiplying both sides of the equality with $x^n/n!$ and summing over all $n$ we get the following differential equation \begin{equation} \frac{d}{d x}E^{12\ldots k}_{132}(x) = (E^{12}_{132}(x) + x + 1)E^{12\ldots k}_{132}(x) + E^{12\ldots (k-1)}_{132}(x), \label{equality2} \end{equation} with the initial conditions $E^{12\ldots k}_{132}(0) = 0$ for $k\geq 3$. Observe that equality~(\ref{equality2}) is not valid for $k=2$. Indeed, if $k=2$, then it is incorrect to add the term $E_{n,k-1} = E_{n,1}$ in~(\ref{equality1}), since this term counts the number of permutations $\pi = 1 \tau$ with the only restriction for $\tau$ that it must avoid $132$. The absence of an additional restriction for $\tau$ means that the 3 leftmost letters of $\pi$ could form the pattern $132$. However, we can use~(\ref{equality2}) to find $E^{12}_{132}(x)$ by letting $k$ equal~1. In this case we have $$\frac{d}{d x}E^1_{132}(x) = (E^{12}_{132}(x) + x + 1)E^1_{132}(x),$$ which gives \begin{equation} E^{12}_{132}(x) = \frac{e^{-x^2/2}}{1 - \int_{0}^{x}e^{-t^2/2}\ dt} - x - 1. \label{formulaF2} \end{equation} For the case $k\geq 3$, it is convenient to write $E^{12}_{132}(x)$ in the form $$E^{12}_{132}(x) = B^{\prime}(x)-x-1,$$ where $B(x)=-\ln (1-\int_{0}^{x}e^{-t^2/2}\ dt)$ and thus $B^{\prime}(x)=\exp(B(x)-\frac{x^2}{2})$. We will use the fact that $E^{1}_{132}(x)=e^{B(x)}$, which follows directly from~(\ref{formulaF1}) and the definition of $B(x)$. So~(\ref{equality2}) is equivalent to the differential equation $$\frac{d}{d x}E^{12\ldots k}_{132}(x) = B^{\prime}(x)E^{12\ldots k}_{132}(x) + E^{12\ldots (k-1)}_{132}(x)$$ which has the solution \bigskip\bigskip \begin{eqnarray*} &&E^{12\ldots k}_{132}(x) = e^{B(x)}\displaystyle\int_{0}^{x}e^{-B(t)}E^{12\ldots (k-1)}_{132}(t)\;dt = \\[20pt] &&E^1_{132}(x)\displaystyle\int_{0}^{x}\frac{E^{12\ldots (k-1)}_{132}(t)}{E^{1}_{132}(t)}dt =\\[20pt] &&E^1_{132}(x)\displaystyle\int_{0}^{x}\int_{0}^{t_2}\frac{E^{12\ldots (k-2)}_{132}(t_1)}{E^{1}_{132}(t_1)}dt_1dt_2 =\\[20pt] && E^1_{132}(x)\displaystyle\int_{0}^{x}\int_{0}^{t_{k-2}}\cdots \int_{0}^{t_2}\frac{E^{12}_{132}(t_1)}{E^1_{132}(t_1)}dt_1dt_2 \cdots dt_{k-2}. \end{eqnarray*} \bigskip \noindent Using (\ref{formulaF1}) and (\ref{formulaF2}) we now get the desired result. \end{proof} Using the formula for $E^{12\ldots k}_{132}(x)$ in Theorem~\ref{132increasingBegin} one can derive, in particular, that $$E^{123}_{132}(x) = -\frac{1}{2} - x - \frac{x^2}{2} + \frac{\left( 1+\frac{x}{2}\right)e^{-x^2/2} - \frac{1}{2}}{1-\int_{0}^{x}e^{-t^2/2}\ dt}.$$ \begin{thm}\label{132decreasingBegin} For $k \geq 2$ $$E^{k(k-1)\ldots 1}_{132}(x) = \frac{E^1_{132}(x)}{(k-1)!}\displaystyle\int_{0}^{x}t^{k-1}e^{-t^2/2}\ dt.$$ \end{thm} \begin{proof} We proceed as in the proof of Theorem~\ref{132increasingBegin}. Let $R_{n, k}$ denote the number of $n$-permutations that avoid the pattern $132$ and begin with a decreasing subword of length $k > 1$ and let $\pi$ be such a permutation of length $n+1$. Suppose also that $\pi = \sigma 1 \tau$. If $\tau = \epsilon$ then, obviously, there are $R_{n,k}$ ways to choose $\sigma$. If $|\tau| = 1$, that is, 1 is in the second position from the right in $\pi$, then there are $n$ ways to choose the rightmost letter in $\pi$ and we multiply this by $R_{k,n-1}$, which is the number of ways to choose $\sigma$. If $|\tau| > 1$ then $\tau$ must begin with the pattern $12$, otherwise the letter 1 and the two leftmost letters of $\tau$ form the pattern $132$, which is forbidden. So, in this case there are $\sum_{i \geq 0}{\binom n i}R_{i,k}E_{n-i,2}$ such permutations with the right properties, where $i$ indicates the length of $\sigma$ and $E_{n-i,2}$ is defined in the proof of Theorem~\ref{132increasingBegin}. In the last formula, of course, $R_{i,k} = 0$ if $i1$. Multiplying both sides of the equality with $x^n/n!$, summing over $n$ and reasoning as in the proof of Theorem~\ref{132decreasingBegin}, we get: \begin{equation} \frac{d}{d x} E^{k(k-1)\ldots 1}_{123}(x)= (E^{21}_{123}(x) + x + 1)\left(E^{k(k-1)\ldots 1}_{123}(x) + \frac{x^{k-1}}{(k-1)!}\right), \label{equality5.1} \end{equation} with the initial condition $E^{k(k-1)\ldots 1}_{123}(0) = 0$. To solve~(\ref{equality5.1}), we need to know $E^{21}_{123}(x)$. To find it, we consider the case $k=1$. In this case we have almost the same recurrence as we have in~(\ref{equality5}), but we must remove the last term in the right-hand side: $$P_{n+1,1} = P_{n,1} + nP_{n-1,1} + \displaystyle\sum_{i\geq 0}{\binom n i}P_{i,k}P_{n-i,2}.$$ After multiplying both sides of the last equality with $x^n/n!$ and summing over $n$, we have $$\frac{d}{d x} E^1_{123}(x) = (E^{21}_{123}(x) + x + 1)E^1_{123}(x),$$ and thus $$E^{21}_{123}(x)=\frac{\frac{d}{d x} E^1_{123}(x)}{P_1(x)}-x-1= \frac{\sqrt{3}}{2}\tan\left(\frac{\sqrt{3}}{2}x + \frac{\pi}{6}\right) -x - \frac{1}{2}.$$ Now we solve~(\ref{equality5.1}) in the way we solved Equation~(\ref{equality4}) and get \begin{multline*} E^{k(k-1)\ldots 1}_{123}(x) \\= \frac{e^{x/2}}{(k-1)!\cos\left(\frac{\sqrt{3}}{2}x + \frac{\pi}{6}\right)}\int_{0}^{x}e^{-t/2}t^{k-1}\sin\left(\frac{\sqrt{3}}{2}t + \frac{\pi}{3}\right)\ dt. \end{multline*} \end{proof} The following theorem is straightforward to prove. \begin{thm}\label{123increasingBegin} We have $E^{12\ldots k}_{123}(x)=0$ for $k \geq 3$ and \begin{align*} E^{12}_{123}(x) &= E^1_{123}(x) - E^{21}_{123}(x) \\ &= \frac{\sqrt{3}}{2}\frac{e^{x/2}}{\cos\left(\frac{\sqrt{3}}{2}x + \frac{\pi}{6}\right)} - \frac{1}{2} - \frac{\sqrt{3}}{2}\tan\left(\frac{\sqrt{3}}{2}x + \frac{\pi}{6}\right). \end{align*} \end{thm} \section{Avoiding $213$ and beginning with $k(k-1) \ldots 1$ or $12 \ldots k$} If $k=1$, then by \cite[Theorem 4.1]{ElizNoy} or \cite[Theorem 12]{Kit2} $$E^1_{213}(x) = \frac{1}{1 - \int_{0}^{x}e^{-t^2/2}\ dt}.$$ \begin{thm}\label{213increasingBegin} For $k\geq 2$ $$E^{12\ldots k}_{213}(x)=\int_{0}^{x}\int_{0}^{t}\frac{s^{k-2}e^{T(t)-T(s)}}{(k-2)!(1-\int_{0}^{t}e^{-m^2/2}d m)}\ dsdt,$$ where $T(x)=-x^2/2+\int_{0}^{x}\frac{e^{-t^2/2}}{1-\int_{0}^{t}e^{-s^2/2}d s}\ d t$. \end{thm} \begin{proof} Let $A_n$ denote the number of $n$-permutations that avoid the pattern $213$ and let $K_n$ denote the number of $n$-permutations that avoid $213$ and begin with the pattern $12\ldots k$. Let $C_n$ denote the number of $n$-permutation that avoid $213$, begin with the pattern $12\ldots k$ and end with the pattern $12$ and let $D_n$ denote the number of $n$-permutations that avoid $213$ and end with the pattern $12$. Also, let $A(x)$, $K(x)$, $C(x)$ and $D(x)$ denote the e.g.f. for the numbers $A_n$, $K_n$, $C_n$ and $D_n$ respectively. We observe, that $$D(x)=E^{12}_{132}(x)=e^{-x^2/2}/(1-\int_{0}^{x}e^{-t^2/2}d t) - x - 1,$$ since, by using the reverse and complement discussed in the next section, there are as many permutations that avoid the pattern $213$ and end with the pattern $12$ as those that avoid the pattern $132$ and begin with the pattern $12$. Also, $A(x)=E^1_{312}(x)$ and $K(x)= E^{12\ldots k}_{213}(x)$. Suppose now that $\pi = \sigma (n+1) \tau$ is an $(n+1)$-permutation that avoids the pattern $213$ and begins with the pattern $12\ldots k$. So $\sigma$ must avoid $213$, begin with $12\ldots k$, but also end with the pattern $12$ since otherwise the two rightmost letters of $\sigma$ together with the letter $(n+1)$ form the pattern $213$, which is forbidden. For $\tau$, there is only one restriction --- avoidance of $213$. So if $|\sigma|=i$ then we can choose the letters of $\sigma$ in ${\binom n i}$ ways, which gives $\sum_{i\geq 0}{\binom n i}C_iA_i$ permutations that avoid the pattern $213$ and begin with the pattern $12\ldots k$. Moreover, it is possible for $(n+1)$ to be in the $k$th position, in which case we choose the letters of $\sigma$ in ${\binom n {k-1}}$ ways and arrange them in increasing order. Thus $$K_{n+1} = \displaystyle\sum_{i\geq 0}{\binom n i}C_iA_{n-i} + {\binom n {k-1}}A_{n-(k-1)}.$$ Multiplying both sides of this equality with $x^n/n!$ and summing over~$n$, we get \begin{equation} K^{\prime}(x) = \left(C(x)+\frac{x^{k-1}}{(k-1)!}\right)A(x), \label{equality6} \end{equation} with the initial condition $K(0)=0$. To solve (\ref{equality6}) we need to find $C(x)$. Let $\pi = \sigma (n+1) \tau$ be an $(n+1)$-permutation that avoids the pattern $213$, begins with the pattern~$12\ldots k$ and ends with the pattern $12$. Reasoning as above, $\sigma$ must avoid the pattern $213$, begin with the pattern $12\ldots k$ and end with the pattern $12$, whereas $\tau$ must avoid $213$ and end with the pattern~$12$. This gives $\sum_{i\geq 0}{\binom n i}C_iD_{n-i}$ permutations counted by $C_{n+1}$. Also, the letter $(n+1)$ can be in the $k$th position, which gives ${\binom n {k-1}}D_{n-(k-1)}$ permutations, and this letter can be in the $(n+1)$st position, which gives $C_n$ permutations that avoid the pattern $213$, begin with the pattern $12\ldots k$ and end with the pattern $12$. Also, if $n+1=k$ and all the letters are arranged in increasing order, then $(n+1)$ is in the $(n+1)$st position, but this permutation is not counted by $C_n$ above. So $$C_{n+1} = \displaystyle\sum_{i\geq 0}{\binom n i}C_iD_{n-i} + {\binom n {k-1}}D_{n-(k-1)} + C_n + {\delta}_{n,k-1},$$ where $\delta_{n,k}$ is the Kronecker delta, that is, \[ \delta_{n,k} = \left\{ \begin{array}{ll} 1, & \mbox{if $n=k$,} \\ 0, & \mbox{else.} \end{array} \right. \] Multiplying both sides of the equality with $x^n/n!$ and summing over~$n$, we get \begin{equation} C^{\prime}(x) = (D(x)+1)C(x) + (D(x)+1)\frac{x^{k-1}}{(k-1)!}. \label{equality7} \end{equation} To solve (\ref{equality7}), it is convenient to introduce the function $T(x)$ such that $T^{\prime}(x)=D(x)+1$. Thus $$T(x) = x + \int_{0}^{x}D(t)dt = -x^2/2+\int_{0}^{x}\frac{e^{-t^2/2}}{1-\int_{0}^{t}e^{-s^2/2}d s}\ d t,$$ and we need to solve the equation $$C^{\prime}(x)= T^{\prime}(x)C(x) + T^{\prime}(x)\frac{x^{k-1}}{(k-1)!},$$ with $C(0) = 0$. The solution to this equation is given by \begin{align*} C(x)&=e^{T(x)}\int_{0}^{x}e^{-T(t)}T^{\prime}(t)\frac{t^{k-1}}{(k-1)!}d t \\ &= -\frac{x^{k-1}}{(k-1)!}+e^{T(x)}\int_{0}^{x}e^{-T(t)}\frac{t^{k-2}}{(k-2)!}d t. \end{align*} Now we substitute $C(x)$ into~(\ref{equality6}) to get the desired result. \end{proof} \begin{thm} For $k\geq 2$ \begin{multline*} E^{k(k-1)\ldots 1}_{213}(x)\\ = -\frac{x^{k-1}}{(k-1)!} + \displaystyle\sum_{n=0}^{k-2}\int_{0}^{x}\int_{0}^{t_n}\cdots\int_{0}^{t_1}\frac{C_{k-n}(t) + \delta_{n,k-2}}{1-\int_{0}^{t}e^{-m^2/2}d m}d td t_1 \cdots dt_n, \end{multline*} where \begin{multline*} C_k(x) = e^{T(x)}\displaystyle\int_{0}^{x}\int_{0}^{t_{k-2}}\cdots\int_{0}^{t_1} e^{-T(t)}\\ \cdot\left( \frac{e^{-t^2/2}}{1-\int_{0}^{t}e^{-m^2/2}dm} - t - 1\right)dt dt_1 \cdots dt_{k-2}, \end{multline*} with $T(x)=-x^2/2+\int_{0}^{x}\frac{e^{-t^2/2}}{1-\int_{0}^{t}e^{-s^2/2}d s}\ d t$. \end{thm} \begin{proof} Let $A_n$ denote the number of $n$-permutations that avoid the pattern $213$ and let $B_{n,k}$ denote the number of $n$-permutations that avoid $213$ and begin with the pattern $k(k-1)\ldots 1$ for $k\geq 2$. Let $C_{n,k}$ denote the number of $n$-permutation that avoid $213$, begin with $k(k-1)\ldots 1$ for $k\geq 2$ and end with the pattern $12$ and let $D_n$ denote the number of $n$-permutations that avoid $213$ and end with the pattern $12$. Also, let $A(x)$, $B_k(x)$, $C_k(x)$ and $D(x)$ denote the e.g.f. for the numbers $A_n$, $B_{n,k}$, $C_{n,k}$ and $D_n$ respectively. In the proof of Theorem~\ref{213increasingBegin} it was shown that $D(x)=e^{-x^2/2}/(1-\int_{0}^{x}e^{-t^2/2}d t) - x - 1$ and $A(x)=E^1_{312}(x)$. Moreover, $B_k(x)= E^{k(k-1)\ldots 1}_{213}(x)$. Suppose now that $\pi = \sigma (n+1) \tau$ is an $(n+1)$-permutation that avoids $213$ and begins with the pattern $k(k-1)\ldots 1$. So $\sigma$ must avoid $213$, begin with $k(k-1)\ldots 1$, but also end with the pattern $12$ if $|\sigma|\geq 2$, since otherwise the two rightmost letters of $\sigma$ together with the letter $(n+1)$ form the pattern $213$ which is forbidden. For $\tau$, there is only one restriction - avoidance of $213$. So if $|\sigma|=i$ then we can choose the letters of $\sigma$ in ${\binom n i}$ ways, which gives $\sum_{i\geq 0}{\binom n i}C_{i,k}A_i$ permutations counted by $B_{n+1,k}$. Also, it is possible for $(n+1)$ to be the leftmost letter, in which case the remaining letters must form a $n$-permutation that avoids $213$ and begins with the pattern $(k-1)(k-2)\ldots 1$. Thus \begin{equation} B_{n+1,k} = \displaystyle\sum_{i\geq 0}{\binom n i}C_{i,k}A_{n-i} + B_{n,k-1}. \label{equality9} \end{equation} However, this formula is not valid when $k=2$ and $n=0$. Indeed, since $B_{0,1} = A_{0}=1$, it follows from the formula that $B_{1,2}=1$, which is not true, since $B_{1,2}$ must be $0$. So, in the right-hand side of~(\ref{equality9}), we need to subtract the term \[ \gamma_{n,k} = \left\{ \begin{array}{ll} 1, & \mbox{if $n=0$ and $k=2$,} \\ 0, & \mbox{else.} \end{array} \right. \] Multiplying both sides of the obtained equality by $x^n/n!$ and summing over $n$, we get, that for $k\geq 3$ \begin{equation} \frac{d}{d x} B_k(x) = C_k(x)A(x) + B_{k-1}(x), \label{equality10} \end{equation} with the initial condition $B_k(0)=0$, and \begin{equation} \frac{d}{d x} B_2(x) = C_2(x)A(x) + B_{1}(x) - 1, \label{equality11} \end{equation} with the initial condition $B_2(0)=0$. The solution to differential equations~(\ref{equality10}) and~(\ref{equality11}) is given by $$B_k(x) = -\frac{x^{k-1}}{(k-1)!} + \displaystyle\sum_{n=0}^{k-2}\int_{0}^{x}\int_{0}^{t_n}\cdots\int_{0}^{t_1}\frac{C_{k-n}(t) + \delta_{n,k-2}}{1-\int_{0}^{t}e^{-m^2/2}d m}d td t_1 \cdots dt_n.$$ So, to prove the theorem, we only need to find $C_k(x)$. Suppose $\pi = \sigma (n+1) \tau$ be an $(n+1)$-permutation that avoids the pattern $213$, begins with the pattern $k(k-1)\ldots 1$ and ends with the pattern $12$. It is clear that $\sigma$ must avoid $213$, begin with the pattern $k(k-1)\ldots 1$ and end with the pattern $12$, whereas $\tau$ must avoid $213$ and end with the pattern $12$. There are $\sum_{i\geq 0}{\binom n i}C_{i,k}D_{n-i}$ permutations with these properties. Also, the letter $(n+1)$ can be in the leftmost position, which gives $C_{n,k-1}$ permutations, and $(n+1)$ can be in the rightmost position, which gives $C_{n,k}$ permutations, since in this case, two letters immediately to the left of $(n+1)$ cannot form a descent. So, $$C_{n+1,k} = \displaystyle\sum_{i\geq 0}{\binom n i}C_{i,k}D_{n-i} + C_{n,k-1} + C_{n,k}.$$ Multiplying both sides of the equality with $x^n/n!$ and summing over $n$, we get the following differential equation \begin{equation} C^{\prime}_k(x) = (D(x)+1)C_k(x) + C_{k-1}(x). \label{equality20} \end{equation} As when solving Equation~(\ref{equality7}), it is convenient to introduce the function $T(x)$ such that $T^{\prime}(x)=D(x)+1$. Moreover, Equation~(\ref{equality20}) is similar to Equation~(\ref{equality2}) and we can solve it in the same way. Also we observe that from the definitions, $C_1(t)=D(t)$, and thus \begin{align*} C_k(x) &= e^{T(x)}\displaystyle\int_{0}^{x}\int_{0}^{t_{k-2}}\cdots\int_{0}^{t_1} e^{-T(t)}C_1(t)\,dt dt_1 \cdots dt_{k-2}\\ &=e^{T(x)}\displaystyle\int_{0}^{x}\int_{0}^{t_{k-2}}\cdots\int_{0}^{t_1} e^{-T(t)}\\ &\kern3cm\cdot \left( \frac{e^{-t^2/2}}{1-\int_{0}^{t}e^{-m^2/2}dm} - t - 1\right)dt dt_1 \cdots dt_{k-2}. \end{align*} \end{proof} \section{Summarizing the results from sections 4,5 and 6} We recall that the {\em reverse} $R(\pi)$ of a permutation $\pi=a_1a_2 \ldots a_n$ is the permutation $a_na_{n-1} \ldots a_1$ and the {\em complement} $C(\pi)$ is the permutation $b_1b_2 \ldots b_n$ where $b_i=n+1-a_i$. Also, $R \circ C$ is the composition of $R$ and $C$. We call these bijections of $\mathcal{S}_n$ to itself {\em trivial}. Let $\phi$ be an arbitrary trivial bijection. It is easy to see that, for example, there are as many permutations avoiding the pattern 132 as those avoiding the pattern $\phi(132)$. Moreover if, for instance, a permutation $\pi$ begins with a decreasing pattern of length $k$, then depending on $\phi$, $\phi(\pi)$ either begins with an increasing pattern, or ends with either a decreasing or increasing pattern of length $k$. This allows us to apply Theorems 6 -- 11 to a number of other cases. We summarize all the obtained results concerning avoidance of a generalized 3-pattern with no dashes and beginning or ending with either increasing or decreasing subword, in the table below. \begin{remark} Usually, in the papers on forbidden patterns in permutations one deals with one more trivial bijection, namely the operation of {\em permutation inverse}, which is defined in the classical sense. However, this operation is not extended to generalized patterns in the way $R$ and $C$ do. For instance, the permutation $\pi=25143$ avoids the generalized pattern $\tau=321$, whereas the inverse $\pi^{-1}=31542$ does not avoid $\tau^{-1}=321$. So, in this paper the possible symmetries have been reduced from 8 to 4. \end{remark} \vfill \begin{center} \begin{tabular}{|c|c|c|c|c|} \hline & {\bf avoid} & {\bf begin} & {\bf end} & {\bf e.g.f.} \\ \hline & 123 & $12\ldots k$ & -- & \\ {\bf 1} & 123 & -- & $12\ldots k$ & $\frac{\sqrt{3}}{2}\frac{e^{x/2}}{\cos(\frac{\sqrt{3}}{2}x + \frac{\pi}{6})}$, if $k=1$ \\[4mm] & 321 & $k\ldots 21$ & -- & $\frac{\sqrt{3}}{2}\frac{e^{x/2}}{\cos(\frac{\sqrt{3}}{2}x + \frac{\pi}{6})} - \frac{1}{2} - \frac{\sqrt{3}}{2}\tan(\frac{\sqrt{3}}{2}x + \frac{\pi}{6})$, if $k=2$ \\[4mm] & 321 & -- & $k\ldots 21$ & 0, if $k\geq 3$ \\[3mm] \hline & 123 & $k\ldots 21$ & -- & \\ {\bf 2} & 123 & -- & $k\ldots 21$ & $\frac{\sqrt{3}}{2}\frac{e^{x/2}}{\cos(\frac{\sqrt{3}}{2}x + \frac{\pi}{6})}$, if $k=1$ \\ & 321 & $12\ldots k$ & -- & \\ & 321 & -- & $12\ldots k$ & $\frac{e^{x/2}\int_{0}^{x}e^{-t/2}t^{k-1}\sin(\frac{\sqrt{3}}{2}t + \frac{\pi}{6}))\ dt}{(k-1)!\cos(\frac{\sqrt{3}}{2}x + \frac{\pi}{6})}$, if $k \geq 2$ \\[4mm] \hline & 132 & $12\ldots k$ & -- & \\[3mm] {\bf 3} & 213 & -- & $12\ldots k$ & $(1 - \int_{0}^{x}e^{-t^2/2}\ dt)^{-1}$, if $k=1$ \\[4mm] & 312 & $k\ldots 21$ & -- & $e^{-x^2/2}(1 - \int_{0}^{x}e^{-t^2/2}\ dt)^{-1} - x - 1$, if $k=2$ \\[4mm] & 231 & -- & $k\ldots 21$ & $(1 - \int_{0}^{x}e^{-t^2/2}\ dt)^{-1}\int_{0}^{x}\int_{0}^{t_{k-2}}\cdots \int_{0}^{t_2}(e^{-t_1^2/2} - $ \\[3mm] & & & & $(t_1+1)(1 - \int_{0}^{t_1}e^{-t^2/2}\ dt)) dt_1dt_2 \cdots dt_{k-2}$, if $k\geq 3$ \\[4mm] \hline & 132 & $k\ldots 21$ & -- & \\ {\bf 4} & 213 & -- & $k\ldots 21$ & $(1 - \int_{0}^{x}e^{-t^2/2}\ dt)^{-1}$, if $k=1$ \\[4mm] & 312 & $12\ldots k$ & -- & $\frac{1}{(k-1)!(1 - \int_{0}^{x}e^{-t^2/2}\ dt)}\int_{0}^{x}t^{k-1}e^{-t^2/2}\ dt$, if $k\geq 2$ \\ & 231 & -- & $12\ldots k$ & \\ \hline & 213 & $12\ldots k$ & -- & $(1 - \int_{0}^{x}e^{-t^2/2}\ dt)^{-1}$, if $k=1$ \\ {\bf 5} & 132 & -- & $12\ldots k$ & \\ & 231 & $k\ldots 21$ & -- & $\int_{0}^{x}\int_{0}^{t}\frac{s^{k-2}e^{T(t)-T(s)}}{(k-2)!(1-\int_{0}^{t}e^{-m^2/2}d m)}\ dsdt$ , if $k\geq 2$, where \\ & 312 & -- & $k\ldots 21$ & $T(x)=-x^2/2+\int_{0}^{x}\frac{e^{-t^2/2}}{1-\int_{0}^{t}e^{-s^2/2}d s}\ d t$\\[4mm] \hline & 213 & $k\ldots 21$ & -- & $(1 - \int_{0}^{x}e^{-t^2/2}\ dt)^{-1}$, if $k=1$ \\[4mm] {\bf 6} & 132 & -- & $k\ldots 21$ & $-\frac{x^{k-1}}{(k-1)!} + \displaystyle\sum_{n=0}^{k-2}$$\int_{0}^{x}\int_{0}^{t_n}\cdots\int_{0}^{t_1}\frac{C_{k-n}(t) + \delta_{n,k-2}}{1-\int_{0}^{t}e^{-m^2/2}d m}d td t_1 \cdots dt_n$, \\[4mm] & 231 & $12\ldots k$ & -- & if $k\geq 2$, where $C_k(x)=e^{T(x)}\int_{0}^{x}\int_{0}^{t_{k-2}}\cdots \int_{0}^{t_1} e^{-T(t)}\cdot$ \\[4mm] & 312 & -- & $12\ldots k$ & $\left( \frac{e^{-t^2/2}}{1-\int_{0}^{t}e^{-m^2/2}dm} - t - 1\right)dt dt_1 \cdots dt_{k-2}$ and $T(x)$ as above \\[4mm] \hline \end{tabular} \end{center} \begin{thebibliography}{14} \bibitem[BabStein]{BabStein} E. Babson, E. Steingr\'{\i}msson: Generalized permutation patterns and a classification of the Mahonian statistics, S\'eminaire Lotharingien de Combinatoire, B44b:18pp, 2000. \bibitem[Bon]{Bon} M. B\'ona: Exact enumeration of $1342$-avoiding permutations: a close link with labeled trees and planar maps, J. Combin. Theory Ser. A {\bf 80} (1997), no. 2, 257--272. \bibitem[Claes]{Claes} A. Claesson: Generalised Pattern Avoidance, European J. Combin. {\bf 22} (2001), 961-971. \bibitem[ClaesMans]{ClaesMans} A. Claesson and T. Mansour: Permutations avoiding a pair of generalized patterns of length three with exactly one dash, preprint CO/0107044. \bibitem[ElizNoy]{ElizNoy} S. Elizalde and M. Noy: Enumeration of Subwords in Permutations, Proceedings of FPSAC 2001. \bibitem[Kit1]{Kit1} S. Kitaev: Multi-avoidance of generalised patterns, to appear in Discrete Mathematics. \bibitem[Kit2]{Kit2} S. Kitaev: Partially ordered generalized patterns, to appear in Discrete Mathematics. \bibitem[Knuth]{Knuth} D. E. Knuth: {\em The Art of Computer Programming}, 2nd ed. Addison Wesley, Reading, MA, (1973). \bibitem[Loth]{Loth} M. Lothaire: {\em Combinatorics on Words}, Encyclopedia of Mathematics and its Applications, {\bf 17}, Addison-Wesley Publishing Co., Reading, Mass. (1983). \bibitem[Mans1]{Mans1} T. Mansour: Continued fractions and generalized patterns, European J. Combin., to appear (2002), math.CO/0110037. \bibitem[Mans2]{Mans2} T. Mansour: Continued fractions, statistics, and generalized patterns, to appear in Ars Combinatorica (2002), preprint CO/0110040. \bibitem[SloPlo]{SloPlo} N. J. A. Sloane and S. Plouffe: {\em The Encyclopedia of Integer Sequences}, Academic Press, (1995). \verb>http://www.research.att.com/~njas/sequences/> \bibitem[Stan]{Stan} R. Stanley: {\em Enumerative Combinatorics}, Volume {\bf 1}, Cambridge University Press, (1997). \bibitem[SchSim]{SchSim} R. Simion, F. Schmidt: Restricted permutations, European J. Combin. {\bf 6} (1985), no. 4, 383--406. \end{thebibliography} \end{document}