\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\DeclareMathOperator{\Av}{Av}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf
The Number of Permutations Avoiding a Set \\
\vskip .1in
of Generalized Permutation Patterns
}
\vskip 1cm
\large
Yonah Biers-Ariel \\
Department of Mathematics\\
Rutgers University\\
Piscataway, NJ 08854 \\
USA \\
\href{mailto:yb165@math.rutgers.edu}{\tt yb165@math.rutgers.edu} \\
\end{center}
\vskip .2 in
\begin{abstract}
We prove a conjecture that the sequence defined recursively by $a_1=1, a_2=2, a_n=4a_{n-1} - 2a_{n-2}$ counts the number of length-$n$ permutations avoiding the four generalized permutation patterns $1\text{-}32\text{-}4, 1\text{-}42\text{-}3, 2\text{-}31\text{-}4$, and $2\text{-}41\text{-}3$.
\end{abstract}
\section{Introduction}
Let $(a_n)_{n \ge 1}$ be defined recursively by $a_1=1, a_2=2$, and
$a_n=4a_{n-1}-2a_{n-2}$ for $n \ge 3$. Callan \cite[\seqnum{A006012}]{oeis} conjectured
that $a_n$ gives the number of permutations of length $n$ for which no
subsequence $abcd$ has the following two properties: $b$ and $c$ occur
consecutively in the permutation and $\max\{a,c\} < \min\{b,d\}$. In
this paper, we prove Callan's conjecture by first restating it in terms
of generalized pattern avoidance. Next, we show that the permutations
that avoid the relevant generalized patterns are exactly the same ones
that avoid a similar set of ordinary patterns, and we finally count the
number of permutations that avoid this set of ordinary patterns.
\section{Preliminaries}
\label{prelim}
First, we rewrite the conjecture in the language of pattern avoidance using the dashed notation introduced by Babson and Steingr\'imsson \cite{Babson}. Therefore, we define a \textit{pattern} to be a permutation $\pi_1\cdots \pi_k$ where some of its elements may be separated by dashes. A subsequence of a permutation is an \textit{occurrence} of a pattern if
\begin{itemize}
\item[(i)] all the elements have the same relative order as the elements of the pattern; and
\item[(ii)] if there is no dash between the $i\textsuperscript{th}$ and $i+1\textsuperscript{th}$ elements of the pattern,
then the $i\textsuperscript{th}$ and $i+1\textsuperscript{th}$ elements of
the subsequence occur consecutively in the permutation.
\end{itemize}
We say that a permutation \textit{avoids} a pattern if it does not contain any occurrence of the pattern, and a permutation avoids a set of patterns if it does not contain any occurrence of any of them. If $A$ is a set of patterns, then Av$(A)$ is the set of permutations that avoid them, and $\Av_n(A)$ is the set of length-$n$ permutations that avoid them. The following two examples should help clarify these definitions.
\begin{example} The permutation 251346 contains the subsequence 5146 which is an occurrence of the pattern 3-1-24 because the elements of the subsequence occur in the same relative order as 3124, and the 4 and 6 are consecutive in the original permutation. Note that the 5 and 1 are also consecutive - that is allowed but not necessary.
\end{example}
\begin{example} The permutation 251346 avoids 32-1-4; i.e.,
$$251346 \in \Av_6(\{32{\text{-}}1{\text{-}}4\}) \subseteq \Av(\{32{\text{-}}1{\text{-}}4\}).$$
\end{example}
We are now ready to rewrite the conjecture using this notation. To express it and the theorems in the next section concisely, we let $A= \{1\text{-}32{\text{-}}4,\allowbreak 1{\text{-}}42{\text{-}}3,\allowbreak 2{\text{-}}31{\text{-}}4,\allowbreak 2{\text{-}}41{\text{-}}3\}$ and $B=\{1{\text{-}}3{\text{-}}2{\text{-}}4,\allowbreak 1{\text{-}}4{\text{-}}2{\text{-}}3,\allowbreak 2{\text{-}}3{\text{-}}1{\text{-}}4,\allowbreak 2{\text{-}}4{\text{-}}1{\text{-}}3\}$.
\begin{proposition}\label{conjecture} A subsequence of a permutation $abcd$ has the properties that $b$ and $c$ occur consecutively in the permutation and $\max\{a,c\} < \min\{b,d\}$ if and only if that subsequence is an occurrence of a pattern in $A$.
\end{proposition}
\begin{proof}
Let $abcd$ be a subsequence with the two indicated properties. Suppose that $ac$ or $b>d$, we can apply the same argument as long as we switch $1\text{-}32\text{-}4$ with another appropriately chosen member of $A$.
Conversely, suppose that $abcd$ is an occurrence of a pattern in $A$. In every pattern in $A$, the first and third elements are 1 and 2, while the second and fourth are 3 and 4. Therefore, we have $\max\{a,c\} < \min\{b,d\}$. Further, since there is no dash between the second and third elements of any pattern in $A$, it must be that $b$ and $c$ occur consecutively.
\end{proof}
Using Proposition \ref{conjecture}, we rewrite Callan's conjecture as
\begin{equation}\label{main}
a_n = |\Av_n(A)|.
\end{equation}
\section{Main results}
We will prove two theorems. The first is that Av$(A)$ and Av$(B)$ are the same set. In particular, this theorem establishes that $|\Av_n(A)|=|\Av_n(B)|$ for $n \ge 1$. The second theorem is that $a_n=|\Av_n(B)|$ for $n \ge 1$, so together these two theorems prove that Equation \ref{main} holds.
\begin{theorem} Let $A$ and $B$ be the sets defined in Section \ref{prelim}. Then $\Av(A)=\Av(B)$.
\end{theorem}
\begin{proof}
It is immediately clear that any permutation containing an occurrence of an element of $A$ must contain an occurrence of an element of $B$, so we only need to show that the converse is also true. Let $\pi$ be a permutation. First, recall that a subpermutation $\pi_a\pi_b\pi_c\pi_d$ of $\pi$ is an occurrence of a pattern in $A$ if and only if $c=b+1$ and $\max\{\pi_a,\pi_c\} < \min\{\pi_b,\pi_d\}$. Similarly, a subpermutation $\pi_a\pi_b\pi_c\pi_d$ of $\pi$ is an occurrence of a pattern in $B$ if and only if $\max\{\pi_a,\pi_c\} < \min\{\pi_b,\pi_d\}$.
Choose any element of $B$, and suppose that $\pi$ contains an occurrence of this element. As noted above, this means that we can find $a ** \max\{\pi_a, \pi_c\}$, i.e., $e= \max\{i : i \max\{\pi_a, \pi_c\}\}$. Because $b$ is an element of $\{i : i \max\{\pi_a, \pi_c\}\}$, it follows that $e$ exists and $a < b \le e < e+1\le c< d$. Now, we claim that $\pi_a\pi_e\pi_{e+1}\pi_d$ is an occurrence of a pattern in $A$. Obviously, $e +1 =e+1$, and so it remains to check that $\max\{\pi_a,\pi_{e+1}\} < \min\{\pi_e, \pi_d\}$. Because $\max\{\pi_a,\pi_c\} < \min\{\pi_b, \pi_d\}$, we conclude that $\pi_a < \pi_d$, and by the choice of $e$, we also have $\pi_a < \pi_e$. Now, either $e+1 = c$, in which case $\pi_{e+1}=\pi_c$, or else $\pi_{e+1} < \max\{\pi_a, \pi_c\}$ because otherwise we would have chosen $e+1$ as the $\max\{i : i \max\{\pi_a, \pi_c\}\}$ instead of $e$. It follows that $\pi_{e+1} \le \max\{\pi_a,\pi_c\} < \pi_d, \pi_e$ for the same reasons as $\pi_a$. Therefore, $\max\{\pi_a,\pi_{e+1}\} < \min\{\pi_e, \pi_d\}$ and $\pi_a\pi_e\pi_{e+1}\pi_d$ is an occurrence of a pattern in $A$. We conclude that the permutations avoiding the patterns of $A$ are the same as the permutations avoiding the patterns of $B$.
\end{proof}
Armed with this theorem, we now need only show that $\big(|\Av_n(B)|\big)_{n \ge 1}$ satisfies the same recurrence as $(a_n)_{n \ge 1}$. Our strategy will be as follows: given $\Av_{n-1}(B)$, define four maps which, when all of them are applied to all the permutations of $\Av_{n-1}(B)$, will generate all of the permutations of $\Av_n(B)$. Then we will count how many permutations of $\Av_n(B)$ are double-counted in this way, and find that there are two for every element of $\Av_{n-2}(B)$, thereby establishing the recurrence.
Note that, for a permutation to avoid all the patterns of $A$, it must be the case that either 1 and 2 occur consecutively (not necessarily in that order) or either 1 or 2 is the last element of the permutation. This observation motivates the following definitions of the four maps $f_\text{before}, f_\text{after}, f_\text{end}$, and $f_\text{bump}$. Let $f_\text{before}$ be the function that inputs a permutation and outputs that permutation with all elements increased by 1 and a 1 inserted immediately before the new 2. Let $f_\text{after}$ be the function that also inputs a permutation and outputs that permutation with all the elements increased by 1 and a 1 inserted immediately after the new 2. Similarly, let $f_\text{end}$ be the function that inputs a permutation, increases all its elements by 1 and puts a 1 at the end of it, and let $f_\text{bump}$ be the function that inputs a permutation, increases all its elements by 1, replaces the new 2 with a 1 and puts a 2 at the end. The following example gives a concrete illustration of the four functions.
\begin{example} Let $\pi= 31542$. Then $f_\text{before}(\pi) = 412653, \allowbreak f_\text{after}(\pi) = 421653, \allowbreak f_\text{end}(\pi) = 426531, \allowbreak \text{ and } f_\text{bump}(\pi) = 416532$. Note that $\pi \in \Av(B)$, and so are all its images.
\end{example}
Suppose $n \ge 2$. The following two lemmas will together establish that
\begin{equation}\label{lemmas}
f_\text{before}(\Av_{n-1}(B)) \cup f_\text{after}(\Av_{n-1}(B)) \cup f_\text{end}(\Av_{n-1}(B)) \cup f_\text{bump}(\Av_{n-1}(B)) = \Av_{n}(B).
\end{equation}
\begin{lemma}
The functions $f_\text{before}, f_\text{after}, f_\text{end}$, and $f_\text{bump}$ all map elements of $\Av_{n-1}(B)$ to elements of $\Av_n(B)$.
\end{lemma}
\begin{proof}
Choose some $\sigma \in \Av_{n-1}(B)$, and consider each function in turn. If $f_\text{before}(\sigma)$ or $f_\text{after}(\sigma)$ contains an occurrence $\tau$ of a pattern in $B$, then this occurrence must use the element 1 or else $\tau$ would already be an offending pattern in $\sigma$. But then replacing 1 by 2 would again give an offending pattern in $\sigma$. Thus, no such occurrence is possible in either $f_\text{before}(\sigma)$ or $f_\text{after}(\sigma)$. In addition, if $f_\text{end}(\sigma)$ or $f_\text{bump}(\sigma)$ contains an occurrence of a pattern in $B$, then this occurrence cannot use the last element because that element is either a 1 or a 2, and patterns in $B$ only end with $3$ or $4$. So, this occurrence would already be an occurrence of the pattern in $\sigma$, and therefore cannot exist.
\end{proof}
\begin{lemma}
Every permutation in $\Av_{n}(B)$ is the image of a permutation in $\Av_{n-1}(B)$ under at least one of the functions $f_\text{before}, f_\text{after}, f_\text{end}$, or $f_\text{bump}$.
\end{lemma}
\begin{proof}
Choose some $\pi \in \Av_{n}(B)$. As previously noted, either 1 and 2 occur consecutively in $\pi$, or else either 1 or 2 is the final element of $\pi$. Let $\pi'$ be $\pi$ with the 1 removed and each element decreased by 1. We have introduced no new patterns, and so $\pi' \in \Av_{n-1}(B)$. Suppose that 1 occurs immediately before 2 in $\pi$, then $f_\text{before}(\pi') =\pi$. If the 1 occurs immediately after 2 in $\pi$, then $f_\text{after}(\pi')= \pi$. If the 1 occurs at the end of $\pi$, then $f_\text{end}(\pi')=\pi$. If the 2 occurs at the end of $\pi$, then we need to define $\pi''$, which is $\pi$ with the 1 removed, the 2 moved the position where the 1 used to be, and each element decreased by 1. Again, we have introduced no new patterns, and so $\pi'' \in \Av_{n-1}(B)$, and $f_\text{bump}(\pi'')=\pi$.
\end{proof}
Now that we have established Equation \ref{lemmas}, we can prove the main result.
\begin{theorem}
The sequence $\big(|\Av_n(B)|\big)_{n \ge 1}$ satisfies the same recurrence as $(a_n)_{n \ge 1}$.
\end{theorem}
\begin{proof} Since $\Av_{1}(B) = \{1\}$ and $\Av_{2}(B) = \{12, 21\}$, the initial conditions hold. If the four functions $f_\text{before}, f_\text{after}, f_\text{end}$, and $f_\text{bump}$ all had disjoint ranges, we could conclude from Equation \ref{lemmas} that $|\Av_n(B)|= 4\cdot |\Av_{n-1}(B)|$. Unfortunately, some permutations are counted in the range of multiple functions. Each $f$ outputs a certain kind of permutation: $f_\text{before}$ outputs permutations where 1 immediately precedes 2, $f_\text{after}$ outputs permutations where 2 immediately precedes 1, $f_\text{end}$ outputs permutations where 1 occurs at the end, and $f_\text{bump}$ outputs permutations where 2 occurs at the end. A permutation in $\Av_n(B)$ that fulfills two of these criteria will be hit twice, hence double-counted. Such permutations must be hit once by either $f_\text{before}$ or $f_\text{after}$ and again by either $f_\text{end}$ or $f_\text{bump}$ because no permutation can be hit by both $f_\text{before}$ and $f_\text{after}$ or both $f_\text{end}$ and $f_\text{bump}$. Thus, the final two elements of such permutations are 1 and 2 (not necessarily in that order). Let $g : \Av_{n}(B) \rightarrow \Av_{n-2}(B) $ be defined as the function that takes a permutation, removes from it the elements 1 and 2, and reduces all other elements by 2. If we restrict $g$ to those permutations that end in either 12 or 21, $g$ becomes a 2-to-1 map from the double-counted permutations of $\Av_{n}(B)$ to the permutations of $\Av_{n-2}(B)$, and so the number of double-counted permutations is twice $|\Av_{n-2}(B)|$. It follows that $|\Av_n(B)|=4\cdot |\Av_{n-1}(B)|-2\cdot |\Av_{n-2}(B)|$ for $n \ge 3$.
\end{proof}
\section{Acknowledgments}
The author would like to thank his (intended) advisor Doron Zeilberger for introducing him to the conjecture and Matthew Russell for providing substantial revisions to this paper.
\begin{thebibliography}{1}
\bibitem{Babson} E. Babson and E. Steingr\'imsson, Generalized
permutation patterns and a classification of the Mahonian statistics,
\textit{S\'em.\ Lothar.\ Combin.\ }\textbf{44} (2000), Art B44b.
\bibitem{oeis} OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2017. Available at
\url{https://oeis.org}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}: Primary 05A05.
\noindent \emph{Keywords:}
permutation pattern, Wilf-equivalence.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequence
\seqnum{A006012}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received July 29 2017;
revised version received August 29 2017.
Published in {\it Journal of Integer Sequences}, August 31 2017.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}
**