\documentstyle[12pt]{amsart} \headheight=8.5pt \textheight=574pt \textwidth=432pt \oddsidemargin=18.88pt \evensidemargin=18.88pt \topmargin=14.21pt \newcommand{\Nnn}{{\Bbb N}} \newcommand{\Cnn}{{\Bbb C}} \newcommand{\bigcenter}[1]{\begin{center} {\Large\bf #1} \end{center}} %\newcommand{\qed}{\mbox{$\Diamond$}\vspace{\baselineskip}} \newcommand{\ler}{left-to-right } \newtheorem{theorem}{Theorem} \newtheorem{conjecture}{Conjecture} \newtheorem{lemma}{Lemma} \newtheorem{proposition}{Proposition} \newtheorem{definition}{Definition} \newtheorem{corollary}{Corollary} \newtheorem{example}{Example} \newcommand{\deb}{D_n^{\beta(0,1)}} \newcommand{\btree}{$\beta(0,1)$-tree } \newenvironment{proof}{\noindent {\bf Proof:}}{{\qed}} \newcommand{\btrees}{$\beta(0,1)$-trees } \newcommand{\df}{\stackrel{\mbox{\rm def }}{=}} \newcommand{\di}{\displaystyle} %\newcommand{\bigtimes}[1]{{{\large\times}\atop {#1}}} \newcommand{\bl}[2]{{\left\langle #1 \:\: \vrule \:\: #2 \right\rangle}} \newcommand{\fact}[2]{{^{\di #1}\left/ _{\di#2}\right.} } % \newcommand{\rest}[2] {#1\left| {_{#2}}\right. } \newcommand{\vanish}[1]{} \newcommand{\prek}{$P$-recursive } \begin{document} \title[Exact enumeration of 1342-avoiding permutations] {Exact enumeration of 1342-avoiding permutations\\ A close link with labeled trees and planar maps} \author{Mikl\'os B\'ona} \address{\hskip-\parindent Department of Mathematics \\ Massachusetts Institute of Technology \\ Cambridge, MA 02139} \email{bona@@math.mit.edu} \thanks{Research at MSRI is supported in part by NSF grant DMS-9022140} \begin{abstract} Solving the first nonmonotonic, longer-than-three instance of a classic enumeration problem, we obtain the generating function $H(x)$ of all 1342-avoiding permutations of length $n$ as well as an {\em exact} formula for their number $S_n(1342)$. While achieving this, we bijectively prove that the number of indecomposable 1342-avoiding permutations of length $n$ equals that of labeled plane trees of a certain type on $n$ vertices recently enumerated by Cori, Jacquard and Schaeffer, which is in turn known to be equal to the number of rooted bicubic maps enumerated by Tutte in 1963. Moreover, $H(x)$ turns out to be algebraic, proving the first nonmonotonic, longer-than-three instance of a conjecture of Zeilberger and Noonan. We also prove that $\sqrt[n]{S_n(1342)}$ converges to 8, so in particular, $lim_{n\rightarrow \infty}(S_n(1342)/S_n(1234))=0$. \end{abstract} \maketitle \section{Introduction} \subsection{Our main results} In this paper we are going to prove an exact formula for the number $S_n(1342)$ of 1342-avoiding permutations of length $n$ showing that \[S_n(1342)=\frac{(7n^2-3n-2)}{2}\cdot (-1)^{n-1} +3\sum_{i=2}^n 2^{i+1}\cdot \frac{(2i-4)!}{i!(i-2)!}\cdot {{n-i+2\choose 2}} \cdot (-1)^{n-i}, \] by first proving that the ordinary generating function $H(x)$ for these numbers $S_n(1342)$ has the following simple form: \[H(x)=\frac{32x}{-8x^2+12x+1-(1-8x)^{3/2}}.\] This is the first result we know of which provides an exact formula for the number $S_n(q)$ of permutations of length $n$ avoiding a given pattern $q$ that is longer than three and is not 1234. Results concerning the case of length three can be traced back to two centuries; \cite{catalan} already makes references to earlier work. The formula for $q=1234$ is given in \cite{ira}. Until recently it has not even been known that $S_n(1342)p_s$ for at least one $s>i \: \}$. Finally, let $l(n)=l(n-1)$. In words, $l(i)$ is the number of entries on the left of $p_i$ (inclusive) which are larger than at least one entry on the right of $p_i$. We note that this way we could define $f$ on the set of {\em all} $n$-permutations starting with the entry 1, but in that case, as we will see, $f$ would not be a bijection. (For example, the images of 1342 and 1432 would be identical). \begin{example} {\em If $p=14325$, then the labels of the nodes of $f(p)$ are, from the leaf to the root, 0,1,2,0,0. } \end{example} \begin{lemma} \label{egyenes} $f$ is a bijection from the set of $\deb$ of all \btrees on $n$ vertices consisting of one single path to the set of 1342-avoiding $n$-permutations starting with the entry 1. \end{lemma} \begin{proof} It is easy to see that $f$ indeed maps into the set of \btrees : $l(i+1)\leq l(i)+1$ for all $i$ because there can be at most one entry counted by $l(i+1)$ and not counted by $l(i)$, namely the entry $p_{i+1}$. All labels are certainly nonnegative and $l(1)=0$. To prove that $f$ is a bijection, it suffices to show that it has an inverse, that is, for any \btree $T$ consisting of a single path, we can find the only permutation $p$ such that $f(p)=T$. We claim that given $T$, we can recover the entry $n$ of the preimage $p$. First note that $p$ was 1342-avoiding and started by 1, so any entry on the left of $n$ must have been smaller than any entry on the right of $n$. In particular, the node preceding $n$ must have label 0. Moreover, $n$ is the leftmost entry $p_i$ of $p$ so that $p_j>0$ for all $j\geq i$ if there is such an entry at all, and $n=p_n$ if there is none. That is, $n$ corresponds to the node which starts the uninterrupted sequence of strictly positive labels which ends in the last node, if there is such a sequence, and corresponds to the last node otherwise. To see this, note that $n$ is the largest of all entries, so in particular it is always larger than at least one entry in any nonempty set of entries. Once we located where $n$ was in $p$, we can simply delete the node corresponding to it from $T$ and decrement all labels after it by 1. (If this means deleting the last node, we just change $l(n-1)$ $l(n-2)$ to satisfy the root-condition). We can indeed do this because the node preceding $n$ had label 0, and the node after $n$ had a positive label, by our algorithm to locate $n$. Then we can proceed recursively, by finding the position of the entries $n-1,n-2,\cdots,1$ in $p$. This clearly defines the inverse of $f$, so we have proved that $f$ is a bijection. \end{proof} \begin{lemma} \label{nullak} The number \btrees with all labels equal to zero is $C_{n-1}$. \end{lemma} \begin{proof} These \btrees are in fact unlabeled plane trees. We prove that they are in one-to-one correspondence with the 132-avoiding permutations whose last entry is $n$. Suppose we already know this for all positive integers $ki$ for which $p_j$ reaches $p_k \},$ and let $F(p)$ be the \btree defined by these labels. (Recall that a descendant of $i$ is an element of the tree whose top element is $i$). First, it is easy to see that $F$ indeed maps into the set of $\beta(0,1)$-trees: if $v$ is an internal node and $v_1,v_2,\cdots, v_k$ are its children, then $l(v) \leq 1+ \sum_{i=1}^k l(v_k)$ because there can be at most one entry counted by $l(v)$ and not counted by any of its children's label, namely $v$ itself. All labels are certainly nonnegative and all leaves, that is, the \ler minima, have label 0. If $p=361542$, then $F(p)$ is the \btree shown in Figure 4b. \[\begin{picture}(230,130)(30,30) \put(27,54){\line(1,2){33}} \put(93,54){\line(-1,2){33}} \put(27,54){\circle*{5}} \put(31,57){3} \put(41,81){\circle*{5}} \put(45,84){6} \put(79,81){\circle*{5}} \put(81,84){5} \put(93,54){\circle*{5}} \put(95,57){1} \put(60,118){\line(0,1){17}} \put(60,118){\circle*{5}} \put(62,116){4} \put(60,138){\circle*{5}} \put(62,138){2} \put(30,20){Figure 4a} \put(127,54){\line(1,2){33}} \put(193,54){\line(-1,2){33}} \put(127,54){\circle*{5}} \put(131,57){0} \put(141,81){\circle*{5}} \put(145,84){1} \put(179,81){\circle*{5}} \put(181,84){1} \put(193,54){\circle*{5}} \put(195,57){0} \put(160,118){\line(0,1){17}} \put(160,118){\circle*{5}} \put(162,116){3} \put(160,138){\circle*{5}} \put(162,138){3} \put(130,20){Figure 4b} \end{picture}\] \vspace*{12pt} To prove that $F$ is a bijection, it suffices to show that it has an inverse, that is, for any \btree $T\in \deb$, we can find the only permutation $p$ so that $F(p)=T$. We again claim that given $T$, we can recover the node $j$ which has the entry $n$ of the preimage $p$ associated to it, and so we can recover the position of $n$ in the preimage. \begin{proposition} \label{pozitiv} Suppose $p_n\neq n$, that is, $n$ is not associated to the root vertex. Then each ancestor of $n$, including $n$ itself, has a positive label. If $p_n=n$, then $l(n)=0$ and thus there is no vertex with the above property. \end{proposition} \begin{proof} If $p_n=n$, then nothing beats it, thus $p_n=0$. Suppose $p_n$ is not the root vertex. To prove our claim it is enough to show that for any node $i$ which is an an ancestor of $j$, there is an entry $p_k$ so that $p_k$ is an ancestor of $p_i$ and $n=p_j$ reaches $k$. Indeed, this would imply that the entry $p_j=n$ is counted by the label $l(i)$ of $i$. Now let $a_m=p_1>a_2>\cdots a_1=1$ be the \ler minima of $p$ so that $n$ is located between $a_r$ and $a_{r+1}$. Then $n$ certainly beats all elements located between $a_r$ and $a_{r+1}$ as $a_r$ can play the role of 1 in the 132-pattern. Clearly, $n$ must beat at least one entry $y_1$ on the right of $a_{r+1}$ as well, otherwise $p$ would be decomposable by cutting it right before $a_{r+1}$. If $y_1$ is on the right of $i$, then we are done. If not, then $y_1$ must beat at least one entry $y_2$ which is on the other side of $a_{r_1+1}$, where $y$ is located between $a_{r_1}$ and $a_{r_1+1}$ for the same reason, and so on. This way we get a subsequence $y_1, y_2, \cdots $ so that $n$ reaches each of the $y_t$, and this subsequence eventually gets to the right of $i$, since in each step we bypass at least one \ler minimum. Thus the proposition is proved. \end{proof} \begin{proposition} Suppose $p_n\neq n$. Then $n$ is the {\em leftmost} entry of $p$ which has the property that each of its ancestors has a positive label. \end{proposition} \begin{proof} Suppose $p_k$ and $n$ both have this property and that $p_k$ is on the left of $n$. (If there are several candidates for the role of $p_k$, choose the rightmost one). If $p_k$ beats an element $y$ on the right of $n$ by participating in the 132-pattern $x\:p_k\:y$, then $x\:p_k\:n\:y$ is a 1342-pattern, which is a contradiction. So $p_k$ does not beat such an element $y$. In other words, all elements after $n$ are smaller than all elements before $p_k$. Still, $p_k$ must reach elements on the right of $n$, thus it beats some element $v$ between $p_k$ and $n$. This element $v$ in turn beats some element $w$ on the right of $n$ by participating in some 132-pattern $t\:v\:w$. However, this would imply that $t\:v\:n\:w$ is a 1342-pattern, a contradiction, which proves our claim. \end{proof} Therefore, we can recover the entry $n$ of $p$ from $T$. Then we can proceed as in the proof of Lemma 1, that is, just delete $n$, subtract 1 from the labels of its ancestors and iterate this procedure to get $p$. If any time during this procedure we find that the current root is associated to the maximal entry that hasn't been associated to other vertices yet, and the tree has more than one branch at this moment, then deleting the root vertex will split the tree into smaller trees. Then we continue the same procedure on each of them. The set of the entries associated to each of these smaller trees is uniquely determined because $T$ as an unlabeled tree determines the \ler minima of $p$. Therefore, we can always recover $p$ in this way from $T$. This proves that $F$ is a bijection. Thus we have set up a bijection between the set of indecomposable 1342-avoiding $n$-permutations and $\deb$. We know from \cite{cori} that $|\deb|= t_n=3 \cdot 2^{n-1} \cdot \frac{(2n)!}{(n+2)!n!}$ and therefore the Theorem is proved. \end{proof} Note that in particular, $F$ maps 132-avoiding permutations into \btrees with all labels equal to 0 and permutations starting with the entry 1 into \btrees consisting of a single path. \begin{corollary} $S_n(1342)$ equals the number of plane forests on $n$ vertices in which each component is a $\beta(0,1)$-tree. \end{corollary} \section{Enumerative results} Tutte \cite{tutte} has obtained the numbers $t_n$ by first computing a translate of their generating function \begin{equation} \label{genfugg} F(x)=\sum_{n=1}^{\infty} 3 \cdot 2^{n-1} \cdot \frac{(2n)!}{(n+2)!n!}x^n= \frac{8x^2+12x-1+(1-8x)^{3/2}}{32x}. \end{equation} By theorem \ref{bijek}, the coefficients of this generating function are the numbers $I_n(1342)$. Therefore, the generating function of {\em all} 1342-avoiding permutations is given by the following theorem. \begin{theorem} Let $s_n=S_n(1342)$ and let $H(x)=\sum_{n=0}^{\infty}s_nx^n$. Then \begin{equation} \label{altal} H(x)=\sum_{i\geq 0}F^i(x)=\frac{1}{1-F(x)}= \frac{32x}{-8x^2+12x+1-(1-8x)^{3/2}}. \end{equation} \end{theorem} \begin{proof} Any 1342-avoiding permutation has a unique decomposition into indecomposable permutations. This can consist of $1,2,\cdots$ blocks, implying that $s_n=\sum_{i=1}^n t_is_{n-i}$, and the statement follows. \end{proof} \begin{theorem}\label{explicit} For all $n\geq 0$ we have \begin{equation} \def\eqalign#1{\null\,\vbox{\openup\jot \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil \crcr#1\crcr}}\,} \label{eformula} \medmuskip1mu \hskip-1em \eqalign{S_n(1342)&=S_n(1342)\cr&=\frac{(7n^2-3n-2)}{2}\cdot (-1)^{n-1} +3\sum_{i=2}^n 2^{i+1}\cdot \frac{(2i-4)!}{i!(i-2)!}{{n-i+2\choose 2}} (-1)^{n-i}.} \hskip-1em \end{equation} \end{theorem} \begin{proof} Multiply both the numerator and the denominator of $H(x)$ by $(-8x^2+20x+1)+(1-8x)^{3/2}$. After simplifying we get \begin{equation} \label{egyszeru} H(x)=\frac{(1-8x)^{3/2}-8x^2+20x+1}{2(x+1)^3}. \end{equation} As $(1-8x)^{3/2}=1-12x+\sum_{n\geq 2} 3\cdot 2^{n+2}x^n \frac{(2n-4)!}{n!(n-2)!}$, formula (\ref{egyszeru}) implies our claim. \end{proof} So the first few values of $S_n(1342)$ are 1,2,6,23,103,512,2740,15485,91245,555662. In particular, one sees easily that the expression on the right hand side of (\ref{eformula}) is dominated by the last summand; in fact, the alternation in sign assures that this last summand is larger than the whole right hand side if $n\geq 8$. As $\frac{(2n-4)!}{n!(n-2)!}<\frac{8^{n-2}}{n^{2.5}}$ by Stirling's formula, we have proved the following exponential upper bound for $S_n(1342)$. \begin{corollary}\label{upper} For all $n$, we have $S_n(1342)<8^n$. \end{corollary} It is straightforward to check that the numbers $I_n=t_n$ satisfy the following recurrence \begin{equation}\label{rekurziv} t_n=(8n-4)t_{n-1}/(n+2). \end{equation} In particular, $\sqrt[n]{t_n}\rightarrow 8$. Using this formula we can disprove a conjecture of Stanley claiming that for all permutation patterns $q$ of length $k$, the sequence $\sqrt[n]{S_n(q)}$ converges to $(k-1)^2 $. \begin{theorem} $\sqrt[n]{s_n}=\sqrt[n]{S_n(1342)}\rightarrow 8$ when $n\rightarrow \infty $. \end{theorem} \begin{proof} This is true as clearly $t_n\leq s_n < 8^n$ by Corollary \ref{upper} and we know from (\ref{rekurziv}) that $\sqrt[n]{t_n}\rightarrow 8$ if $n\rightarrow \infty$. \end{proof} \begin{corollary} $lim_{n\rightarrow \infty}(S_n(1342)/S_n(1234))=0$. \end{corollary} \begin{proof} Follows from $lim_{n\rightarrow \infty} \sqrt[n]{S_n(1234)}=9$ \cite{ira} \cite{Regev}. \end{proof} This Corollary certainly implies that $S_n(1342)